1、概述

Aho-Corasick自動(dòng)機(jī)算法（簡(jiǎn)稱(chēng)AC自動(dòng)機(jī)）1975年產(chǎn)生于貝爾實(shí)驗(yàn)室。該算法應(yīng)用有限自動(dòng)機(jī)巧妙地將字符比較轉(zhuǎn)化為了狀態(tài)轉(zhuǎn)移。此算法有兩個(gè)特點(diǎn)，一個(gè)是掃描文本時(shí)完全不需要回溯，另一個(gè)是時(shí)間復(fù)雜度為O(n)，時(shí)間復(fù)雜度與關(guān)鍵字的數(shù)目和長(zhǎng)度無(wú)關(guān)。

好了，我們先看下最原始的多模式匹配算法：

主串T，n=strlen（T）。

模式串P_i m_i = strlen(p_i)

是O（mn）的時(shí)間復(fù)雜度。

上面的算法很笨吧，下面看看聰明的AC算法是個(gè)啥意思。

2、 AC算法思想

AC算法思想：用多模式串建立一個(gè)確定性的樹(shù)形有限狀態(tài)機(jī)，以主串作為該有限狀態(tài)機(jī)的輸入，使?fàn)顟B(tài)機(jī)進(jìn)行狀態(tài)的轉(zhuǎn)換，當(dāng)?shù)竭_(dá)某些特定的狀態(tài)時(shí)，說(shuō)明發(fā)生模式匹配。

下圖是多模式he/ she/ his /hers構(gòu)成的一個(gè)確定性有限狀態(tài)機(jī)，做幾點(diǎn)說(shuō)明：

1、 該狀態(tài)機(jī)優(yōu)先按照實(shí)線(xiàn)標(biāo)注的狀態(tài)轉(zhuǎn)換路徑進(jìn)行轉(zhuǎn)換，當(dāng)所有實(shí)線(xiàn)標(biāo)注的狀態(tài)轉(zhuǎn)換路徑條件不能滿(mǎn)足時(shí)，按照虛線(xiàn)的狀態(tài)轉(zhuǎn)換路徑進(jìn)行狀態(tài)轉(zhuǎn)換。如：狀態(tài)0時(shí)，當(dāng)輸入h，則轉(zhuǎn)換到狀態(tài)1；輸入s，則轉(zhuǎn)換到狀態(tài)3；否則轉(zhuǎn)換到狀態(tài)0。

2、 匹配過(guò)程如下：從狀態(tài)0開(kāi)始進(jìn)行狀態(tài)轉(zhuǎn)換，主串作為輸入。如主串為：ushers，狀態(tài)轉(zhuǎn)換的過(guò)程是這樣的：

3、  當(dāng)狀態(tài)轉(zhuǎn)移到2，5，7，9等紅色狀態(tài)點(diǎn)時(shí)，說(shuō)明發(fā)生了模式匹配。

如主串為：ushers，則在狀態(tài)5、2、9等狀態(tài)時(shí)發(fā)生模式匹配，匹配的模 式串有she、he、hers。

定義：

在預(yù)處理階段，AC自動(dòng)機(jī)算法建立了三個(gè)函數(shù)，轉(zhuǎn)向函數(shù)goto，失效函數(shù)failure和輸出函數(shù)output，由此構(gòu)造了一個(gè)樹(shù)型有限自動(dòng)機(jī)。

轉(zhuǎn)向函數(shù)，指的是一種狀態(tài)之間的轉(zhuǎn)向關(guān)系。g(pre, x)=next：狀態(tài)pre在輸入一個(gè)字符x后轉(zhuǎn)換為狀態(tài)next（上圖中的實(shí)線(xiàn)部分）。如果在模式串中不存在這樣的轉(zhuǎn)換，則next=failstate。

失效函數(shù)，指的也是狀態(tài)和狀態(tài)之間一種轉(zhuǎn)向關(guān)系。f(per)=next：是在比較失配的情況下使用的轉(zhuǎn)換關(guān)系。在構(gòu)造轉(zhuǎn)向函數(shù)時(shí)，把不存在的轉(zhuǎn)換用failstate表示，但是failstate不是一個(gè)具體的狀態(tài)，狀態(tài)機(jī)轉(zhuǎn)換轉(zhuǎn)換到failstate狀態(tài)的時(shí)候就不知道該往哪轉(zhuǎn)了。所以就要在狀態(tài)機(jī)中找到一個(gè)有意義的狀態(tài)代替failstate，當(dāng)出現(xiàn)failstate狀態(tài)時(shí)，自動(dòng)切換到那個(gè)狀態(tài)。

這個(gè)狀態(tài)節(jié)點(diǎn)應(yīng)該具有這樣的特征：從這個(gè)狀態(tài)節(jié)點(diǎn)向上直到樹(shù)根節(jié)點(diǎn)（狀態(tài)0）所經(jīng)歷的輸入字符，和從產(chǎn)生failstate狀態(tài)的那個(gè)狀態(tài)節(jié)點(diǎn)向上所經(jīng)歷的輸入字符串完全相同。而且這個(gè)狀態(tài)節(jié)點(diǎn)，是所有具備這些條件的節(jié)點(diǎn)中深度最大的那個(gè)節(jié)點(diǎn)。如果不存在滿(mǎn)足條件的狀態(tài)節(jié)點(diǎn)，則失效函數(shù)為0。

累死了。舉例子說(shuō)吧，對(duì)狀態(tài)9輸入任何一個(gè)字符都會(huì)產(chǎn)生failstate狀態(tài)，需要失效函數(shù)。狀態(tài)3向上到狀態(tài)0經(jīng)過(guò)的輸入字符串為s；而由狀態(tài)9向上的輸入字符串為sreh。字符串s相同，并且狀態(tài)3是滿(mǎn)足此條件的唯一節(jié)點(diǎn)，則

f(9)=3。

說(shuō)來(lái)說(shuō)去，失效函數(shù)就是要干這么件事兒：

意思就是說(shuō)，在比較模式串1發(fā)生失配時(shí)，找一個(gè)模式串2，使得P₂[0...j-1] = P₁[i-j+1...i]。然后繼續(xù)比較模式串2。看上面那個(gè)圖，想起點(diǎn)兒什么東西沒(méi)有？對(duì)了，是KMP算法。有人說(shuō)AC算法就是KMP算法在多模式匹配情況下的擴(kuò)展。

輸出函數(shù)，指的是狀態(tài)和模式串之間的一種關(guān)系。output(i)={P}，表示當(dāng)狀態(tài)機(jī)到達(dá)狀態(tài)i時(shí)，模式串集合{P}中的所有模式串可能已經(jīng)完成匹配。

例：

模式串為：he/ she/ hers/ his 時(shí)，如上圖所示：

轉(zhuǎn)向函數(shù)：

失效函數(shù)：

輸出函數(shù)：

3、 AC代碼分析

下面的代碼參考snort入侵檢測(cè)系統(tǒng)開(kāi)源軟件的acsmx.c文件。

3.1數(shù)據(jù)結(jié)構(gòu)分析

所有狀態(tài)都被存儲(chǔ)在一個(gè)ACSM_STATETABLE類(lèi)型的數(shù)組中。

typedef struct  {   

    int      NextState[ ALPHABET_SIZE ]; 

    int      FailState;  

    ACSM_PATTERN *MatchList；

}ACSM_STATETABLE；

NextState對(duì)應(yīng)轉(zhuǎn)向函數(shù)；FailState對(duì)應(yīng)失效函數(shù)；MatchList對(duì)應(yīng)輸出函數(shù)。

3.2代碼分析

代碼流程如下圖：