3.2 Aho-Corasick演算法#

概念說明#

Aho-Corasick 演算法（1975 年由 Alfred Aho 與 Margaret Corasick 提出）解決的問題是：給定一個樣式集合 {p₁, p₂, …, pₖ}，在一篇長度 n 的文字中，一次掃描找出所有樣式的所有出現位置。若用 KMP 對每個樣式逐一比對，總時間是 O(n + |p₁| + … + |pₖ|) 乘以樣式數 k；Aho-Corasick 則達到 O(n + M + z)，其中 M 是樣式總長度、z 是匹配總數——這是理論上的最佳線性時間。

演算法分兩階段：

建構階段：把所有樣式插入 Trie（前一節的資料結構），再加上失敗連結（failure link）。節點 u 的失敗連結指向「樹上最長的真後綴，且該後綴也是樹上某個樣式的前綴」的節點。這正是 KMP 的失敗函數從「單鏈」推廣到「樹」的版本：在 KMP 中比對失敗要退回模式串較短的前綴，在 AC 自動機中比對失敗要退回 Trie 上最長的、可繼續匹配的後綴節點。
掃描階段：狀態從根出發，讀入文字的每個字元 c：若當前節點有 c 邊就走過去；否則沿失敗連結跳，直到有 c 邊或到達根。每到一個狀態，就沿失敗連結往回檢查所有「以當前位置結尾」的樣式（輸出連結可加速此步）。

失敗連結可用廣度優先搜尋（BFS）由淺至深計算：節點 v（其父經字元 c 到 v）的失敗連結，等於「parent 的失敗連結沿 c 走一步；若無 c 邊則再跳失敗連結，直到找到或到根」。這遞迴定義保證 BFS 順序下每個節點的失敗連結只依賴更淺的節點。

輸出連結（output link / suffix link）是進一步的優化：每個節點指向「失敗連結鏈上最近一個是樣式結尾的節點」。掃描時沿輸出連結走即可枚舉所有匹配，不必每步都走整條失敗鏈。

應用面極廣：敏感詞過濾（第10章實戰）、病毒碼掃描、生物序列多重樣式搜尋、入侵偵測系統的特徵匹配，都是 AC 自動機的標準用途。

演算法步驟#

建 Trie：把 k 個樣式依 3.1 節方法插入，樣式末端節點標記 output。
BFS 建失敗連結：根的失敗連結指向自己（或 None）；根的每個子節點失敗連結指向根。佇列中依序取出節點 u，對 u 的每個 (c, v)：沿 u.fail 找有 c 邊的最近祖先節點 w，令 v.fail = w.children[c]（若 w 為根且根無 c 邊則 v.fail = 根）；並合併輸出：v.output |= v.fail.output（用輸出連結時改為 v.out_link）。
掃描文字：state = 根；對每個字元 c：while state 無 c 邊且 state ≠ 根：state = state.fail；若有 c 邊則 state = state.children[c]；從 state 沿輸出連結枚舉所有以「當前位置」結尾的樣式並記錄位置。
（可選）掃描完成後，把失敗連結預先「壓平」成確定有限自動機（DFA）：每個狀態預先算好每個字元的轉移，掃描時不再需要 while 迴圈，但空間變成 O(狀態數 × |Σ|)。

Python 程式碼範例#

from collections import deque

class AhoCorasick:
    def __init__(self):
        self.next = [{}]      # next[state][char] -> state
        self.fail = [0]       # 失敗連結
        self.out = [[]]       # 每個狀態以它結尾的樣式編號
        self.words = []       # 樣式清單

    def add(self, word):
        s = 0
        for ch in word:
            if ch not in self.next[s]:
                self.next.append({})
                self.fail.append(0)
                self.out.append([])
                self.next[s][ch] = len(self.next) - 1
            s = self.next[s][ch]
        if word not in self.words:
            self.words.append(word)
            self.out[s].append(word)

    def build(self):
        q = deque()
        for ch, v in self.next[0].items():
            self.fail[v] = 0
            q.append(v)
        while q:
            u = q.popleft()
            for ch, v in self.next[u].items():
                f = self.fail[u]
                while f and ch not in self.next[f]:
                    f = self.fail[f]
                self.fail[v] = self.next[f][ch] if ch in self.next[f] and self.next[f][ch] != v else 0
                self.out[v] = self.out[v] + self.out[self.fail[v]]
                q.append(v)

    def search(self, text):
        s, hits = 0, []
        for i, ch in enumerate(text):
            while s and ch not in self.next[s]:
                s = self.fail[s]
            s = self.next[s].get(ch, 0)
            for w in self.out[s]:
                hits.append((i - len(w) + 1, w))
        return hits

ac = AhoCorasick()
for w in ["演算法", "演算法分析", "字串", "字元"]:
    ac.add(w)
ac.build()

text = "文字演算法處理字串與字元，演算法分析是核心。"
print(ac.search(text))
# 例如 [(2, '演算法'), (7, '字串'), (10, '字元'), (14, '演算法')]

複雜度分析#

建構：插入 O(M)；BFS 建失敗連結時，沿失敗鏈跳躍的總成本可用均攤分析證明為 O(M × |Σ|) 最壞（|Σ| 用 dict 實作時近似 O(M)），因為每跳一次失敗，狀態深度嚴格減少。
掃描：每讀一個字元，狀態深度至多加一，沿失敗鏈跳躍使深度嚴格減少，故總跳躍數 ≤ n，掃描為 O(n + z)，z 為匹配輸出數。
空間：Trie 節點 O(M)；若轉成完整 DFA 則為 O(M × |Σ|)。
與逐一 KMP 比較：KMP 需 O(k×n + M) 次；AC 在樣式數大時優勢壓倒性——敏感詞過濾 5 萬詞、10 萬字文章，AC 只掃一遍。

練習#

修改 add 與 out，讓 search 回傳每個匹配的「樣式、起點、終點」，並用重疊樣式（如 he、she、hers）手動驗證輸出。
實作「輸出連結（output link）」優化：每個節點指向失敗鏈上最近的樣式結尾節點，讓枚舉匹配不再需要走完整條失敗鏈；比較兩版在 10 萬字文字上的執行時間。
將 AC 自動機壓平為 DFA（每狀態預算所有字元轉移），測量記憶體與掃描速度的變化，討論字母表大小對空間的影響；再思考中文（數千常用字）場景下該如何取捨。