Trie는 이 구조를 구현한 라이브러리도 여럿있어서 파이썬으로 구현하기는 쉬울 것이다. 하지만 trie에 대해 더 잘 이해하고 연습도 할 겸 여기저기에서 참조해가며 직접 만들어 보았다. 이번에는 trie에 대한 간단한 개념과 문자열의 삽입과 조회 부분의 구현까지 진행할 것이다.
특징
Trie는 prefix tree라고도 불리는 트리 구조의 알고리즘이다. Trie는 다음과 같은 특징이 있다.
- 검색이 빠르고,
- 문자열을 키로하는 동적 집합이나 연관 배열로 사용되고
- 노드는 키를 갖지 않는 대신 노드의 위치가 키 역할을 하고
- root가 빈 스트링이라는 특징이 있다.
시간 복잡도
시간 복잡도는 알고리즘의 수행시간 분석결과를 나타내는 용어이다. 당연히 시간 복잡도가 낮을수록 좋으며 연산 횟수를 계산하고, 처리해야 할 데이터의 수 n에 대한 연산횟수 함수 T(n)을 구성하여 구한다.
Trie의 시간 복잡도는 대표적인 트리 구조 중 하나인 이진 검색 트리(Binary Search Tree)와 비교를 해보도록 하겠다.
| 데이타 구조 | 시간 복잡도 |
|---|
| (정수/실수) 이진 검색 트리 | O(logN) |
| 문자열 이진 검색 트리 | O(MlogN) |
| 트라이 | O(M) |
문자열은 길이가 변하기 때문에 검색 시간이 많이 소요된다. 길이가 고정된 정수나 실수는 O(logN)의 시간이 걸리지만 문자열은 길이가 변하기 떄문에 문자열의 최대 길이 M을 곱한 O(MlogN)이 된는데 trie는 이러한 문제를 해결하기 위해 고안된 자료구조이다.
트라이의 구조
알파벳만을 사용하여 trie를 구성할 경우 각 노드는 26개의 알파벳과 1개의 공백으로 구성된 27개의 포인터를 갖고있는 배열을 갖고 있다.
문자열 집합 : S = {"BE", "BET", "BUS", "TEA", "TEN"}을 trie로 구성한 그림은 다음과 같다.
루트는 빈 노드이며 부모노드에 접미 문자를 하나씩 붙여 자식 노드를 구성한다. 노드와 노드를 연결하는 edge는 접미문자가 붙는 것을 나타낸다. 그리고 회색으로 표시된 노드는 종료 노드를 나타낸다. 루트에서 해달 종료 노드까지의 문자를 모으면 원하는 검색어를 발견할 수 있다.
구현
우선은 노드 부분에 대한 내용이다.
import collections
class Node:
def __init__(self, label=None, data=None):
self.label = label
self.data = data
self.children = collections.defaultdict(Trie)
self.NodeCount = 0
def add_child(self, key, data=None):
if not isinstance(key, Node): # key가 Node의 instance가 아니면
self.children[key] = Node(key, data)
else:
self.children[key.label] = key
def __getitem__(self, key):
return self.children[key]
def __str__(self, depth=0):
s = []
for key in self.children:
s.append('{}{} {}'.format(' ' * depth, key or '#', '\n'
+ self.children[key].__str__(depth + 1)))
return ''.join(s)
collections 라이브러리를 임포트하고 Node라는 클래스를 생성한다. Node 클래스의 생성자에 있는 label과 data는 각각 edge와 노드에 저장되는 데이터를 의미한다. NodeCount는 자식노드의 숫자를 의미한다. 막 생성된 노드는 자식이 없기 때문에 0으로 설정한다. add_child 함수는 말 그대로 부모노드에 자식노드를 추가하는 함수의 역할을 한다.
__str__()은 trie 구조를 출력하는 용도로 사용된다. Trie를 출력하는 방식에 대해 찾아볼 때 대부분 중괄호({, })와 콤마(,) 그리고 _end_를 사용하여 나타내는 방식이었다. 개인적으로 출력되는 모양이 알아보기 힘들고 지저분해 보이던 와중에 위 코드와 같은 방식으로 나타내는 것을 발견하였는데 개인적으로 참 마음에드는 코드이다. 방식은 children에 저장된 모든 key값을 받아와서 띄어쓰기와 개행으로 trie를 표현했는데 각 문자열의 마지막에는 #을 추가해 줘서 내가 봤을때는 굉장히 구조를 파악하기 수월했다.
class Trie:
def __init__(self):
self.head = Node()
def __getitem__(self, key):
return self.head.children[key]
def __str__(self, depth=0):
return self.head.__str__()
def add(self, word):
current_node = self.head
word_finished = True
for i in range(len(word)):
if word[i] in current_node.children:
current_node = current_node.children[word[i]]
else:
word_finished = False
break
if not word_finished:
while i < len(word):
current_node.add_child(word[i])
current_node.NodeCount += 1
current_node = current_node.children[word[i]]
i += 1
current_node.add_child(None)
current_node.NodeCount += 1
current_node = current_node.children[None]
current_node.data = word
def insert_word(self, word):
for word in word.split():
self.add(word)
이제 trie를 구현하는 부분이다. 원리는 간단하다. 기존에 있는 문자열이 있는지 확인하고 기존에 없는 문자열들만 새로 자식노드에 추가해주는 방식으로 문자열의 삽입이 진행된다.자식노드가 추가되면 NodeCount의 숫자를 증가시켜 해당 노드에 몇개의 자식이 있는지 파악한다. insert_word 함수는 입력받은 문장을 공백을 기준으로 단어별로 나누어서 add함수에 넣어주는 역할을 담당한다.
if __name__ == '__main__':
trie = Trie()
trie.insert_word('stan stem standard money')
print(trie)
마지막으로 실행 부분이다. insert_word 함수를 통해 stan, stem, standard, money를 입력한 결과를 출력하면
위 그림과 같은 결과가 나온다. stan과 standard을 보면 stan은 standard의 부분집합(?)과 같은 단어이다. #이 없으면 stan이 없으면 출력 화면상에서 stan이 삽입이 되어있는지 확인할 방법이 없을것이다. 하지만 #이 있기 때문에 두 단어가 구분이 된다.
---------------------------------------------------------------------------------------------------
출처
- https://nickstanisha.github.io/2015/11/21/a-good-trie-implementation-in-python.html
- http://clojure.or.kr/wiki/doku.php?id=study:algorithms:trie
- Laboratory Module D, TRIE TREES
