[알고리즘] Suffix Tree

Suffix tree는 문자열의 모든 접미사들을 표현하는 trie 모양의 자료 구조이다.
prefix tree라 불리는 trie가 근간이 되는 자료구조인듯 한데 두 자료구조의 차이는 banana라는 단어가 있을 때 trie는 banana라는 단어만 저장을 하지만 suffix tree는 banana, anana, nana, ana, na, a 와 같이 banana라는 단어에서 나올 수 있는 모든 경우의 수를 다 저장한다는 것이다. 쓸데없이 모든 경우를 저장하는 이유는 문자열에 대한 검색을 할 때 필요하기 때문이다. Trie 자료구조 같은 경우에는 ban, ba와 같은 일부분의 단어로 banana라는 완전한 단어를 찾을 수 있지만 nan, ana와 같은 단어로는 banana를 찾을 수 없다. 이러한 문제를 해결하기위해 trie를 개선시킨 것이 suffix tree인듯 하다.

 Suffix trie는 trie에 모든 suffix들을 저장한 구조를 의미한다. 아래 그림은 abaaba라는 문자열 T를 suffix tree에 저장하는 예시이다. suffix tree나 suffix trie에 문자열을 저장할 때는 문자열의 끝에 $를 붙이는데 그 이유는 정확히 모르겠다... 아마 문자열의 끝을 알리기 위한 용도인 것 같다.

Suffix Trie의 형태

 위 그림의 왼쪽과 같은 모양이 suffix trie이다. 여기서 자식 노드가 1개 뿐인 것들을 합치면 오른쪽과 같은 모양이 되는데 저러한 형태의 자료구조를 suffix tree라 한다.

Suffix Tree

 이 suffix tree는 문자열의 길이만큼의 leaf node를 갖는다

 위 그림에서 오른쪽 그림은 tree의 edge label을 (offset, length)의 형태로 T를 나타낸 것이다.

Suffix tree의 label

 각 노드의 label은 root로부터 node로 연결된 edge의 label과 동일하다. 그리고 이것들은 명료하게 저장되어 있지는 않다.

 edge가 문자열 label을 가질 수 있기 때문에 두가지 의미의 'depth'에 대한 구분도 필요하다. 첫 번째는 노드 depth이다. 노드 depth는 root에서부터 노드까지 몇개의 edge를 통과해야 하는지에 대한 것이다. 두 번째는 Label depth이다. 이것은 root에서 노드까지의 경로에있는 edge에 대한 edge label의 총 길이를 의미한다.

음.. 정리를 하다보니 기반 지식의 부족함을 느껴 여기까지만하고 추가적인 공부후에 수정을 해야겠다..


--------------------------------------------------------------------
출처
https://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf
http://www.cs.jhu.edu/~langmea/resources/lecture_notes/suffix_trees.pdf