suffix-tree教程（個人總結）

背景

在計算機科學和生物信息學中，字符串處理是一個非常重要的領域。無論是搜索引擎、基因序列分析，還是壓縮算法，都離不開高效的字符串處理。傳統的字符串匹配算法，如暴力搜索、Knuth-Morris-Pratt (KMP) 算法和 Boyer-Moore 算法，雖然在特定場景下表現優異，但在處理大規模數據時常顯得捉襟見肘。后綴樹作為一種高級數據結構，以其高效的構建和查詢性能，成為處理復雜字符串問題的利器。

什么是后綴樹？

后綴樹是一種特殊的樹結構，用于表示一個字符串的所有后綴。給定一個長度為 n 的字符串 S，其后綴樹是一個有根的有向樹，包含 n 個葉子節點，每個葉子節點對應 S 的一個后綴。每個內部節點（除根節點外）至少有兩個孩子節點，每條邊都標記有 S 的一個非空子串。同一節點的兩條邊所標記的子串不能以相同的字符開頭。后綴樹的關鍵屬性是，從根到葉子的路徑所連接的邊標記拼接起來正好是 S 的一個后綴。

優勢與劣勢

優勢

快速構建：使用 Ukkonen 算法，后綴樹可以在 O(n) 時間內構建。
高效查詢：后綴樹允許在 O(m) 時間內進行子串搜索，其中 m 是查詢子串的長度。
豐富的應用：后綴樹在子串搜索、模式匹配、最長重復子串和最長公共子串等問題上表現出色。
空間優化：雖然后綴樹的空間復雜度為 O(n)，但通過后綴數組等優化手段，可以進一步降低空間消耗。

劣勢

空間消耗較大：在最壞情況下，后綴樹的空間復雜度為O(n2)，實際應用中通常為 O(n)。
實現復雜：Ukkonen 算法的實現較為復雜，對初學者有一定難度。
特定場景適用：后綴樹主要用于字符串處理問題，對于其他類型的數據處理，可能不如其他數據結構高效。

后綴樹的構建

后綴樹的構建可以通過 Ukkonen 算法在 O(n) 時間內完成。以下是構建后綴樹的詳細步驟：

初始化

從一個僅包含根節點的空樹開始。初始化活動點（active point），包括活動節點（active node）、活動邊（active edge）和活動長度（active length）。

逐字符插入

對字符串中的每個字符，將對應的后綴插入到樹中。每次插入新字符時，更新活動點并應用適當的擴展規則：

擴展規則 1：在活動點后插入一個新的邊。
擴展規則 2：在活動點后擴展現有的邊。
擴展規則 3：創建一個新的內部節點，并分裂現有的邊。

活動點更新

根據擴展后的新狀態，更新活動點的位置和狀態。如果活動點在根節點且活動長度大于0，則將活動長度減1，并將活動邊向前移動一位。如果活動點不是根節點，則將活動點移動到其后綴鏈接。

示例

以下是構建字符串 BANANA 的后綴樹的詳細過程：

初始化：從一個僅包含根節點的空樹開始。

插入后綴：

插入 A:

Root└── A

插入 NA:

Root└── A└── NA

插入 ANA:

Root└── A└── NA└── N└── A

插入 NANA:

Root└── A└── NA└── N└── A└── NA

插入 ANANA:

Root└── A└── N└── ANA└── N└── A└── NA

插入 BANANA:

Root└── A└── N└── ANA└── B└── ANANA└── N└── A└── NA

Ukkonen 算法

Ukkonen 算法是一個在線算法，通過逐步擴展后綴樹來處理字符串中的每個字符。該算法的核心思想是維護一個活動點，通過該活動點跟蹤當前正在處理的后綴。每次插入新字符時，算法根據當前活動點的位置和狀態選擇適當的規則進行處理。

詳細步驟

