1、多模匹配算法第1頁，共28頁，2022年，5月20日，14點7分，星期二titleAho-Corasick自動機算法（簡稱AC自動機）1975年產(chǎn)生于貝爾實驗室。該算法應(yīng)用有限自動機巧妙地將字符比較轉(zhuǎn)化為了狀態(tài)轉(zhuǎn)移。該算法的基本思想是這樣的：在預(yù)處理階段，AC自動機算法建立了三個函數(shù)，轉(zhuǎn)向函數(shù)goto，失效函數(shù)failure和輸出函數(shù)output，由此構(gòu)造了一個樹型有限自動機。在搜索查找階段，則通過這三個函數(shù)的交叉使用掃描文本，定位出關(guān)鍵字在文本中的所有出現(xiàn)位置。此算法有兩個特點，一個是掃描文本時完全不需要回溯，另一個是時間復(fù)雜度為O(n)，時間復(fù)雜度與關(guān)鍵字的數(shù)目和長度無關(guān)。AC算法-有限自

2、動機的多模式匹配算法第2頁，共28頁，2022年，5月20日，14點7分，星期二2. 樹型有限自動機： 樹型有限自動機包含一組狀態(tài)，每個狀態(tài)用一個數(shù)字代表。狀態(tài)機讀入文本串y中的字符，然后通過產(chǎn)生狀態(tài)轉(zhuǎn)移或者偶爾發(fā)送輸出的方式來處理文本。樹型有限自動機的行為通過三個函數(shù)來指示：轉(zhuǎn)向函數(shù)g，失效函數(shù)f和輸出函數(shù)output。 第3頁，共28頁，2022年，5月20日，14點7分，星期二例如：對應(yīng)模式集he, she, his, hers的樹型有限自動機圖1 a） 轉(zhuǎn)向函數(shù)g圖1 b） 失效函數(shù)f 圖1 c） 輸出函數(shù)output 第4頁，共28頁，2022年，5月20日，14點7分，星期二3.

3、轉(zhuǎn)向，失效和輸出函數(shù)的構(gòu)建 現(xiàn)在說明如何根據(jù)一個關(guān)鍵字集建立正確的轉(zhuǎn)向、失效和輸出函數(shù)。整個構(gòu)建包含兩個部分，在第一部分確定狀態(tài)和轉(zhuǎn)向函數(shù)，在第二部分我們計算失效函數(shù)。輸出函數(shù)的計算則是穿插在第一部分和第二部分中完成。 為了構(gòu)建轉(zhuǎn)向函數(shù)，我們需要建立一個狀態(tài)轉(zhuǎn)移圖。開始，這個圖只包含一個代表狀態(tài)0。然后，通過添加一條從起始狀態(tài)出發(fā)的路徑的方式，依次向圖中輸入每個關(guān)鍵字p。新的頂點和邊被加入到圖表中，以致于產(chǎn)生了一條能拼寫出關(guān)鍵字p的路徑。關(guān)鍵字p會被添加到這條路徑的終止狀態(tài)的輸出函數(shù)中。當然只有必要時才會在圖表中增加新的邊。第5頁，共28頁，2022年，5月20日，14點7分，星期二例如: 對

4、關(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)。第6頁，共28頁，2022年，5月20日，14點7分，星期二 增加第三個關(guān)鍵字“his”，我們得到了下面這個圖。注意到當我們增加關(guān)鍵字“his”時，已經(jīng)存在一條從狀態(tài)0到狀態(tài)1標記著h的邊了，所以我們不必另外添加一條同樣的邊。輸出“his”是和狀態(tài)7相關(guān)聯(lián)的第7頁，共28頁，2022年，5月20日，14點7分，星期二 添加第四個關(guān)鍵字“hers”，可以得到：

