1973-後綴樹#

案件摘要#

1973 年，Peter Weiner 在 FOCS（當年稱 SWAT）會議上發表《Linear Pattern Matching Algorithms》，提出後綴樹（suffix tree）——一個為字串建「一次索引、查任意次」的資料結構。三年後 McCreight 把建構過程的空間問題解掉，1995 年 Ukkonen 再推出能「邊讀邊建」的線上演算法。此案偵辦的謎題是：當 KMP 與 Boyer-Moore 已把單次匹配壓到線性時間，為什麼還需要後綴樹？答案在於另一種犯罪型態——同一份長文字上要反覆查詢任意模式。

前因 -- 為什麼會有這個案子#

KMP（1977）與 Boyer-Moore（1977）把單次字串匹配做到 O(n + m)，但每次查詢仍要重新掃描整份文本 O(n)；查一萬個模式就是一萬次全掃。
生物序列分析的早期需求：DNA 是長達數百萬字元的字串，研究人員需要對同一份基因組反覆查詢不同模式、找重複片段、比較兩條序列。
Weiner 的構想：預先把文本的所有後綴組織成一個索引結構，之後任何查詢都只與模式長度 m 有關，與文本長度 n 無關。
1970 年代初的 trie 與 Patricia tree 理論已成熟，問題是如何把「所有後綴」塞進線性空間——naive 後綴 trie 是 O(n²) 個節點。

線索與推理 -- 數學式、程式、理論#

線索一：後綴樹是壓縮的後綴 trie#

字串 $T = t_1 t_2 \cdots t_n$ 的所有後綴為 $T_i = t_i t_{i+1} \cdots t_n \

$$ （加終止符 $ 防止前綴歧義）。把這 n 條後綴插入 trie，再壓縮所有「單子鏈」，就得到後綴樹——本質是一棵 Patricia tree。Weiner 證明：壓縮後的後綴樹節點數是 O(n)，因此可以線性空間儲存。他的建構自底向上、從最長後綴開始，需要輔助的「指示表」，時間 O(n) 但實作繁瑣且空間常數大。

線索二：McCreight 的空間改進與 Ukkonen 的線上建構#

McCreight（1976）發現在建構過程中，剛插入的後綴的「活動位置」與下一個後綴之間存在一條捷徑——後綴連結（suffix link）： $$

\text{若節點 } v \text{ 對應字串 } a w \text{，則其後綴連結指向對應 } w \text{ 的節點}

\[ 沿著這條捷徑，每一步的插入可攤還常數時間，總時間 O(n)，記憶體只需 Weiner 方案的一小部分。Ukkonen（1995）再把建構改成「線上」：逐字元讀入文本，每讀一個字元就更新部分後綴樹，全程維護有效後綴與活動點（active point），同樣攤還 O(n)。三人的破案時刻構成一條 22 年的破案鏈： \]

\text{Weiner 1973（O(n), 繁瑣）} \to \text{McCreight 1976（O(n), 省空間）} \to \text{Ukkonen 1995（O(n), 線上）} $$

線索三：應用的數學——查詢只看 m#

後綴樹建好後，任一模式 $P$ （長度 m）的出現位置查詢是：從根沿 P 下行，若走到某節點或邊中段，則 P 是某後綴的前綴，其出現次數等於該子樹的葉數。查詢時間 O(m)（不含輸出），與 n 無關——這正是「預處理-多查詢」範式的精髓。其他經典應用：

最長重複子字串：最深（字串深度最大）的內部節點，對應字串即所求，O(n)。
最長共同子字串（LCS）：把兩串 $S_1 \# S_2$ 合併建一棵後綴樹，找同時有兩色葉子的最深內部節點。
生物序列比對：後綴樹支援近似匹配與多重序列查詢，是 BLAST 等工具的思想祖先。
空間 O(n) 但常數高達 10-20 倍，實務上被 Manber-Myers（1990）的後綴陣列取代：排序 n 條後綴、存 n 個整數，空間省約 20 倍，配合 LCP 陣列能重現後綴樹的大部分功能。

程式佐證：Python 可執行示範#

def suffix_array_naive(s):
    return sorted(range(len(s)), key=lambda i: s[i:])

def longest_repeated_substring(s):
    sa = suffix_array_naive(s)
    best, best_len = "", 0
    for a, b in zip(sa, sa[1:]):
        i = 0
        while i < min(len(s) - a, len(s) - b) and s[a + i] == s[b + i]:
            i += 1
        if i > best_len:
            best_len, best = i, s[a:a + i]
    return best

def count_pattern(s, pattern):
    sa = suffix_array_naive(s)
    lo = 0
    hi = len(sa)
    while lo < hi:
        mid = (lo + hi) // 2
        if s[sa[mid]:sa[mid] + len(pattern)] < pattern:
            lo = mid + 1
        else:
            hi = mid
    start = lo
    hi = len(sa)
    while lo < hi:
        mid = (lo + hi) // 2
        if s[sa[mid]:sa[mid] + len(pattern)] <= pattern:
            lo = mid + 1
        else:
            hi = mid
    return lo - start

text = "banana_mississippi_bandana"
print("後綴陣列:", suffix_array_naive(text))
print("最長重複子字串:", longest_repeated_substring(text))
print("模式 'ana' 出現次數:", count_pattern(text, "ana"))

執行結果：最長重複子字串: ana、模式 'ana' 出現次數: 4——排序後綴後，相鄰後綴的最長共同前綴立即暴露重複片段；二元搜尋讓任意模式的查詢只需 O(m log n)，正是後綴樹 O(m) 查詢的簡化影子。

結案 -- 後果與影響#

後綴樹成為生物資訊學的基石：DNA 比對、基因組重複序列分析、BLAST 等工具的思想祖先。
後綴陣列（Manber-Myers 1990）成為實務標準，空間比後綴樹省約 20 倍，廣用於搜尋引擎與壓縮工具。
「預處理一次、查詢任意次」成為字串演算法的核心範式，衍生壓縮後綴陣列（FM-index，2000）等成果。
後綴樹是 LZ77 壓縮演算法字典結構的高效實作，連接了壓縮與索引兩個領域。
Ukkonen 的線上建構啟發了「流式演算法」思想：資料未到齊也能維護有效結構。

關鍵人物與文獻#

Peter Weiner, "Linear Pattern Matching Algorithms", Proceedings of the 14th Annual Symposium on Switching and Automata Theory (SWAT/FOCS), 1973, pp. 1-11.
Edward M. McCreight, "A Space-Economical Suffix Tree Construction Algorithm", Journal of the ACM, 23(2): 262-272, 1976.
Esko Ukkonen, "On-line Construction of Suffix Trees", Algorithmica, 14(3): 249-260, 1995.
Udi Manber and Gene Myers, "Suffix Arrays: A New Method for On-Line String Searches", SODA 1990, pp. 319-327.
Donald E. Knuth, James H. Morris, Jr., and Vaughan R. Pratt, "Fast Pattern Matching in Strings", SIAM Journal on Computing, 6(2): 323-350, 1977.
Paolo Ferragina and Giovanni Manzini, "Opportunistic Data Structures with Applications", FOCS 2000, pp. 390-390.
Dan Gusfield, Algorithms on Strings, Trees, and Sequences, Cambridge University Press, 1997.