코드분석1_1 - Trie 자료구조란

앞의 "코드분석1 - 한글처리 알고리즘" 에서 언급한 Trie에 대해 먼저 알아보고 가도록 하자.
(트리 아님. 트라이 임) 
Trie(트라이)는 자료구조의 한 종류로써 빠른 단어 검색에 용이하다.

만약 단어를 저장할때, 배열을 쓴다고 하자. 그러면
0: god
1: created
2: space
3: genesis
4: noooooo
5: 
6: 
.
.
.
이런식으로 저장이 될것이다. 이렇게 배열에 쌓아두고 찾으려면 간단하게 처음부터 찾는다고 하면 time-complexity는 worst case에서 linear한 O(n)이 된다. 

심지어 같은 알파벳묶음을 가진 단어들이 한 배열에 저장되어있다면 공간의 낭비가 심각해진다.
0: genesis
1: genesis!
2: genesis???
3: genesis;
4: genesis!!!!!!!
5:
6:
....
따라서 단어를 저장하는데 배열을 사용하는 것은 빠르지도, 공간도 많이 잡아먹는 자료구조가 될 것 이다.

이를 해결하는 것이 '트라이' 이다. 트라이 또한 트리의 일종이라고 볼 수 있는데,

저장하는 방식은 만약 romane romanus romalus rubens ruber 을 저장한다고 하면,(trie자료구조예시.jpg 참고)

모든 단어가 r을 가지고 있고 다음 철자들 중에서 갈래가 나뉘어진다.

r'oma'ne r'oma'nus r'oma'lus r'ube'ns r'ube'r

이렇게 r다음에 oma 또는 ube 두가지의 갈래길이 나오고 그러면 트리구조로 child를 두개 생성해서 저장한다.

그리고 나서 ome 다음으로 따라오는 철자를 똑같은 방식으로 트리 형식으로 저장한다. 

roma/'n'e 

roma/'n'us 

roma/lus

이므르, 트리구조에 oma의 child로 n 과 lus를 생성한다.

이제 romalus 라는 단어는 저장이 완료 되었다.

n의 child를 저장하기 위해서, romane romanus 를 살펴보면, n다음으로 공통되는 철자가 없으므로, n의 child로 'e' 와 'us'를 n의 child로 저장한다. 

이런식으로 모든 단어를 저장하면 업데이트 된 그림처럼 저장이 되는 것을 알수 있다.

중요한 것은 문자열을 찾는 시간복잡도 인데, 이진탐색을 사용하면, 최대 길이가 m인 문자열 n개의 집합에서 검색을 한다고 할 때, 

 O(mlog⁡n)로 단축시킬 수 있지만, 정렬 과정 자체에 O(nmlog⁡n)의 시간이 걸린다, 
 
 하지만 trie 자료구조를 사용하게 되면,
 [편집]

문자열 집합의 개수와 상관 없이 찾고자 하는 문자열의 길이가 시간 복잡도가 된다. 

즉, 문자열의 길이가 mmm이라면 시간 복잡도는 O(m). 

그 이유는 간단하다. 트라이를 구현할 때, nnn과 mmm이 상대적으로 작다면[6] 배열을 사용할 텐데, 

현재 노드의 위치를 i, j번째 문자라고 한다면 trie[i][j]의 위치를 조회하는 건 O(1)에 수행이 가능하다. 

여기서 m번을 수행하니 O(m)의 시간이 걸리는 것이다. 

하지만 n과 m이 큰 경우에는, 메모리 확보를 위해 시간을 희생해서라도 n이 진짜 무식하게 큰 게 아닌 이상 의미없다. 

Map으로 트라이를 만들기도 한다. 이 경우엔 O(mlog⁡n)의 시간이 소모된다.