5、輸出“hers”和狀態(tài)9相關(guān)聯(lián)。在這里，我們能夠使用已有的兩條邊：一條是從狀態(tài)0到1標記著h的邊；一條是從狀態(tài)1到2標記著e的邊。 第8頁，共28頁，2022年，5月20日，14點7分，星期二 這樣，圖已經(jīng)成為一棵帶根的樹。為了完成轉(zhuǎn)向函數(shù)的構(gòu)建，我們對除了h和s外的其他每個字符，都增加一個從狀態(tài)0到狀態(tài)0的循環(huán)。這樣，我們得到了如圖1 a) 所示的狀態(tài)轉(zhuǎn)移圖，這個圖就代表轉(zhuǎn)向函數(shù)。第9頁，共28頁，2022年，5月20日，14點7分，星期二算法1：建立轉(zhuǎn)向函數(shù)g。輸入：關(guān)鍵字集P=p1,p2,p3,pr。輸出：轉(zhuǎn)向函數(shù)g和部分的output函數(shù)。方法: 圖2 建立轉(zhuǎn)向函數(shù)g的偽代碼第10頁，

6、共28頁，2022年，5月20日，14點7分，星期二 失效函數(shù)是根據(jù)轉(zhuǎn)向函數(shù)建立的。首先，我們定義狀態(tài)轉(zhuǎn)移圖中狀態(tài)s的深度為從狀態(tài)0到狀態(tài)s的最短路徑。例如圖1 a)起始狀態(tài)的深度是0，狀態(tài)1和3的深度是1，狀態(tài)2，4，和6的深度是2，等等。 圖1 a)d(0) = 0; d(1) = d(3) = 1; d(2) = d(6) = d(4) = 2 d(8) = d(7) = d(5) = 3; d(9) = 4第11頁，共28頁，2022年，5月20日，14點7分，星期二 計算思路：先計算所有深度是1的狀態(tài)的失效函數(shù)值，然后計算所有深度為2的狀態(tài)，以此類推，直到所有狀態(tài)（除了狀態(tài)0，因為它

7、的深度沒有定義）的失效函數(shù)值都被計算出。 計算方法：用于計算某個狀態(tài)失效函數(shù)值的算法在概念上是非常簡單的。首先，令所有深度為1的狀態(tài)s的函數(shù)值為f(s) = 0。假設(shè)所有深度小于d的狀態(tài)的f值都已經(jīng)被算出了，那么深度為d的狀態(tài)的失效函數(shù)值將根據(jù)深度小于d的狀態(tài)的失效函數(shù)值來計算。 第12頁，共28頁，2022年，5月20日，14點7分，星期二 為了計算深度為d狀態(tài)的失效函數(shù)值，我們考慮每個深度為d-1的狀態(tài)r，執(zhí)行以下步驟：Step1：如果對所有狀態(tài)a的g(r, a) = fail，那么什么都不做Step2：否則，對每個使得g(r, a) = s存在的狀態(tài)s，執(zhí)行以下操作記state = f(

8、r)。零次或者多次令state = f(state)，直到出現(xiàn)一個狀態(tài)使得g(state, a) != fail（注意到，因為對任意字符a，g(0, a) != fail，所以這種狀態(tài)一定能夠找到）Step2：記f(s) = g(state, a)第13頁，共28頁，2022年，5月20日，14點7分，星期二 以圖1 a)為例說明計算的失效函數(shù)f；先令f(1) = f(3) = 0，因為1和3是深度為1的狀態(tài)。計算深度為2的狀態(tài)2，6和4的失效函數(shù)。 計算f(2)，令state = f(1) = 0；由于g(0, a) = 0，得到f(2) = 0。 計算f(6)，令state = f(1)

9、= 0；由于g(0, i) = 0，得到f(6) = 0 。 計算f(4)，令state = f(3) = 0； 由于g(0, h) = 1，得到f(4) = 1。按這種方式繼續(xù)，最終得到了如圖1 b) 所示的失效函數(shù)f。 在計算失效函數(shù)的過程中，也更新了輸出函數(shù)。當求出f(s) = s，時，我們把狀態(tài)s的輸出和狀態(tài)s，的輸出合并到一起。對于上文中的例子，從圖1 a) 我們求出f(5) = 2。這時，把狀態(tài)2的輸出集，也就是he，增加到狀態(tài)5的輸出集中，這樣就得到了新的輸出集合he, she。最終各狀態(tài)的非空輸出集如圖1 c) 所示。 第14頁，共28頁，2022年，5月20日，14點7分，星

