AC自動機演算法
| AC自動機演算法 | |
|---|---|
 艾侯-科拉希克自動機示意圖 | |
| 概況 | |
| 類別 | 字串搜尋、字串匹配 |
| 資料結構 | 字串有限狀態機 |
| 複雜度 | |
| 相關變數的定義 | |
在電腦科學中，艾侯-科拉希克演算法（英語：Aho–Corasick algorithm）是由阿爾佛雷德·艾侯和瑪格麗特·J·科拉希克（Margaret J. Corasick）發明的字串搜尋演算法，[1]用於在輸入的一串字串中匹配有限組「字典」中的子串。它與普通字串匹配的不同點在於同時與所有字典串進行匹配。演算法均攤情況下具有近似於線性的時間複雜度，約為字串的長度加所有匹配的數量。然而由於需要找到所有匹配數，如果每個子串互相匹配（如字典為a，aa，aaa，aaaa，輸入的字串為aaaa），演算法的時間複雜度會近似於匹配的二次函數。
該演算法主要依靠構造一個有限狀態機（類似於在一個trie樹中添加失配指標）來實現。這些額外的失配指標允許在尋找字串失敗時進行回退（例如設Trie樹的單詞cat匹配失敗，但是在Trie樹中存在另一個單詞cart，失配指標就會指向字首ca），轉向某字首的其他分支，免於重複匹配字首，提高演算法效率。
當一個字典串集合是已知的(例如一個電腦病毒庫), 就可以以離線方式先將自動機求出並儲存以供日後使用，在這種情況下，演算法的時間複雜度為輸入字串長度和匹配數量之和。
UNIX系統中的一個命令fgrep就是以AC自動機演算法作為基礎實現的。
樣例
設一個字典中有如下單詞：{a,ab,bab,bc,bca,c,caa}.
下方的圖是用AC自動機演算法由該詞典構造而成的一棵Trie樹，其中每個節點都有一條從根節點到它的唯一路徑，代表一個單詞。
在這種數據結構中，字串的每一個字首都有一個節點來表示（詳見Trie）。所以如果（bca）在字典中，則會存在（bca），（bc），（b）和（）對應的節點。如果該節點表示的字串在字典中存在，則該節點為一個藍色節點，否則為一個灰色節點。
樹中的黑色有向邊代表起點是終點的「父親」（即起點對應字串增加一個字元可得終點對應字串），例如從（bc）有一條指向（bca）的黑色有向邊。
樹中的藍色有向邊（字尾節點）代表終點對應字串是起點對應字串的最大嚴格字尾。例如對於一個節點（caa），它的嚴格字尾為（aa），（a）和（），其中在圖中且最長的為（a），所以（caa）有一條指向（a）的藍色有向邊。一個節點的藍色有向邊可以在線性時間內通過重複遍歷節點父親節點的藍色有向邊直到橫移節點（the traversing node）有一個屬於目標節點字首的孩子。
樹中的綠色有向邊（字典字尾節點）代表終點是起點經過藍色有向邊到達的第一個藍色節點（即字典中存在終點對應字串）。例如（bca）有一條綠色邊連向（a），因為（a）是（bca）通過藍色有向邊到達的第一個藍色節點，路徑為（bca）→（ca）→（a）。綠色有向邊也可以在線性時間內通過遍歷藍色有向邊直到找到一個藍色節點，並用記憶化的方法計算。
| 節點 | 是否在字典中 | 字尾節點（藍色有向邊） | 字典字尾節點（綠色有向邊） |
|---|---|---|---|
| () | – | ||
| (a) | + | () | |
| (ab) | + | (b) | |
| (b) | – | () | |
| (ba) | – | (a) | (a) |
| (bab) | + | (ab) | (ab) |
| (bc) | + | (c) | (c) |
| (bca) | + | (ca) | (a) |
| (c) | + | () | |
| (ca) | – | (a) | (a) |
| (caa) | + | (a) | (a) |
在每一步中，演算法先尋找當前節點的「孩子節點」，如果沒有找到匹配，尋找它的後綴（suffix）節點的孩子，如果仍然沒有，接着尋找後綴節點的後綴節點的孩子，如此循環，直到根結點，如果到達根節點仍沒有找到匹配則結束。
當演算法尋找到一個節點，則輸出所有結束在當前位置的字典項。輸出步驟為首先找到該節點的字典字尾，然後用遞歸的方式一直執行到節點沒有字典字首為止。同時，如果該節點為一個字典節點，則輸出該節點本身。
輸入abccab後演算法的執行步驟如下：
| 節點 | 剩餘字串 | 輸出：結束位置 | 過渡 | 輸出 |
|---|---|---|---|---|
| () | abccab | 從根開始 | ||
| (a) | bccab | a:1 | ()→子節點(a) | 當前節點 |
| (ab) | ccab | ab:2 | (a)→子節點(ab) | 當前節點 |
| (bc) | cab | bc:3, c:3 | (ab)→字尾節點(b)→子節點(bc) | 當前節點，字典字尾 |
| (c) | ab | c:4 | (bc)→字尾節點(c)→字尾節點()→子節點(c) | 當前節點 |
| (ca) | b | a:5 | (c)→(ca) | 字典字尾 |
| (ab) | ab:6 | (ca)→字尾節點(a)→子節點(ab) | 當前節點 |
參考來源
- ^ Aho, Alfred V.; Corasick, Margaret J. Efficient string matching: An aid to bibliographic search. Communications of the ACM. June 1975, 18 (6): 333–340. MR 0371172. doi:10.1145/360825.360855.
外部連結
- Set Matching and Aho–Corasick Algorithm, lecture slides by Pekka Kilpeläinen
- Aho–Corasick entry（頁面存檔備份，存於互聯網檔案館） in NIST's Dictionary of Algorithms and Data Structures
- Aho-Corasick implementation in C++（頁面存檔備份，存於互聯網檔案館）
- Aho-Corasick implementation in Go（頁面存檔備份，存於互聯網檔案館）