접미사 트라이(Suffix Trie)

본 문서는 다음 내용을 편역 하였다.

Suffix array - a contest approach - CS 97SI(http://www.google.co.kr/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&ved=0CCoQFjAA&url=http%3A%2F%2Fcs97si.stanford.edu%2Fsuffix-array.pdf&ei=69ytUIj-DMbvsga-7oH4Dg&usg=AFQjCNHjS8jTxKaXGR8cgK7bedDyIzDCpg&sig2=j7FsJb7lmcZ6bLFY9o_zkw)

소개

트라이(trie)는 접미사 트리(Suffix Tree)의 일반화된 개념이다. 트라이는 문자열을 저장하기 위한 트리이다. 트라이의 각 노드는 주어진 문자열에서 사용된 문자의 개수와 같은 수의 자식 노드를 가진다. 즉, 영어 문자로 이뤄진 문자열을 저장하기 위해서 각 노드는 최대 26개의 자식 노들을 가질 것이다. 루트 노드에서 시작하여 리프 노드에 이르는 동안 에지에 저장된 표지를 연결하면 부분 문자열을 얻을 수 있다. 트라이를 통해 문자열을 찾는 것은 시간에 수행된다. 여기에서 n은 문자열의 길이이다. 그런 까닭에, 검색 시간은 트라이에 저장된 문자의 갯수에 의존하지 않고, 트라이가 검색에 효율적인 자료 구조가 되게 한다.

무엇이 접미사 트라이인지 알아 보자.

주어진 문자열 은 i번째 위치에서 시작하는 A의 접미사인 으로 표현될 수 있다. 그리고 이 때 n은 A의 길이이다. 접미사 트라이는 아래 그림에 보이듯이  A의 모든 접미사인 를 하나의 트라이로 압축함으로써 생성할 수 있다.

문자열 "abac"에 대응되는 접미사 트라이는 다음과 같다.

접미사 트라이에 대한 연산은 매우 쉽게 수행된다.

• 문자열 W가 문자열 A의 부분 문자열인지 확인하는 연산: 루트 노드에서 시작하여 W에 있는 문자들에 대응되는 표지를 가진 에지를 따라 순회하는 것으로 충분하다.(복잡도, n은 W의 길이)
• A의 두 접미사에 대한 가장 긴 접두사(LCP, Longest Common Prefix) 찾기 연산: 트라이에서 각각 두 접미사의 끝에 대응하는 u와 v의 노드를 선택하고, 최소 공통 조상(LCA, Least Common Ancestor) 알고리즘을 이용하여, 검색된 접두사의 끝에 대응하는 노드를 찾는다. 예를 들어, 위의 그림에서 abac와 ac는 각각 노드 5와 6에 대응된다. 그들의 최소 공통 조상(LCA)은 노드 2이고, 이것은 접미사가 a임을 알려준다.
• 사전식 순서에 따른 k 번째 접미사 찾기 연산: 적절한 전처리로 복잡도를 얻을 수 있다. 예를 들어, 위의 그림은 abac에 대한 트라이이고 abac의 사전식 순서에서 3 번째 접미사는 3번째 리프 노드(bac)로 표현되어 있다. 참고적으로 1번째 접미사는 abac, 2번째 접미사는 ac, 4번째는 c이다.

접미사 트라이의 아이디어가 처음에는 매우 좋게 느껴지지만, 단순히 주어진 문자열의 모든 접미사들을 트라이에 입력하는 것은 복잡도 알고리즘을 야기한다. 이런 경우 Ukkonen 씨의 알고리즘(http://juggernaut.tistory.com/entry/Ukkonens-Online-construction-of-suffix-tree-%ED%95%9C%EA%B5%AD%EC%96%B4-%EB%B2%88%EC%97%AD)을 이용하여 선형 시간에 접미사 트리를 생성할 수도 있다. 접미사 트리는 바깥으로 나가는 에지가 하나 밖에 없는 경우 단일 에지로 압축된 노드만을 연결한 접미사 트라이의 일종이다. 위의 그림에서, 접미사 트리는 2-3-4-5와 1-7-8-9의 연결로 표현된다.

A 문자열의 접미사가 무엇인지 트라이에 대한 깊이 우선 탐색(DFT, Depth first Traversal)을 통해 살펴보자. 깊이우선 탐색을 하는 동안 우리는 현재 노드를 부모 노드로 연결하는 에지를 사전식 정렬에서 오름차순(a, b, c 순)으로 따라가도록 한다. 우리는 다음의 접미사 배열을 얻을 수 있다.

접미사들이 오름차순으로 정렬된 것을 알 수 있다. 그것들을 저장하기 위해서 모든 문자열 목록을 저장할 필요는 없고, 단지 정렬된 배열에 있는 모든 접미사의 위치만 저장하는 것만으로도 충분하다. 위의 예제의 경우 우리는 P=(0,2,1,3)의 배열을 얻게 되고, 이것은 문자열 abac의 접미사 배열이 된다.