[머신러닝] 접미사 트라이(Suffix trie), 접미사 트리(Suffix tree) ,나이브 베이즈(Naive Bayes)- 컴도리돌이

반응형

---

Suffix trie

Suffix tree

Definition

Construction with Naive algorithm

---

접미사 트라이(Suffix trie)

• edge가 문자를 가진 문자열 모음을 가진 그래프를 트라이(trie)라고 한다.
• 접미사 트라이(Suffix trie)는 접미사 트리(Suffix Tree)의 일반화된 개념이며, 문자열을 저장하기 위한 트리이다.
• 트라이 구축(trie Construction): O(|patterns|)
• 패턴 매칭 : O(|Text| * |LongestPattern|)
• text T(abaaba)의 모든 접미사(루트에서 리프까지)를 포함하는 트리로 예를 들어보자.

해당 그래프만 보고서는 접미사가 무엇인지 정확하게 알 수가 없다.

문자열의 끝을 나타내는 터미널 기호 추가

루트에서 노드로 가는 경로에 터미널 기호를 확인하여 하위 문자열을 가지고 있는 것을 확인해줄 수 있다.

---

접미사 트리(Suffix tree)

• 접미사 트리(suffix tree)는 주어진 텍스트의 모든 접미사를 포함하는 압축된 "trie"이다.
• 접미사 트리를 사용하는 이유는 찾고자 하는 패턴이 문자열에 존재하는지 찾기 위해서 사용되는데, 만약 찾고자 하는 패턴이 문자열에 존재를 한다면 해당 패턴은 문자열에 중간에 나오는 각각의 suffix의 prefix가 되기 때문에 접미사 트리를 사용한다.
• S라는 string이 주어질 때 부분 문자열 패턴(substring pattern)이 있는지, 패턴이 S의 접미사(suffix)의 prefix로 존재하는지 탐색한다.
• 루트 노드(root node)를 제외한 각각의 인터널 노드(internal node)는 적어도 두 개 이상의 자식 노드(children node)를 갖고 있다.
• 어떤 두 edge에서 나오는 같은 문자열을 가지는 edge-labels을 갖고 있지 않다. edge에는 suffix의 위치 정보와 길이 정보를 가지고 있다.

 

지점이 없는 경로를 문자열 lable과 함께 단일 edge로 결합

edge lable을 한 쌍(offset, length)으로 변환

$에 어디서 시작했는지 leaf에 offset 값을 저장한다.

접미사 트리 : 탐색(suffix tree : searching)

모든 리프 노드 아래로 방문하고 각 노드의 offset을 보고한다.

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

---

접미사 트리 : 나이브 알고리즘(Suffix tree : naive algorithm)

• 레이블이 S(i+1, n)$의 접두사와 일치하는 루트에서 가장 긴 경로 찾기
• 새 내부 노드를 만들기 위해 edge 중간에서 불일치(mismatch)를 찾는 경우 분할 에지(split dege)

 

• N1에서 주어진 문자열에 대한 노드를 생성한다. 다음 suffix를 보니 N1과 다르기 때문에 새로운 suffix에 대한 노드를 생성한다.(N2)

• N4에서 suffix가 "xa"인데 해당 문자열은 N1 노드의 시작 문자열과 같이 때문에 N1 노드에 하나의 edge를 만들어준다.

---