Suffix Tree

Suffix Tree는 주어진 문자열의 모든 접미사(suffix)를 압축된 트라이(trie) 형태로 표현한 트리 구조로, 각 간선은 문자열의 부분 문자열을 나타내며, 리프 노드는 접미사의 시작 위치를 나타낸다.

https://www.geeksforgeeks.org/pattern-searching-using-suffix-tree/

특징

  1. 모든 접미사를 트리 형태로 표현한다.
  2. 공통 접두사를 공유하여 압축된 형태로 저장한다.
  3. 트리의 높이는 항상 O(n)을 유지한다.

장점

  1. 패턴 매칭, 최장 공통 부분 문자열 찾기 등의 연산을 효율적으로 수행한다.
  2. 검색 시간이 O(m)으로 매우 빠릅니다(m은 찾는 패턴의 길이).
  3. 다양한 문자열 관련 문제를 해결하는 데 활용될 수 있다.

단점

  1. 구현이 복잡하고 메모리 사용량이 많다.
  2. 구축 비용이 높다.

응용

  1. 문자열 검색 및 패턴 매칭
  2. DNA 시퀀싱 및 생물정보학 분석
  3. 데이터 압축 알고리즘
  4. 텍스트 인덱싱 및 전체 텍스트 검색

동작 원리

  1. 문자열의 모든 접미사를 트리에 삽입한다.
  2. 공통 접두사를 공유하는 노드를 압축한다.
  3. 각 리프 노드에 접미사의 시작 위치를 저장한다.

구성 요소

  1. 루트 노드: 트리의 시작점
  2. 내부 노드: 공통 접두사를 나타내는 노드
  3. 리프 노드: 접미사의 끝을 나타내는 노드
  4. 간선: 노드 사이를 연결하며 부분 문자열을 나타냄

구현 방식

Suffix Tree는 일반적으로 Ukkonen’s 알고리즘을 사용하여 선형 시간에 구축할 수 있다.

주요 연산들의 동작 과정

  1. 구축: Ukkonen’s 알고리즘을 사용하여 O(n) 시간에 트리를 구축한다.
  2. 검색: 루트에서 시작하여 패턴을 따라 트리를 탐색합니다. O(m) 시간 복잡도를 가진다.
  3. 최장 공통 부분 문자열 찾기: 가장 깊은 내부 노드를 찾는다.

예시 코드

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91

class Node:
    def __init__(self):
        self.children = {}
        self.suffix_link = None
        self.start = -1
        self.end = -1
        self.suffix_index = -1

class SuffixTree:
    def __init__(self, text):
        self.text = text
        self.root = Node()
        self.active_node = self.root
        self.active_edge = -1
        self.active_length = 0
        self.remaining_suffixes = 0
        self.leaf_end = -1
        self.node_count = 0
        self.build_tree()

    def build_tree(self):
        for i in range(len(self.text)):
            self.extend(i)

    def extend(self, pos):
        self.leaf_end = pos
        self.remaining_suffixes += 1
        last_new_node = None

        while self.remaining_suffixes > 0:
            if self.active_length == 0:
                self.active_edge = pos

            if self.active_edge not in self.active_node.children:
                self.active_node.children[self.active_edge] = Node()
                self.active_node.children[self.active_edge].start = pos
                self.active_node.children[self.active_edge].end = self.leaf_end
                self.active_node.children[self.active_edge].suffix_index = pos - self.remaining_suffixes + 1
                self.node_count += 1

                if last_new_node is not None:
                    last_new_node.suffix_link = self.active_node
                    last_new_node = None

                self.remaining_suffixes -= 1
            else:
                next_node = self.active_node.children[self.active_edge]
                if self.walk_down(next_node):
                    continue

                if self.text[next_node.start + self.active_length] == self.text[pos]:
                    self.active_length += 1
                    if last_new_node is not None:
                        last_new_node.suffix_link = self.active_node
                    break

                split_node = Node()
                split_node.start = next_node.start
                split_node.end = next_node.start + self.active_length - 1
                self.active_node.children[self.active_edge] = split_node
                split_node.children[self.text[pos]] = Node()
                split_node.children[self.text[pos]].start = pos
                split_node.children[self.text[pos]].end = self.leaf_end
                split_node.children[self.text[pos]].suffix_index = pos - self.remaining_suffixes + 1
                next_node.start += self.active_length
                split_node.children[self.text[next_node.start]] = next_node
                self.node_count += 2

                if last_new_node is not None:
                    last_new_node.suffix_link = split_node
                last_new_node = split_node

                self.remaining_suffixes -= 1

            if self.active_node == self.root and self.active_length > 0:
                self.active_length -= 1
                self.active_edge = pos - self.remaining_suffixes + 1
            elif self.active_node != self.root:
                self.active_node = self.active_node.suffix_link

    def walk_down(self, node):
        if self.active_length >= node.end - node.start + 1:
            self.active_edge += node.end - node.start + 1
            self.active_length -= node.end - node.start + 1
            self.active_node = node
            return True
        return False

# 사용 예
text = "banana$"
suffix_tree = SuffixTree(text)

참고 및 출처