본문 바로가기
IT/Algorithm

Trie

by 물통꿀꿀이 2019. 6. 11.

Trie에 대해 알아보려고 한다.


Trie를 간단히 설명하면 문자열을 저장하는 트리 기반의 자료 구조이다. 자세한 내용을 알아보기 전에 코드를 살펴면서 어떤 것인지 알아보도록 하자.


그림 1. Trie


그림 1을 보면 트리의 노드 마다 각각의 문자가 담겨있는 것을 확인 할 수 있다. 이는 Trie는 문자열을 문자로 하나씩 쪼개서 자식 노드로 만든다.


그러므로 그림 1을 다시 살펴보면..

- geer

- geeks

- geekt

- geez

총 4개의 문자열이 있음을 알 수 있다. (추가로, 문자열의 각 인덱스가 노드의 깊이인 것 또한 확인 할 수 있다.)

그런데 특이하게도 루트 노드는 특정한 문자로 표현되지 않는다. 곰곰이 생각해보면 쉽게 알 수 있는데 예를 들어 'G' 문자로 루트 노드를 시작하면 Trie에서는 'G'로 시작하는 문자열만 받을 수 있어 제한적이 된다. 하지만 루트 노드를 사용하지 않는 대신 각 문자열의 첫 번째 문자만 참조하고 있다면 Trie에서는 여러 개의 문자열을 바탕으로 트리를 만들 수 있다.


                       root
                    /   \    \
                    t   a     b
                    |   |     |
                    h   n     y
                    |   |  \  |
                    e   s  y  e
                 /  |   |
                 i  r   w
                 |  |   |
                 r  e   e
                        |
                        r

위와 같이 't', 'a', 'b'로 시작하는 문자열을 구성 할 수 있다.


그렇다면 코드를 살펴보도록 하자.

class TrieNode:
# Trie node class
def __init__(self):
self.children = [None] * 26

# isEndOfWord is True if node represent the end of the word self.isEndOfWord = False 


Trie는 각 노드에 대한 특별한 자료 구조를 사용한다. 문자열의 인덱스 간에 노드로 연결되어야 하기 때문이다.

그래서 위의 코드에서는 자식 노드를 배열로 만드는데 문자열을 알파벳이라는 가정하에 크기 26의 배열로 정의한다. 또한 isEndOfWord 라는 변수는 문자열의 끝을 표현하기 위함이다. 


class Trie:
# Trie data structure class
def __init__(self):
self.root = self.getNode()

def getNode(self):

# Returns new trie node (initialized to NULLs)
return TrieNode()

def _charToIndex(self, ch):

# private helper function
# Converts key current character into index
# use only 'a' through 'z' and lower case

return ord(ch) - ord('a')

def insert(self, key):

# If not present, inserts key into trie
# If the key is prefix of trie node,
# just marks leaf node
pCrawl = self.root
length = len(key)
for level in range(length):
index = self._charToIndex(key[level])

# if current character is not present
if not pCrawl.children[index]:
pCrawl.children[index] = self.getNode()
pCrawl = pCrawl.children[index]

# mark last node as leaf
pCrawl.isEndOfWord = True

def search(self, key):

# Search key in the trie
# Returns true if key presents
# in trie, else false
pCrawl = self.root
length = len(key)
for level in range(length):
index = self._charToIndex(key[level])
if not pCrawl.children[index]:
return False
pCrawl = pCrawl.children[index]

return pCrawl != None and pCrawl.isEndOfWord  


Trie 에서는 Insert와 Search 작업을 수행한다. 먼저 Insert는 트리에 문자열을 넣으며 Search는 이미 구성된 트리에서 문자열을 찾는 작업이다.

그래서 Insert 부분은 루트 노드로 시작하여 입력 받은 문자열의 크기를 바탕으로 자식 노드를 하나씩 만들어 간다. 그리고 Search 또한 문자열의 크기를 바탕으로 자식 노드를 찾아 내려가면서 문자열을 찾는다.


이렇듯 코드를 바탕으로 Trie가 어떤식으로 구성 되고 동작하는지 알아보았다. 그럼 이제부터 본격적으로 개념에 대해 알아보려고 한다.


Trie는 문자열을 검색하는데 효율적인 자료 구조를 가진다. BST(Binary Search Tree)와 비교를 해봤을 때 BST는 O(M * LogN) 이 걸리는 반면에 Tri는 O(M) 정도의 시간이 걸린다.

* BST에서 문자열을 찾는데 LogN과 문자열의 길이 M (문자열을 찾아 전체 비교를 해야하기 때문에)

* Tri는 문자열의 길이만

물론 Trie가 추가적인 자료 구조로 인해 메모리가 좀 더 소비되긴 하지만 시간 상 이득을 취할 수 있다.


이 외에도 Trie를 사용하는 이유를 살펴보면,

1) 알파벳 순서대로 문자열을 찾을 수 있다. (Hashing은 Trie와 시간 복잡도가 비슷하나 Hash를 만들기 때문에 쉽지 않다.)

2) Prefix를 찾는 것이 쉽다. (맨 처음 예를 확인해봐도 Prefix인 'gee'를 빠르게 찾을 수 있다.)


다만 앞서 짤막하게 언급했었지만 공간 복잡도가 생각 보다 클 수 있다. O(알파벳 사이즈 26 * 문자열 길이 * 문자열 개수) 이다.


Reference

https://www.geeksforgeeks.org/trie-insert-and-search/

https://www.geeksforgeeks.org/advantages-trie-data-structure/

'IT > Algorithm' 카테고리의 다른 글

0-1 Knapsack  (0) 2019.06.28
Window Sliding Technique  (0) 2019.06.22
Topological Sorting  (0) 2019.06.10
Segment Tree  (0) 2019.06.07
Boyer–Moore Majority Vote  (0) 2019.06.06

댓글