델파이로 만드는 검색엔진

트라이(trie)는 탐색과 정렬이 가능하고 key로 시작하는 단어 검색과 같은 like 연산도
가능하기 때문에 문자열 검색에 아주 훌륭한 자료구조이다.
그런데 트라이의 가장 큰 단점은 문자 집합만큼  노드를 가져야 한다는 것이다.
예를들어 영문자 같은 경우 노드가 'a'..'z'에 해당하는 26개의 노드를 가진다는 것이다.
이정도까지는 어느 정도 감당할 수 있겠지만 한글이나 유니코드가 나오면 어쩔 방법이 없다.
유니코드인 경우 문자집합이 65000이 넘어가니 공간 문제 때문에 트라이를 사용할 수가 없다.
대안으로 노드를 해시를 이용하면 해결이 가능하겠지만, 그러면 해시의 특성상 정렬 기능을
사용할 수 없기 때문에 반쪽짜리 트라이가 될 것이다.

이런 문제를 해결할 수 있는 것이 삼진 검색 트라이(Ternary Search Trie - TST)이다.
TST는 문자 집합만큼 노드를 가지는 것이 아니라 딱 세개의 노드만 가진다. 키값보다 작은
노드, 키값과 같은 노드, 키값보다 큰 노드 이렇게 새개의 노드만 가지기 때문에 유니코드와
같이 문자집합이 아무리 커져도 상관없이 트라이를 구성할 수 있다.

TST의 단점으로는 생성에 시간이 좀 더 걸린다는 것과 이진 탐색에 비해 공간을 더 차지한다는
거 정도인데 이는 장점에 비해서는 별 문제가 되지는 않을 거라 생각한다.
따라서 TST는 검색엔진에서 아주 쓸만한 자료구조인 것 같다.
TST에 대한 자료는 http://www.geocities.jp/m_hiroi/light/pyalgo10.html에 잘 설명이 되어 있다.
또는 Algoruthms in C(로버트 세지윅 지음)에 자세히 설명되어 있다.

해시는 대부분의 언어에서 지원하기 때문에 그동안 검색에 해시를 많이 사용했는데 앞으로 TST를 애용할 것 같다.