簡介

Aho-Corasick算法簡稱AC算法，通過將模式串預處理為確定有限狀態(tài)自動機，掃描文本一遍就能結束。其復雜度為O(n)，即與模式串的數(shù)量和長度無關。

思想

自動機按照文本字符順序，接受字符，并發(fā)生狀態(tài)轉移。這些狀態(tài)緩存了“按照字符轉移成功（但不是模式串的結尾）”、“按照字符轉移成功（是模式串的結尾）”、“按照字符轉移失敗”三種情況下的跳轉與輸出情況，因而降低了復雜度。

基本構造

AC算法中有三個核心函數(shù)，分別是：

success; 成功轉移到另一個狀態(tài)（也稱goto表或success表）

failure; 不可順著字符串跳轉的話，則跳轉到一個特定的節(jié)點（也稱failure表），從根節(jié)點到這個特定的節(jié)點的路徑恰好是失敗前的文本的一部分。

emits; 命中一個模式串（也稱output表）

舉例

以經(jīng)典的ushers為例，模式串是he/ she/ his /hers，文本為“ushers”。構建的自動機如圖

其實上圖省略了到根節(jié)點的fail邊，完整的自動機如下圖：

匹配過程

自動機從根節(jié)點0出發(fā)

首先嘗試按success表轉移（圖中實線）。按照文本的指示轉移，也就是接收一個u。此時success表中并沒有相應路線，轉移失敗。

失敗了則按照failure表回去（圖中虛線）。按照文本指示，這次接收一個s，轉移到狀態(tài)3。

成功了繼續(xù)按success表轉移，直到失敗跳轉步驟2，或者遇到output表中標明的“可輸出狀態(tài)”（圖中紅色狀態(tài)）。此時輸出匹配到的模式串，然后將此狀態(tài)視作普通的狀態(tài)繼續(xù)轉移。

算法高效之處在于，當自動機接受了“ushe”之后，再接受一個r會導致無法按照success表轉移，此時自動機會聰明地按照failure表轉移到2號狀態(tài)，并經(jīng)過幾次轉移后輸出“hers”。來到2號狀態(tài)的路不止一條，從根節(jié)點一路往下，“h→e”也可以到達。而這個“he”恰好是“ushe”的結尾，狀態(tài)機就仿佛是壓根就沒失敗過（沒有接受r），也沒有接受過中間的字符“us”，直接就從初始狀態(tài)按照“he”的路徑走過來一樣（到達同一節(jié)點，狀態(tài)完全相同）。

構造過程

看來這三個表很厲害，不過，它們是怎么計算出來的呢？

goto表

很簡單，了解一點trie樹知識的話就能一眼看穿，goto表就是一棵trie樹。把上圖的虛線去掉，實線部分就是一棵trie樹了。

output表

output表也很簡單，與trie樹里面代表這個節(jié)點是否是單詞結尾的結構很像。不過trie樹只有葉節(jié)點才有“output”，并且一個葉節(jié)點只有一個output。下圖卻違背了這兩點，這是為什么呢？其實下圖的output會在建立failure表的時候進行一次拓充。

以上兩個表通過一個dfs就可以構造出來。關于trie樹的更詳細內(nèi)容，請參考：《Ansj分詞雙數(shù)組Trie樹實現(xiàn)與arrays.dic詞典格式》，《Trie樹分詞》，《雙數(shù)組Trie樹(DoubleArrayTrie)Java實現(xiàn)》。

failure表

這個表是trie樹沒有的，加了這個表，AC自動機就看起來不像一棵樹，而像一個圖了。failure表是狀態(tài)與狀態(tài)的一對一關系，別看圖中虛線亂糟糟的，不過你仔細看看，就會發(fā)現(xiàn)節(jié)點只會發(fā)出一條虛線，它們嚴格一對一。

這個表的構造方法是：

首先規(guī)定與狀態(tài)0距離為1（即深度為1）的所有狀態(tài)的fail值都為0。

然后設當前狀態(tài)是S1，求fail(S1)。我們知道，S1的前一狀態(tài)必定是唯一的（剛才說的一對一），設S1的前一狀態(tài)是S2，S2轉換到S1的條件為接受字符C，測試S3= goto(fail(S2), C)。

如果成功，則fail(S1) = goto(fail(S2), C) = S3。

如果不成功，繼續(xù)測試S4= goto(fail(S3), C)是否成功，如此重復，直到轉換到某個有效的狀態(tài)Sn，令fail(S1) = Sn。

Java實現(xiàn)

原理誰都可以說幾句的，可是優(yōu)雅健壯的代碼卻不是那么容易寫的。我考察了Git上幾個AC算法的實現(xiàn)，發(fā)現(xiàn)robert-bor的實現(xiàn)非常好。一趟代碼看下來，學到了不少設計上的知識。我fork了下來，針對Ascii做了優(yōu)化，添加了中文注釋。

另外，我實現(xiàn)了基于雙數(shù)組Trie樹的AC自動機：《Aho Corasick自動機結合DoubleArrayTrie極速多模式匹配》。性能更高，內(nèi)存可控。

```

//創(chuàng)建set集合

Set stringSet =new HashSet<>();

stringSet.add("高危");

stringSet.add("并發(fā)");

stringSet.add("江蘇");

stringSet.add("彩信");

String[] value =new String[stringSet.size()];

stringSet.toArray(value);

Trie.TrieBuilder trieBuilder = Trie.builder();

if(false){

trieBuilder.stopOnHit();

}

for (String key:value) {

trieBuilder.addKeyword(key);

}

Trie trie = trieBuilder.build();

System.out.println("查看是否包含這些字樣");

System.out.println(trie.containsMatch("江蘇高危短信彩信錫"));

System.out.println("----------查看有哪些-----------------");

Collection emits = trie.parseText("江蘇高危短信彩信錫");

for(Emit temp : emits)

{

System.out.println("包含集合："+temp.getKeyword());

}

```