트라이(Trie)

이경섭·2022년 9월 17일

Algorithm

목록 보기

12/15

트라이(Trie)는 검색 트리의 일종으로 일반적으로 키가 문자열인, 동적 배열 또는 연관 배열을 저장하는 데 사용되는 정렬된 트리 자료구조다.

트라이(Trie)는 실무에서 유용하게 쓰이는 자료구조로, 특히 자연어 처리(NLP) 분야에서 문자열 탐색을 위한 자료구조로 널리 쓰인다.

1959년에 처음 공개됐으며, 검색을 뜻하는 'retrieval' 에서의 중간 음절에서 유래되었다.

초창기에는 '트리'로 발음했으나, 기존의 트리(Tree)와 구분하기 위해 '트라이'로 불린다.

-[출처] - 파이썬 알고리즘 인터뷰

🤔 연관 배열이란?

키 하나와 값 하나가 연관되어 있으며 키를 통해 연관되는 값을 얻을 수 있는 자료구조
연상 배열, 결합형 배열, 맵(map), 사전(dictionary)으로 부르기도 한다.
-[출처] - 위키피디아

트라이(Trie) 자료구조란?

트라이(Trie)는 문자열의 집합을 표현하는 '트리 자료구조'이다

원하는 원소를 찾기 위해 자주 이용되는 이진검색(BS) 은 원소를 찾는데 O(logN)의 시간이 걸린다.
그러므로 문자열의 경우, 문자열의 길이(M) 만큼의 원소를 찾기 때문에 O(MlogN)의 시간이 걸린다.

이러한 이진탐색트리보다도 더 빠른 O(N) 시간으로 문자열을 찾을 수 있는 자료구조가 '트라이'이다.

트라이(Trie) 작동원리

그림으로 문자열 집합 {"apple", "appear", "appeal"} 을 트라이로 표현한다면 아래와 같다.

이처럼, 트라이는 집합에 포함된 문자열의 각 문자들이 노드로 연결된 다진 트리 형태의 자료구조이다.

문자열을 탐색하기 위해선 첫 문자의 노드부터 다음 문자 존재 유무를 판단하여 있을 시 연결된 노드로 이동 탐색을 진행한다.
해당 문자열의 끝에 도달했을 때, 끝나는 문자열에 True/False 유무 판단하여 True 값일 시 해당 문자열이 문자열 집합에 포함된다는 것을 알 수 있다.

그리고, 트라이의 중요 속성 중 하나는 루트에서부터 내려가는 경로의 문자를 순서대로 모으면 탐색하려는 문자열을 얻을 수 있다는 것이다.

위 그림의 'apple'을 찾는다고 가정하면, a -> ap -> app -> appl -> apple로 'apple'을 도출할 수 있다.
따라서 각 노드에 모든 문자열을 저장할 필요없이 하나의 문자 정보만 순서대로 저장하면 충분하다.

트라이(Trie) 자료구조의 장/단점

트라이의 장점은 앞에서도 언급했듯이 빠른 탐색 시간[O(N)] 이다.
문자열의 집합에 문자열을 추가해도 문자열의 길이만큼 노드를 따라가거나, 추가하면 되기 때문에,
추가(insert)와 추가된 문자열 탐색(search)도 O(N) 시간복잡도를 가진다.

반면에, 단점은 필요한 메모리 크기가 너무 크다는 점이다.
문자열이 모두 영소문자(a-z)로 이루어져 있다고 해도, 자식 노드를 가리키는 26개의 포인터를 저장해야 한다.
최악의 경우에는 집합에 포함되는 문자열들의 길이의 총합만큼 노드가 필요하므로,
총메모리는 O(포인터 크기 * 포인터 배열 개수 * 총노드의 개수)가 된다.
만약, 1000자리의 문자열이 1000개만 들어온다고 하더라도 100만 개의 노드가 필요하고, 포인터의 크기가 8byte라고 하면 약 200MB의 메모리가 필요하게 된다.

따라서, 이 단점을 해결하기 위해서 보통 map이나 vector를 이용하여 필요한 노드만 메모리를 할당하는 방식들을 이용한다.
문제에 따라서 메모리 제한이 빡빡한 경우에는 최적화가 꽤나 까다롭기 때문에, 문제에서 주어진 조건을 보고 트라이를 이용할 수 있는 문제인지 파악하는 것이 중요하다.

트라이(Trie) 구현

[ 파이썬 알고리즘 인터뷰 - p.461 ~ 465 ]에 나오는 트라이 구현을 참조하여 아래와 같이 파이썬으로 트라이를 구현해 보았다.

class TrieNode:
    def __init__(self):
        self.children = {}
        self.endOfWord = False
        
class Trie:
    def __init__(self):
        self.root = TrieNode()
        
    def insert(self, word: str) -> None:
        cur = self.root                        
        for c in word:                        
            if c not in cur.children:         
                cur.children[c] = TrieNode() 
            cur = cur.children[c]             
        cur.endOfWord = True          

    def search(self, word: str) -> bool:
        cur = self.root
        for c in word:
            if c not in cur.children:
                return False         
            cur = cur.children[c]  
        return cur.endOfWord
    
    def startsWith(self, prefix: str) -> bool:
        cur = self.root
        for c in prefix:
            if c not in cur.children:
                return False
            cur = cur.children[c]
        return True

1. node

아래와 같이 문자를 넣을 맵(map) 과 문자열의 끝을 판변할 boolean 데이터로 node를 구성한다.

class TrieNode:
    def __init__(self):
        self.children = {}
        self.endOfWord = False

2. 삽입(insert)

위에서 설명했듯이 공간복잡도를 낮추기 위해 map을 이용해 필요한 노드만을 생성하며
문자열의 길이만큼 for문을 돌아 node를 생성, O(N)의 시간복잡도로 연선 처리를 한다.

class Trie:
    def __init__(self):
        self.root = TrieNode()
        
    def insert(self, word: str) -> None:
        cur = self.root                        
        for c in word:                        
            if c not in cur.children:         
                cur.children[c] = TrieNode() 
            cur = cur.children[c]             
        cur.endOfWord = True

3. 탐색(search)

위에서 언급했듯이 for문을 통해 탐색할 문자열의 각 문자를 차례로 탐색하여 O(n)의 시간복잡도로 연산 처리를 한다.

    def search(self, word: str) -> bool:
       cur = self.root
       for c in word:
           if c not in cur.children:
               return False         
           cur = cur.children[c]  
       return cur.endOfWord