3.3 後綴陣列與後綴樹#

概念說明#

前兩節的索引把「樣式集合」組織起來，去比對一篇文字；本節反過來，把一篇文字本身建成索引，之後任意查詢字串都能快速回答「在哪裡出現、出現幾次」。這就是後綴結構：一個長度 n 的字串 s 共有 n 個後綴 s[i:]，把它們（連同結尾哨兵 $）全部寫下來並字典排序。

後綴陣列（suffix array）SA：記錄排序後各後綴的起始位置，即 SA[j] = 排第 j 名的後綴的起點。另可附帶 rank 陣列（rank[i] = 後綴 s[i:] 的名次）與 LCP 陣列（相鄰兩名後綴的最長共同前綴長度）。
後綴樹（suffix tree）：把 n 個後綴壓縮成一棵 trie（去除只有單一子節點的路徑，即 Radix Tree 化），葉子對應各後綴起點。空間 O(n)，任意子字串對應樹上一條路徑。

為什麼後綴索引這麼強？ 因為文字的任意子字串都是某個後綴的前綴。在後綴陣列上，所有以 p 為前綴的後綴在排序後是連續的一段區間，二分搜尋即可定位；在後綴樹上，p 對應唯一節點，子樹的葉子就是所有出現位置。

後綴樹的經典建構法 Ukkonen 演算法可線上性時間 O(n) 建樹，但實作繁複；後綴陣列有簡潔的 O(n log n) 倍增法與 O(n) 的 SA-IS 演算法。實務上後綴陣列因空間常數小、實作簡單而更常用，LCP 陣列補足了後綴樹的樹形資訊。應用包括：全文檢索、最長重複子字串、最長共同子字串（第4章）、生物序列比對、資料壓縮（LZ77 可用後綴結構加速）。

演算法步驟#

倍增法建後綴陣列（O(n log n)）：

初始：每個後綴以其第一個字元的排名為鍵排序。
第 t 輪：每個後綴以「前 2^(t-1) 個字元的排名、接下來 2^(t-1) 個字元的排名」組成二元組為鍵排序（第二次的排名查 rank[i + 2^(t-1)]）。
由二元組重新計算名次；若所有名次互異則提前結束。
重複直到長度 ≥ n。

查詢樣式 p（出現次數與位置）：

二分搜尋找下界：第一個「後綴 ≥ p」的位置 lo。
二分搜尋找上界：第一個「後綴 > 以 p 為前綴的範圍」的位置 hi。
SA[lo:hi] 即所有出現位置；hi − lo 為出現次數。

LCP 陣列（Kasai 演算法，O(n)）： 依 rank 順序從「原字串位置由大到小」計算 h[i]：h[i] ≥ h[i−1] − 1 的性質保證總工作量为 O(n)。

Python 程式碼範例#

def build_sa(s):
    """倍增法後綴陣列，O(n log n)"""
    n = len(s)
    rank = [ord(c) for c in s]
    sa = list(range(n))
    k = 1
    while True:
        key = lambda i: (rank[i], rank[i + k] if i + k < n else -1)
        sa.sort(key=key)
        new = [0] * n
        for j in range(1, n):
            new[sa[j]] = new[sa[j - 1]] + (key(sa[j]) != key(sa[j - 1]))
        rank = new
        if rank[sa[-1]] == n - 1:   # 名次全異，結束
            break
        k <<= 1
    return sa, rank

def build_lcp(s, sa, rank):
    """Kasai 演算法，O(n)"""
    n = len(s)
    h, lcp = 0, [0] * n
    for i in range(n):
        if rank[i] > 0:
            j = sa[rank[i] - 1]
            while i + h < n and j + h < n and s[i + h] == s[j + h]:
                h += 1
            lcp[rank[i]] = h
            if h: h -= 1
        else:
            h = 0
    return lcp

def count_positions(s, sa, p):
    """二分搜尋：p 在 s 的出現次數與位置"""
    n = len(s)
    lo, hi = 0, n
    while lo < hi:                      # 下界
        m = (lo + hi) // 2
        if s[sa[m]:] < p: lo = m + 1
        else: hi = m
    left, hi = lo, n
    while lo < hi:                      # 上界
        m = (lo + hi) // 2
        if s[sa[m]:sa[m] + len(p)] <= p: lo = m + 1
        else: hi = m
    return lo - left, sa[left:lo]

s = "banana"
sa, rank = build_sa(s)
print(sa)                    # [5, 3, 1, 0, 4, 2]  a, ana, anana, banana, na, nana
print(build_lcp(s, sa, rank))
print(count_positions(s, sa, "ana"))   # (2, [1, 3])

s2 = "演算法是處理文字的演算法"      # 中文同樣適用
sa2, _ = build_sa(s2)
print(count_positions(s2, sa2, "演算法"))

複雜度分析#

建構：倍增法 O(n log n)（每輪排序 O(n log n)、至多 log n 輪；改用基數排序可到 O(n log n) 內的更小常數）；SA-IS 為 O(n) 但實作複雜；後綴樹 Ukkonen 為 O(n)。
查詢長度 m 的樣式：後綴陣列二分搜尋 O(m log n)（配合 LCP 可到 O(m + log n)）；後綴樹 O(m + 出現數)。
空間：後綴陣列 O(n)（一個整數陣列）；後綴樹 O(n) 但常數大（每節點需子節點表）。
比較：查詢極多次且文字不變時，後綴結構遠優於每次重新比對；只查一兩次時，KMP/Boyer-Moore 反而划算。

練習#

用 build_sa 對 "mississippi" 建後綴陣列與 LCP，手動列出全部後綴驗證排序結果，並找出最長重複子字串（LCP 陣列的最大值對應的後綴前綴）。
實作「最長共同子字串」：把兩個字串 s₁#s₂ 拼接建後綴陣列，掃相鄰後綴（一個來自 s₁、一個來自 s₂）的 LCP 取最大值，此技巧將在第4章再次出現。
給定一篇 10 萬字的文章，先建後綴陣列，再支援 1000 次任意子字串查詢；與「每次查詢都用 str.find 全文掃描」比較總時間，說明索引在什麼查詢次數門檻之上才划算。