深入淺出AC算法——源泉書簽

1、Author:源泉書簽Date：2015-12-13Description：解讀Aho-Corasick自動機(jī)算法（AC算法）Version：1.0版本說明版本號作者日期說明1.0源泉書簽2015-12-13初稿參考資料：點(diǎn)此超鏈接AC算法介紹模式匹配算法（本文中模式匹配即為關(guān)鍵詞匹配），基本的有KMP算法、BM算法。這些都是單模式（單關(guān)鍵詞）匹配算法，實(shí)際的防火墻開發(fā)中，更多的情況是需要使用多模式匹配。Aho-Corasick自動機(jī)算法（下稱AC算法）是多模式匹配的經(jīng)典算法，商用的軟件中使用的多模式匹配算法往往就是基于AC算法的改進(jìn)算法。AC算法既然如此重要，我們就需要對其進(jìn)行深入解讀，了解

2、其原理。假設(shè)現(xiàn)在我們有這么一個多模式匹配問題：有四個關(guān)鍵詞he, she, his, hers，然后給你一段文本“ushers”，要求找出此文本中是否包含這些關(guān)鍵詞。下面我們用AC算法解決此問題。AC算法使用了有限狀態(tài)自動機(jī)（Deterministic Finite Automaton，DFA）的概念。DFA包含一組狀態(tài)，每個狀態(tài)用一個數(shù)字代表。狀態(tài)機(jī)讀入文本串中的字符，然后通過產(chǎn)生狀態(tài)轉(zhuǎn)移或者發(fā)送輸出的方式來處理文本。DFA行為通過三個函數(shù)來指示：轉(zhuǎn)向函數(shù)goto function，失效函數(shù)failure function和輸出函數(shù)output function。DFA包含三個抽象的函數(shù)概念

3、：（1） goto function ： 轉(zhuǎn)向函數(shù)（2） failure function ： 失效函數(shù)（3） output function ： 輸出函數(shù)我們先把模式集he, she, his, hers的DFA畫出來，讀者不懂沒關(guān)系，先往下看。DFA的三個函數(shù)轉(zhuǎn)向函數(shù)失效函數(shù)輸出函數(shù)轉(zhuǎn)向，失效和輸出函數(shù)的構(gòu)建 現(xiàn)在說明如何根據(jù)一個關(guān)鍵字集建立正確的轉(zhuǎn)向、失效和輸出函數(shù)。整個構(gòu)建包含兩個部分，在第一部分確定狀態(tài)和轉(zhuǎn)向函數(shù)，在第二部分我們計(jì)算失效函數(shù)。輸出函數(shù)的計(jì)算則是穿插在第一部分和第二部分中完成。構(gòu)建轉(zhuǎn)向函數(shù)為了構(gòu)建轉(zhuǎn)向函數(shù)，我們需要建立一個狀態(tài)轉(zhuǎn)移圖。開始，這個圖只包含一個初始狀態(tài)0。然

4、后，通過添加一條從起始狀態(tài)出發(fā)的路徑的方式，依次向圖中輸入每個關(guān)鍵字。新的頂點(diǎn)和邊被加入到圖表中，以致于產(chǎn)生了一條能拼寫出關(guān)鍵字的路徑。關(guān)鍵字會被添加到這條路徑的終止?fàn)顟B(tài)的輸出函數(shù)中。當(dāng)然只有必要時才會在圖表中增加新的邊。我們開始對關(guān)鍵字集he, she, his, hers建立轉(zhuǎn)向函數(shù)。向圖表中添加第一個關(guān)鍵字，得到：從狀態(tài)0到狀態(tài)2的路徑拼寫出了關(guān)鍵字“he”，我們把輸出“he”和狀態(tài)2相關(guān)聯(lián)。添加第二個關(guān)鍵字“she”，得到：輸出“she”和狀態(tài)5相關(guān)聯(lián)。增加第三個關(guān)鍵字“his”，我們得到了下面這個圖。注意到當(dāng)我們增加關(guān)鍵字“his”時，已經(jīng)存在一條從狀態(tài)0到狀態(tài)1標(biāo)記著h的邊了，所以

5、我們不必另外添加一條同樣的邊。輸出“his”是和狀態(tài)7相關(guān)聯(lián)的。在這里，我們能夠使用已有的兩條邊：一條是從狀態(tài)0到1標(biāo)記著h的邊；一條是從狀態(tài)1到2標(biāo)記著e的邊。這樣，圖已經(jīng)成為一棵帶根的樹。為了完成轉(zhuǎn)向函數(shù)的構(gòu)建，我們對除了h和s外的其他每個字符，都增加一個從狀態(tài)0到狀態(tài)0的循環(huán)。這樣，我們得到了狀態(tài)轉(zhuǎn)移圖，這個圖就代表轉(zhuǎn)向函數(shù)。在構(gòu)建轉(zhuǎn)向函數(shù)的過程中，我們已經(jīng)得到了輸出集：ioutput(i)2he5she7his9hers注意，這個還不是最終的輸出集。構(gòu)建失效函數(shù)失效函數(shù)是根據(jù)轉(zhuǎn)向函數(shù)建立的。首先，我們定義狀態(tài)轉(zhuǎn)移圖中狀態(tài)state的深度為從狀態(tài)0到狀態(tài)state的最短路徑。例如在下圖中

6、，起始狀態(tài)的深度是0，狀態(tài)1和3的深度是1，狀態(tài)2，4，和6的深度是2，等等。這里列出每一個狀態(tài)（即圖中的每一個數(shù)字）的深度：d(0) = 0; d(1) = d(3) = 1; d(2) = d(6) = d(4) = 2d(8) = d(7) = d(5) = 3; d(9) = 4計(jì)算思路：先計(jì)算所有深度是1的狀態(tài)的失效函數(shù)值，然后計(jì)算所有深度為2的狀態(tài)，以此類推，直到所有狀態(tài)（除了狀態(tài)0，因?yàn)樗纳疃葲]有定義）的失效函數(shù)值都被計(jì)算出。 計(jì)算方法：用于計(jì)算某個狀態(tài)失效函數(shù)值的算法在概念上是非常簡單的。首先，令所有深度為1的狀態(tài)state的失效函數(shù)值為fail_func(state) = 0。假設(shè)所有深度小于deep的狀態(tài)的fail值都已經(jīng)被算出了，那么深度為deep的狀態(tài)的失效函數(shù)值將根據(jù)【深度小于deep的狀態(tài)】的【失效函數(shù)值】來計(jì)算。這里舉個例子：狀態(tài)4的失效函數(shù)值計(jì)算狀態(tài)4的前一個狀態(tài)為3，3的失效值為0，由于3狀態(tài)是經(jīng)過條件字符h（注意這個字符h）才轉(zhuǎn)換成4的，所以我們要取【3的失效值0經(jīng)過條件字符h后的狀態(tài)1】作為狀態(tài)4的失效值。即fail_func(4)=1。最終，我們可以構(gòu)建出所有狀態(tài)的失效函數(shù)值：在計(jì)算失效函數(shù)的過程中，注意需要更新輸出函數(shù)。對于上文中的例子，我們求出fail_func(5) = 2。這時，把狀態(tài)2的輸出集，也就是he，增加到