多模匹配算法

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

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

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

4、關(guān)鍵字集he, she, his, hers建立轉(zhuǎn)向函數(shù)。 向圖表中添加第一個(gè)關(guān)鍵字，得到： 從狀態(tài)0到狀態(tài)2的路徑拼寫出了關(guān)鍵字“he”，我們把輸出“he”和狀態(tài)2相關(guān)聯(lián)。 添加第二個(gè)關(guān)鍵字“she”，得到：輸出“she”和狀態(tài)5相關(guān)聯(lián)。第6頁(yè)，共28頁(yè)，2022年，5月20日，14點(diǎn)7分，星期二 增加第三個(gè)關(guān)鍵字“his”，我們得到了下面這個(gè)圖。注意到當(dāng)我們?cè)黾雨P(guān)鍵字“his”時(shí)，已經(jīng)存在一條從狀態(tài)0到狀態(tài)1標(biāo)記著h的邊了，所以我們不必另外添加一條同樣的邊。輸出“his”是和狀態(tài)7相關(guān)聯(lián)的第7頁(yè)，共28頁(yè)，2022年，5月20日，14點(diǎn)7分，星期二 添加第四個(gè)關(guān)鍵字“hers”，可以得到：

5、輸出“hers”和狀態(tài)9相關(guān)聯(lián)。在這里，我們能夠使用已有的兩條邊：一條是從狀態(tài)0到1標(biāo)記著h的邊；一條是從狀態(tài)1到2標(biāo)記著e的邊。 第8頁(yè)，共28頁(yè)，2022年，5月20日，14點(diǎn)7分，星期二 這樣，圖已經(jīng)成為一棵帶根的樹。為了完成轉(zhuǎn)向函數(shù)的構(gòu)建，我們對(duì)除了h和s外的其他每個(gè)字符，都增加一個(gè)從狀態(tài)0到狀態(tài)0的循環(huán)。這樣，我們得到了如圖1 a) 所示的狀態(tài)轉(zhuǎn)移圖，這個(gè)圖就代表轉(zhuǎn)向函數(shù)。第9頁(yè)，共28頁(yè)，2022年，5月20日，14點(diǎn)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頁(yè)，

6、共28頁(yè)，2022年，5月20日，14點(diǎn)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頁(yè)，共28頁(yè)，2022年，5月20日，14點(diǎn)7分，星期二 計(jì)算思路：先計(jì)算所有深度是1的狀態(tài)的失效函數(shù)值，然后計(jì)算所有深度為2的狀態(tài)，以此類推，直到所有狀態(tài)（除了狀態(tài)0，因?yàn)樗?/p>

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

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

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

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

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

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

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

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

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

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

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