初始化：創建一個根節點，并將活動點設置為根節點。
逐字符擴展：對字符串中的每個字符，執行以下步驟：
- 擴展規則：根據當前活動點的位置和狀態選擇適當的擴展規則：
  - 規則 1：在活動點后插入一個新的邊。
  - 規則 2：在活動點后擴展現有的邊。
  - 規則 3：創建一個新的內部節點，并分裂現有的邊。
- 活動點更新：根據擴展后的新狀態，更新活動點的位置和狀態。

示例代碼

以下是 Ukkonen 算法的 Python 實現：

class SuffixTreeNode:def __init__(self):self.children = {}self.suffix_link = Noneself.start = Noneself.end = Noneclass SuffixTree:def __init__(self, text):self.text = textself.root = SuffixTreeNode()self.build_suffix_tree()def build_suffix_tree(self):n = len(self.text)self.root.end = -1self.root.suffix_link = self.rootactive_node = self.rootactive_edge = -1active_length = 0remainder = 0for i in range(n):last_new_node = Noneremainder += 1while remainder > 0:if active_length == 0:active_edge = iif self.text[active_edge] not in active_node.children:leaf = SuffixTreeNode()leaf.start = ileaf.end = nactive_node.children[self.text[active_edge]] = leafif last_new_node:last_new_node.suffix_link = active_nodelast_new_node = Noneelse:next_node = active_node.children[self.text[active_edge]]edge_length = next_node.end - next_node.startif active_length >= edge_length:active_edge += edge_lengthactive_length -= edge_lengthactive_node = next_nodecontinueif self.text[next_node.start + active_length] == self.text[i]:if last_new_node:last_new_node.suffix_link = active_nodeactive_length += 1breaksplit = SuffixTreeNode()split.start = next_node.startsplit.end = next_node.start + active_lengthactive_node.children[self.text[active_edge]] = splitleaf = SuffixTreeNode()leaf.start = ileaf.end = nsplit.children[self.text[i]] = leafnext_node.start += active_lengthsplit.children[self.text[next_node.start]] = next_nodeif last_new_node:last_new_node.suffix_link = splitlast_new_node = splitremainder -= 1if active_node == self.root and active_length > 0:active_length -= 1active_edge = i - remainder + 1elif active_node != self.root:active_node = active_node.suffix_linkdef traverse_tree(self, node, suffixes, current_suffix):if not node.children:suffixes.append(current_suffix)returnfor char, child in node.children.items():self.traverse_tree(child, suffixes, current_suffix + self.text[child.start:child.end])def get_suffixes(self):suffixes = []self.traverse_tree(self.root, suffixes, "")return suffixestext = "BANANA"
st = SuffixTree(text)
suffixes = st.get_suffixes()
print(suffixes)

后綴樹的優化

雖然后綴樹具有許多優點，但其空間復雜度可能較高。為了優化空間，可以考慮以下幾種方法：

后綴數組：后綴數組是一種空間更為緊湊的數據結構，可以用來替代后綴樹。在某些應用中，后綴數組能夠提供類似的功能，并具有更低的空間開銷。
增強后綴數組：增強后綴數組結合了后綴數組和后綴樹的優點，提供了一種高效且空間優化的解決方案。
節點壓縮：通過合并后綴樹中的某些節點，減少節點數量，從而降低空間復雜度。

后綴數組

后綴數組是一個存儲字符串所有后綴的數組，每個后綴按字典順序排序。構建后綴數組的時間復雜度為O(nlogn)，并且通過使用 Kasai 等人的算法，可以在 O(n) 時間內構建出后綴數組的高度數組（LCP 數組）。

示例代碼

以下是構建后綴數組的 Python 實現：

def build_suffix_array(text):n = len(text)suffixes = sorted([text[i:] for i in range(n)])suffix_array = [n - len(suffix) for suffix in suffixes]return suffix_arraytext = "BANANA"
suffix_array = build_suffix_array(text)
print(suffix_array)