트라이(Trie)

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

트라이(Trie)란?

문자열에 특화된 자료구조로 길이가 m인 문자열을 $O(m)$에 찾을 수 있는 자료구조다. 만약 최대 길이가 m이고 개수가 n인 집합에서 문자열이 포함되어 있는지 화인하려면 $O(nm)$이 요구되며 설령 사전작업으로 정렬한 뒤 이분 탐색을 하여도 정렬 과정에 $O(mn\log\ n)$과 탐색 과정에 $O(mlog\ n)$이 소요된다. (정렬에 $nlog\ n$, 최대길이 m), (탐색에 $log\ n$, 최대길이 m)

압도적으로 시간복잡도 문제를 해결할 수 있기 때문에 자연어 처리 등에 많이 보인다.

트라이 구현

기본적으로 다진 트리(m-ary Tree)로 구현된다. 순서대로 각 문자열마다 색인이 생성되는 원리로 초고속 탐색이 가능하지만 "ae"나 "ea"가 전혀 다른 트리에 속하는 등 공간복잡도가 굉장히 커지는 문제가 있다.

루트 노드를 비워두고 루트 하단의 노드들로부터 차례대로 각 글자가 입력된다. 각 substring에 대해 트라이에 입력된 글자는 맨 앞에 위치하므로 접두사라 표현할 수 있고 이 때문에 트라이를 접두사 트리(Prefix Tree)라고도 부른다. defaultdict 기반으로 트라이를 직접 구현해보자.

Trie 노드 선언

class TrieNode:
    def __init__(self):
        self.fin = False # 해당 노드에서 단어 종료 여부
        self.child = defaultdict(TrieNode) # 자식 노드 저장

Trie 선언

class Trie:
    def __init__(self):
        self.root = TrieNode() # 첫째 노드 초기화

Trie에 값 삽입

    def insert(self, word):
        node = self.root
        for w in word: # 첫 번째 글자부터
            node = node.children[w] # 노드 조회 or 생성 반복
        node.fin = True # 글자 입력이 종료되면 단어의 끝을 표기
        '''
        자식노드를 defaultdict로 생성하므로
        최상의 노드의 값이 빈 것처럼 트라이가 만들어진다.
        '''

Trie 특정 단어 조회

    def search(self, word):
        node = self.root
        for w in word:
            if w not in node.children:
                return False # 자식 노드에 없으면 종료
            node = node.children[w] # 진행
        return node.fin # 단어 종료 여부 리턴

Trie 접두사 존재 여부 조회

    def startsWith(self, word):
        node = self.root
        for w in word:
            if w not in node.children:
                return False
            node = node.children[w]
        return True # 단어 종료 상관없음

전체 python 코드

from collections import defaultdict


class TrieNode:
    def __init__(self):
        self.fin = False
        self.children = defaultdict(TrieNode)


class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for w in word:
            node = node.children[w]
        node.fin = True

    def search(self, word):
        node = self.root
        for w in word:
            if w not in node.children:
                return False
            node = node.children[w]
        return node.fin

    def startWith(self, word):
        node = self.root
        for w in word:
            if w not in node.children:
                return False
            node = node.children[w]
        return True


t = Trie()
s_list = ["app", "api", "blur", "blog", "door", "doom"]
for s in s_list:
    t.insert(s)
print(f'search for doom : {t.search("doom")}')
print(f'start with blu : {t.startWith("blu")}')
print(f'search for apple : {t.search("apple")}')