[자료구조] X. Trie(트라이)

1. 탄생 배경

Trie는 1959년 René de la Briandais의 <File Searching Using Variable Length Keys> 라는 논문에서 처음으로 등장하였다.

(Trie라는 단어 자체는 2년 후에 만들어졌지만 Trie의 기본 알고리즘은 이 논문이 최초라고 한다)

 

논문의 내용을 정말 간단하게 요약하자면, 모든 Search의 성능은 주어진 데이터의 크기 (N)가 가장 큰 결정 요소인데 이것을 해결하기 위해 고안된 자료구조이다.

 

즉, Search 연산에 대한 전체 복잡도를 주어진 데이터 크기와 최대한 상관이 없도록 만들어진 것이다.

 

하지만 이러한 문제점을 극복하기 위해 HashTable이라는 자료구조도 나오지 않았는가?

그러나 당시 컴퓨터들에게는 Hash 방식을 비롯한 기존 방식들이 가지고 있는 몇 몇 문제점들이 있었다.

 

1) Hashing의 문제점

Trie의 등장 전까지 많은 자료구조들이 탐색에 대한 복잡도를 줄이고자 하였다. 이전까지의 과정을 크게 종합해보면

 

Sequential Search -> Binary Search -> Hashing

      O(N)                ->      log(N)        ->     O(1)

 

이러한 흐름으로 진화해왔는데, O(1)의 엄청난 성능을 가진 Hashing의 가장 큰 문제점은 바로 버킷이 가득 찼을 경우 다시 Rehashing하는 과정이 너무 복잡하다는 점이었다. 버킷이 가득 찼을 때마다 다시 더 큰 새로운 HashTable을 생성하고 모든 데이터를 다시 다 Hash화 시키는 과정은 당시 컴퓨터들에게 큰 부담이었다.

 

또한 Hashing은 공간복잡도면에서도 치명적인 단점이 있는데, Collision이 발생할 경우 같은 해쉬값에 대한 데이터를 처리해줘야 하기 때문에 Collision이 일어날수록 메모리 공간이 늘어난다. 즉, 저용량 컴퓨터에서는 좋은 자료구조가 아닌 것이다.

Hashing의 이러한 문제점을 해결하기 위해 여러가지 방법들이 생겼지만 (Seperate Chaining, Open Adressing 등), 결국 이를 파악하고 해결하는 과정도 모두 컴퓨터 장치에게 연산부담으로 되돌아왔고 이러한 메모리 문제들을 해결하기 위해 Trie가 탄생하였다. 

 

2)  Variable Length Information

논문의 제목에서도 알 수 있듯이 Trie의 탄생 배경엔 가변길이의 정보 (Variable Length Information)에 대한 처리 기능 또한 중요한 관심사였다. Hashing의 경우 입력 Key의 모든 글자 하나 하나 Hash Function을 돌려야 해야했다. 이것은 즉 input key 길이 만큼 Hash Function을 실행해야 한다는 의미이다. 이러한 과정 없이 각 데이터들이 서로 연관성이 있어 공간을 효율적으로 쓰면서 가변길이의 데이터도 저장할 수 있는 자료구조를 만들고자 한 것이다.

 

결국 Trie는 한 마디로 가변길이의 데이터 처리와 메모리 공간을 동시에 효율적으로 관리하는 자료구조를 만들고자 생겨난 것이다.

 

저자는 이러한 문제점들을 각 엔트리가 서로 연관되있도록 하면 어떨까? 라는 사고로부터 해법을 찾기 시작한 것으로 보인다.

오토마타의 개념을 공부한 적이 있다면 직관적으로 이해가 될 것이라 생각한다.

첫 Trie의 구조 형태

 

논문 링크:

https://pdfs.semanticscholar.org/3ce3/f4cc1c91d03850ed84ef96a08498e018d18f.pdf?_ga=2.217007766.1044787041.1579181430-720908620.1579181430

 

2. 개념 정리: Trie란 무엇인가?

 