10、期二算法2：建立失效函數(shù)f。輸入：轉(zhuǎn)向函數(shù)g和部分的輸出函數(shù)output。輸出：失效函數(shù)f和完整的輸出函數(shù)output。方法:圖3 建立失效函數(shù)f的偽代碼第15頁，共28頁，2022年，5月20日，14點7分，星期二 4. 轉(zhuǎn)向函數(shù)的構(gòu)建 圖1中樹型自動機的狀態(tài)有0, 1, , 9。某個狀態(tài)（通常是0狀態(tài)）被指定為起始狀態(tài)。 轉(zhuǎn)向函數(shù)把一個由狀態(tài)和輸入字符組成的二元組映射成另一個狀態(tài)或者一條失敗消息。 圖1 a) 的狀態(tài)圖代表轉(zhuǎn)向函數(shù)g。比如,從0到1標記著h 的邊表示g(0, h) = 1，如果缺省箭頭則表示失敗。可見，對除e和i之外的其他輸入字符，都有g(shù)(1, h) = fail。所有的樹

11、型有限自動機都有一個共同的特點，即對任何輸入字符a, 都有g(shù)(0, a) != fail。我們將看到，轉(zhuǎn)向函數(shù)在0狀態(tài)上的這種性質(zhì)確保每個輸入字符都可以在狀態(tài)機的一個操作循環(huán)內(nèi)被處理。 第16頁，共28頁，2022年，5月20日，14點7分，星期二舉個例子，記樹型有限自動機為狀態(tài)機M。狀態(tài)機M利用圖1的函數(shù)去處理輸入文本“ushers”，圖4顯示了M在處理文本串時產(chǎn)生的狀態(tài)轉(zhuǎn)移情況。考慮M在狀態(tài)4，且當前輸入字符為e時的操作循環(huán)。由于g(4, e) = 5，狀態(tài)機進入狀態(tài)5，文本指針將前進到下一個輸入字符，并且輸出output(5)。這個輸出表明狀態(tài)機已經(jīng)發(fā)現(xiàn)輸入文本的第四個位置是“she”和

12、“he”出現(xiàn)的結(jié)束位置。在狀態(tài)5上輸入字符r，狀態(tài)機M在此次操作循環(huán)中將產(chǎn)生兩次狀態(tài)轉(zhuǎn)移。由于g(5, r) = fail，M進入狀態(tài)2 = f(5)。然后因為g(2, r) = 8，M進入狀態(tài)8，同時前進到下一個輸入字符。在這次操作循環(huán)中沒有輸出產(chǎn)生。圖4 掃描“ushers”時的狀態(tài)轉(zhuǎn)換序列 第17頁，共28頁，2022年，5月20日，14點7分，星期二 記s為狀態(tài)機的當前狀態(tài)，a為輸入文本y的當前輸入字符。樹型有限自動機的一次操作循環(huán)可以定義如下： 如果g(s, a) = s，那么樹型有限自動機將做一個轉(zhuǎn)向動作。自動機進入狀態(tài)s，而且y的下一個字符變成當前的輸入字符。另外，如果outpu

13、t( s，)不為空，那么狀態(tài)機將輸出與當前輸入字符位置相對應(yīng)的一組關(guān)鍵字。 如果g(s, a) = fail，狀態(tài)機將詢問失效函數(shù)f并且進行失效轉(zhuǎn)移。如果 f(s) = s，那么狀態(tài)機將以s，作為當前狀態(tài)，a為當前輸入字符重復(fù)這個操作循環(huán)。 第18頁，共28頁，2022年，5月20日，14點7分，星期二算法3：樹型有限狀態(tài)機。輸入：一個字符串y=y1y2y3yn（其中yi是一個輸入字符）；一臺 包含上述轉(zhuǎn)向函數(shù)g，失效函數(shù)f和輸出函數(shù)output的樹型有限自動機。輸出：關(guān)鍵字在y中出現(xiàn)的位置。 圖5 建立樹型有限自動機的算法偽代碼第19頁，共28頁，2022年，5月20日，14點7分，星期二

