[科普中國]-AC自動機算法

在計算機科學中，Aho–Corasick算法是由Alfred V. Aho和Margaret J.Corasick 發(fā)明的字符串搜索算法，用于在輸入的一串字符串中匹配有限組“字典”中的子串1。它與普通字符串匹配的不同點在于同時與所有字典串進行匹配。算法均攤情況下具有近似于線性的時間復雜度，約為字符串的長度加所有匹配的數量。然而由于需要找到所有匹配數，如果每個子串互相匹配（如字典為a，aa，aaa，aaaa，輸入的字符串為aaaa），算法的時間復雜度會近似于匹配的二次函數。

簡介AC自動機算法主要依靠構造一個有限狀態(tài)機（類似于在一個trie樹中添加失配指針）來實現。這些額外的失配指針允許在查找字符串失敗時進行回退（例如設Trie樹的單詞cat匹配失敗，但是在Trie樹中存在另一個單詞cart，失配指針就會指向前綴ca），轉向某前綴的其他分支，免于重復匹配前綴，提高算法效率。

當一個字典串集合是已知的(例如一個計算機病毒庫), 就可以以離線方式先將自動機求出并儲存以供日后使用，在這種情況下，算法的時間復雜度為輸入字符串長度和匹配數量之和。

UNIX系統(tǒng)中的一個命令fgrep就是以AC自動機算法作為基礎實現的。

樣例設一個字典中有如下單詞：{a,ab,bab,bc,bca,c,caa}.

下方的圖是用AC自動機算法由該詞典構造而成的一棵Trie樹，其中每個節(jié)點都有一條從根節(jié)點到它的路徑，代表一個單詞。

在這種數據結構中，字符串的每一個前綴都有一個節(jié)點來表示（詳見Trie）。所以如果（bca）在字典中，則會存在（bca），（bc），（b）和（）對應的節(jié)點。如果該節(jié)點表示的字符串在字典中存在，則該節(jié)點為一個藍色節(jié)點，否則為一個灰色節(jié)點。

樹中的黑色有向邊代表起點是終點的“父親”（即起點對應字符串增加一個字符可得終點對應字符串），例如從（bc）有一條指向（bca）的黑色有向邊。

樹中的藍色有向邊（后綴節(jié)點）代表終點對應字符串是起點對應字符串的最大嚴格后綴。例如對于一個節(jié)點（caa），它的嚴格后綴為（aa），（a）和（），其中在圖中且最長的為（a），所以（caa）有一條指向（a）的藍色有向邊。一個節(jié)點的藍色有向邊可以在線性時間內通過重復遍歷節(jié)點父親節(jié)點的藍色有向邊直到橫移節(jié)點（the traversing node）有一個屬于目標節(jié)點前綴的孩子。

樹中的綠色有向邊（字典后綴節(jié)點）代表終點是起點經過藍色有向邊到達的第一個藍色節(jié)點（即字典中存在終點對應字符串）。例如（bca）有一條綠色邊連向（a），因為（a）是（bca）通過藍色有向邊到達的第一個藍色節(jié)點，路徑為（bca）→（ca）→（a）。綠色有向邊也可以在線性時間內通過遍歷藍色有向邊直到找到一個藍色節(jié)點，并用記憶化的方法計算。

|| ||

在每一步中，算法先查找當前節(jié)點的“孩子節(jié)點”，如果沒有找到匹配，查找它的后綴節(jié)點(suffix)的孩子，如果仍然沒有，接著查找后綴節(jié)點的后綴節(jié)點的孩子, 如此循環(huán), 直到根結點，如果到達根節(jié)點仍沒有找到匹配則結束。

當算法查找到一個節(jié)點，則輸出所有結束在當前位置的字典項。輸出步驟為首先找到該節(jié)點的字典后綴，然后用遞歸的方式一直執(zhí)行到節(jié)點沒有字典前綴為止。同時，如果該節(jié)點為一個字典節(jié)點，則輸出該節(jié)點本身。

輸入abccab后算法的執(zhí)行步驟如下：

本詞條內容貢獻者為:

王偉 - 副教授 - 上海交通大學