Tree Structure 노트10 - Suffix Tree

Search Tree 구성의 종류 

- key 전체를 비교하는 방법 / key의 일부를 비교하는 방법 / 각 node마다 동일한 기준으로 비교하는 방법 / 각 node마다 비교하는 기준이 다른 경우

 

Trie 구조가 필요한 Text Application의 전형적인 예)

- Dictionary : memory를 작게 만드는 것이 중요한 작업

- 자동차 네비게이션에서 주소 찾기 or 우편번호 주소 찾기

 

Digital Search Tree

- key 값을 binary로 바꿔서 각 level마다 비교대상을 다르게 함.

- level i node에서 볼때 왼쪽 subtree의 모든 값은 i번쨰 bit = 0, 오른쪽 subtree의 i번째 bit = 1

 

Trie는 기본적으로 multi-way branch tree. -> k-ary tree / 각 level i의 노드에서는 i번째 information [i]에 따라서 branch를 한다. 따라서 길이 k인 string의 경우 탐색을 k번 해야 함. 데이터의 갯수에 dependent 하지 않음. 이것은 중요한 사실. BST는 O(logN) / 이 구조를 보다 효율적으로 개선하면 single path를 압축(compress)하여 하나의 노드로 만든다. -> compressed trie. 비교 횟수는 각 char 별로 한다면 큰 차이는 없지만 자료구조의 크기를 줄일 수 있다.

 

Suffix Trie

- edge가 문자를 가진 문자열 모음의 그래프를 Trie라고 함.

- Suffix Trie는 Suffix Tree의 일반화된 개념이며, 문자열을 저장하기 위한 트리이다.

- Trie Construction : O(|patterns|)

- 패턴 매칭 : O(|Text| * |LongestPattern|)

 

Suffix Tree

- suffix tree는 주어진 텍스트의 모든 접미사(suffix)를 포함하는 압축된 trie이다.

- suffix tree를 사용하는 이유는 찾고자 하는 패턴이 문자열에 존재하는지 찾기위해서 사용되는데, 만약 찾고자 하는 패턴이 문자열에 존재한다면 해당 패턴은 문자열의 중간에 나오는 각각의 suffix의 prefix가 되기 떄문에 사용.

- S라는 string이 주어질 때 부분 문자열 패턴(substring pattern)이 있는지, 패턴이 S의 접미사(suffix)의 prefix로 존재하는지 탐색.

- root node를 제외한 각각의 internal node는 적어도 두개 이상의 children node를 갖고 있다.

- 어떤 두 edge에서 나오는 같은 문자열을 가지는 edge-labels를 갖고 있지 않다. edge에는 suffix의 위치 정보와 길이 정보를 가지고 있다.

- suffix tree의 탐색 > 각 노드의 offset을 보고하면 해당 서브 문자열이 당연히 존재하는지 알 수 있고, 어느 위치에 있는지까지 알 수 있다.

 

Reference string T에 대해서 어떤 string w가 포함되어 있는지 검사

F(T, w) = { Yes, No }

- 일반적인 방법 (2개의 for loop) > 최악의 경우 O(N*M(문자열길이))

- 혁신적인 방법 Suffix Tree : 어떤 문자열의 suffix는 substring의 집합 = { T[i:n] : 0 <= i <= n }

 

Suffix Tree : naive algorithm

- Label이 S(i+1, n)의 접두사와 일치하는 루트에서 가장 긴 경로 찾기

- 새 내부 노드를 만들기위해 edge 중간에서 불일치(mismatch)를 찾는 경우 split edge.