2.1 기본 개념

Trie는 여러가지 이름으로 불리기도 하는데, 그 중에 prefix tree, digital tree, retrieval tree 라고도 부른다.

Trie는 탐색 트리의 일종으로 정렬되어 있는 것이 특징이며, (key, value)의 형태의 데이터가 저장되는 자료구조이다.

(key,value)는 거의 대부분 key에는 string, value에는 숫자값이 들어가게 된다.

 

결국 Trie는 문자열을 효율적으로 저장하고 탐색하기 위한 자료구조이다.

 

해당 Trie 예시로 동작 원리에 대해서 살펴보자.

(key,value)로 이루어진 데이터 5개: (be, 7) (bee,20) (can,17) (cat, 8), (cd, 2)를 이러한 형식으로 저장하는 구조이다.

어떠한 이점을 가지게 되는것일까?

 

1. 탐색 시 주어진 문자열의 길이 만큼만 lookup을 하게 된다.

 Hash의 경우 최악의 케이스가 O(N)까지 떨어질 수 있다는 점과 대조적이다.

 

2. Collision이 일어나지 않는다.

Hash의 경우 Hash Function에 따라 달라지겠지만, 서로 다른 key값이지만 동일한 index를 가지는 경우가 발생한다. 

 

3.  Hash Function이 필요하지 않다.

 

4. Alphbetical Ordering이 자동화 된다.

 

하지만 Hash에 대해 완벽하게 우위적인 성능을 발휘하는 것은 아니다. 노드의 수 < 엔트리 수가 되기 때문에 메모리공간이 Hash보다 더 많이 요구 되는 경우가 대부분이다.

 

단점: 메모리를 많이 잡아먹음

 

2.2  실용성

 

Trie는 여러가지 구현 방법이 있다. 가장 공간적으로 효율적인 Trie는 Compact Prefix Tree (Radix Tree라고도 불린다)인데 이는 다음 글에서 다루도록 하겠다.

Trie의 가장 좋은 적용 분야는 문자열 자동 완성 기능이다. 구조를 봐서도 알겠지만, 각 노드들이 입력되는 문자에 따라 다음 노드로 이동하기 때문에 가능성이 있는 결과들에 대한 응답을 굉장히 빠른 시간안에 반환할 수 있다.

 

3. 구현 in Python

class Node:
    
    def __init__(self, char):
        self.char = char
        self.children = {} #dictionary 데이터형이다
        self.word_finished = False #String형의 마지막 null과 같은 역할
        self.counter = 0 #해당 노드가 전체 Trie에서 어느 높이에 있는지 저장하는 변수
        
class Trie:
    
    def __init__(self):
        self.root = Node('*') #root는 빈 노드로 남겨둔다.
        
    def insert(self,word):
        current = self.root
        #word를 한 글자씩 확인
        for char in word:
            
            #자식 노드 중 해당 글자를 가지고 있을 때
            if char in current.children:
                #다음 노드로 넘어간다
                current = current.children[char]
                current.counter += 1
            
            #자식 노드 중 해당 글자가 없을 때
            else:
                new_node = Node(char)
                #children 딕셔너리는 (글자, 노드) 형태로 저장된다
                current.children[char] = new_node
                #다음 노드로 넘어간다
                current = new_node
                current.counter += 1
        
        #word의 insert가 끝났다
        current.word_finished = True
        
    def search(self,word):
        
        #빈 Trie 예외처리
        if not self.root.children:
            return False
        
        
        current = self.root
        #word를 한 글자씩 확인
        for char in word:
            #자식 노드 중 해당 글자를 가지고 있을 때
            if char in current.children:
                #다음 노드로 넘어간다
                current = current.children[char]
            #하나라도 일치하지 않으면 Trie내에 존재하지 않는 word이기에 거짓    
            else:
                return False
            
            #word_finished 변수가 True일때만 Search 성공적
            if current.word_finished:
                return True
            
            return False