Level Compressed Trie

 

lc-trie는 학부시절 네트워크 시간에 배운 longest prefix matching(이하 lpm) 을 효율적으로 하기 위해 만들어진 알고리즘입니다. 네트워크에서 lpm은 서브넷팅된 IP 대역대를 prefix에 따라 다음 hop을 탐색하기 위해 사용됩니다. 이런 lpm을 효율적으로 수행하기 위해서 고안된 lc-trie는 커널에서도 lpm을 위해 사용되는 자료구조입니다.

 

위 그림은 일반적인 이진트리로 특히 0,1 비트로 이루어진 IP주소를 탐색하기 용이한 자료구조입니다. 루트에서 시작하여 하나의 비트씩 비교하며 노드를 탐색하여 prefix 더 이상 진행하지 못하면 해당 노드의 next 값을 반환합니다.

오른쪽 트리는 path를 compress를 수행한 구조입니다. patricia trie라고 합니다. 하나의 자식노드를 가진 노드를 압축하여 쓸모없는 메모리 공간을 줄이고 트라이 높이를 줄였기에 쿼리 횟수가 줄어들었습니다. 하지만 여전히 비어있는 공간이 보입니다.

위 트리는 최종적으로 한 노드에서 모든 child 노드가 비어있는 경우, level compress를 하여 빈공간을 최소화한 lc-trie입니다.

이러한 lpm을 위한 트라이구조는 네트워크 뿐만 아니라 자동완성 같은 string matching에서도 자주 사용되는 구조입니다. 아래 코드는 string 매칭을 위한 이해하기 쉽도록 재귀를 이용하여 lc-trie를 구현해봤습니다. 

 

//https://gist.github.com/rlaxodbs0/baa845f251a6c31ecf5456431f0ba6be
package lctrie

import (
	"errors"
	"fmt"
	"sync"
)

type LcTrie struct {
	mu sync.RWMutex
	head *Node
}

type Node struct {
	key string
	skip int
	child map[string]*Node
	value interface{}
}

func (n *Node) toString() string {
	keys := make([]string, 0, len(n.child))
	for key := range n.child {
		keys = append(keys, key)
	}
	return fmt.Sprintf("key: %s, skip: %d, %v value: %v", n.key, n.skip, keys, n.value)
}

func Init() *LcTrie  {
	return &LcTrie{head:&Node{}}
}

func (lct *LcTrie) Store(key string, value interface{}) error {
	lct.mu.Lock()
	defer lct.mu.Unlock()
	cur := lct.head
	for _, v := range key {
		if cur.child != nil {
			if next, exists := cur.child[string(v)]; !exists{
				cur.child[string(v)] = &Node{}
				cur = cur.child[string(v)]
			} else {
				cur = next
			}
		} else {
			cur.child = map[string]*Node{string(v): &Node{}}
			cur = cur.child[string(v)]
		}
	}
	if cur.key == key {
		return errors.New("Duplicated Key")
	}
	cur.key = key
	cur.value = value
	return nil
}

func (lct *LcTrie) ComputePathCompress(start *Node, cur *Node, compressed string) {
	keys := make([]string, 0, len(cur.child))
	for key := range cur.child {
		keys = append(keys, key)
	}
	if len(cur.key) != 0 || len(keys) == 0 {
		cur.skip = len(compressed) - 1
		delete(start.child, string([]rune(compressed)[0]))
		start.child[compressed] = cur
		for idx := range keys {
			next := cur.child[keys[idx]]
			lct.ComputePathCompress(cur, next, keys[idx])
		}
	} else {
		if len(keys) > 1 {
			cur.skip = len(compressed) - 1
			delete(start.child, string([]rune(compressed)[0]))
			start.child[compressed] = cur
			for idx := range keys {
				next := cur.child[keys[idx]]
				lct.ComputePathCompress(cur, next, keys[idx])
			}
		} else {
			for idx := range keys {
				next := cur.child[keys[idx]]
				lct.ComputePathCompress(start, next, compressed + keys[idx])
			}
		}
	}
}

func (lct *LcTrie) levelCompressPossible(cur *Node) bool {
	if len(cur.child) == 0 {
		return false
	}
	for idx := range cur.child {
		if len(cur.child[idx].key) != 0 {
			return false
		}
	}
	return true
}

func (lct *LcTrie) ComputeLevelCompress(cur *Node) {
	keys := make([]string, 0, len(cur.child))
	for key := range cur.child {
		keys = append(keys, key)
	}
	if lct.levelCompressPossible(cur){
		for idx := range keys {
			next := cur.child[keys[idx]]
			nextKeys := make([]string, 0, len(next.child))
			for key := range next.child {
				nextKeys = append(nextKeys, key)
			}
			for nextIdx := range nextKeys {
				delete(cur.child, keys[idx])
				cur.child[keys[idx] + nextKeys[nextIdx]] = next.child[nextKeys[nextIdx]]
			}
		}
		lct.ComputeLevelCompress(cur)
	} else {
		for idx := range keys {
			next := cur.child[keys[idx]]
			lct.ComputeLevelCompress(next)
		}
	}
}

func (lct *LcTrie) Compress() { // compress trie
	lct.ComputePathCompress(lct.head, lct.head, "")
	lct.ComputeLevelCompress(lct.head)
}