14、5. AC自動機 預(yù)處理階段： 轉(zhuǎn)向函數(shù)把一個由狀態(tài)和輸入字符組成的二元組映射成另一個狀態(tài)或者一條失敗消息。 失效函數(shù)把一個狀態(tài)映射成另一個狀態(tài)。當轉(zhuǎn)向函數(shù)報告失效時，失效函數(shù)就會被詢問。 輸出狀態(tài)，它們表示已經(jīng)有一組關(guān)鍵字被發(fā)現(xiàn)。輸出函數(shù)通過把一組關(guān)鍵字集（可能是空集）和每個狀態(tài)相聯(lián)系的方法，使得這種輸出狀態(tài)的概念形式化。 搜索查找階段： 文本掃描開始時，初始狀態(tài)置為狀態(tài)機的當前狀態(tài)，而輸入文本y的首字符作為當前輸入字符。然后，樹型有限自動機通過對每個文本串的字符都做一次操作循環(huán)的方式來處理文本。 第20頁，共28頁，2022年，5月20日，14點7分，星期二經(jīng)典的多模式匹配算法- AC自動

15、機。 在預(yù)處理階段，AC自動機算法建立了三個函數(shù)，轉(zhuǎn)向函數(shù)goto，失效函數(shù)failure和輸出函數(shù)output，由此構(gòu)造了一個樹型有限自動機。 在搜索查找階段，則通過這三個函數(shù)的交叉使用掃描文本，定位出關(guān)鍵字在文本中的所有出現(xiàn)位置。 此算法有兩個特點，一個是掃描文本時完全不需要回溯，另一個是時間復(fù)雜度為O(n)，時間復(fù)雜度與關(guān)鍵字的數(shù)目和長度無關(guān)。第21頁，共28頁，2022年，5月20日，14點7分，星期二 1975年，Aho和Corasick提出基于確定性有限自動機(DFA) 理論的模式匹配算法，這又是模式匹配問題中一個經(jīng)典的算法。實際上，多模式匹配算法中，有很大一部分都是基于自動機理論

16、的，而且有不少都是基于對AC75算法的改進。 1979年，Commentz和Walter.B 發(fā)明的算法（簡稱CW79算法）結(jié)合了BM算法，在AC75的自動機算法上實現(xiàn)了跳躍掃描文本。 除了自動機這種主流多模式匹配思想外還有一種很有效的想法。這就是哈希（Hashing），Hashing方法的串查尋最早是在1971年被Harrison介紹，之后得到了充分地分析。1992年到1996年，臺灣人Sun Wu和他的導(dǎo)師Udi Manber發(fā)表了一系列的論文 ，詳細地介紹了他們設(shè)計的匹配算法，并用此算法實現(xiàn)了一個Unix下類似fgrep的工具：agrep。 第22頁，共28頁，2022年，5月20日，1

17、4點7分，星期二 AC和QS結(jié)合的反向自動機王永成等人受FW92（一種融合了BM的自動機算法），提出的相類似的結(jié)合QS的反向自動機多模式匹配算法，而且是針對純中文的處理算法。第23頁，共28頁，2022年，5月20日，14點7分，星期二 Wu.Sum和Udi.manber的agrep92年臺灣學(xué)者吳升發(fā)明的agrep是多模式中最位著名的快速匹配算法之一，對處理大規(guī)模的多關(guān)鍵字匹配問題有很好的效果。第24頁，共28頁，2022年，5月20日，14點7分，星期二 DAWG-MATCHDAWG是一種后綴自動機（Suffix Automaton），是建立在模式集P上，能夠辨認出模式集P中所有關(guān)鍵字后綴的確定型自動機。這種思想主要是AC和RF的結(jié)合結(jié)果。第25頁，共28頁，2022年，5月20日，14點7分，星期二 Raffinot的MultiBDM在上述的AC和DAWG兩種自動機掃描思想上產(chǎn)生的多模匹配算法。根據(jù)匹配過程中使用時刻的不同，作者提出了兩種改進。在作者的實驗中，處理大規(guī)模的多關(guān)鍵字匹配問題中有較好的優(yōu)勢。第26頁