Trie 자료구조

https://en.wikipedia.org/wiki/Trie를 참고하면

https://en.wikipedia.org/wiki/Trie

 

digital tree 또는 prefix tree라고 하는 trie는 일종의 검색 트리입니다. 

동적인 set을 저장하거나 연관있는 배열을 저장할 때 쓰입니다. 
key는 일반적으로 문자열을 저장합니다. 

binary search tree와는 다르게 노드는 관련된 키를 저장하지 않습니다.
대신 트리의 위치가 키를 정의하는 방식입니다.
그래서 키는 트리 구조 전체에 분산되어 있습니다.

노드의 모든 하위 항목에는 해당 노드와 연관된 문자열의 공통 접두사가 있습니다.
루트는 빈문자열과 연관되어 있습니다.

위 그림과 같이 "te"의 하위 항목인 "tea", "ted", "ten"은 "te"라는 공통 접두사가 있다고 보시면 됩니다.

 

아래는 위키피디아에 있는 Python3 코드에 find_prefix함수를 넣어 Trie class를 구현하였습니다.

from collections import deque
''' https://en.wikipedia.org/wiki/Trie '''

class Node:
   def __init__(self) -> None:
       # Note that using a dictionary for children (as in this implementation)
       # would not by default lexicographically sort the children, which is
       # required by the lexicographic sorting mentioned in the next section
       # (Sorting).
       self.children = {}  # mapping from character to Node
       self.value = None

class Trie:
    def __init__(self) -> None:
        self.node = Node()

    def find(self, key: str):
        """Find value by key in node."""
        node = self.node
        for char in key:
            if char in node.children:
                node = node.children[char]
            else:
                return None
        return node.value

    def insert(self, key: str, value=None) -> None:
        """Insert key/value pair into node."""
        if value == None:
            value = key 
        node = self.node
        for char in key:
            if char not in node.children:
                node.children[char] = Node()
            node = node.children[char]
        node.value = value

    def find_prefix(self, key: str):
        curr_node = self.node 
        result = [] 
        subtrie = None 
        for char in key: 
            if char in curr_node.children: 
                curr_node = curr_node.children[char] 
                subtrie = curr_node 
            else: 
                return None 

        dq = deque(subtrie.children.values()) 
        while dq: 
            curr = dq.popleft() 
            if curr.value != None: 
                result.append(curr.value) 

            dq += list(curr.children.values()) 

        return result

if __name__ == '__main__':
    trie = Trie()
    trie.insert('g')
    trie.insert('ga')
    trie.insert('go')
    trie.insert('goo')
    trie.insert('god') 
    trie.insert('good')
    print(trie.find_prefix('g'))

find_prefix 함수는 입력 접두사로 시작하는 문자열을 출력합니다.

 

트라이는 좋은 자료구조이지만 실서비스에 사용하기 위해서는 해결해야 하는 이슈[1]가 있다고 합니다.

 

1. Lock없이 동시에 검색 조회
2. 조회 기능 차단 없이 노드를 동적으로 추가

즉 동시성을 지원하도록 트라이 자료구조를 구현해야 위 문제를 해결할 수 있습니다.
그러나 파이썬은 GIL 때문에 CPU bound에선 멀티쓰레딩으로 성능 향상을 기대하기 어렵습니다.

기회가 된다면 파이썬으로 트라이 자료구조의 성능을 높이기 위한 방법을 알아보도록 하겠습니다.

 

[1] brunch.co.kr/@springboot/75