一種改進的AC多模式匹配算法

劉春暉，黃 宇，宋 琦

（合肥工業(yè)大學(xué)計算機與信息學(xué)院，合肥 230009）

一種改進的AC多模式匹配算法

劉春暉，黃 宇，宋 琦

（合肥工業(yè)大學(xué)計算機與信息學(xué)院，合肥 230009）

在分析AC算法及其相關(guān)算法的基礎(chǔ)上，提出一種改進的多模式匹配算法AC-TE。利用該算法構(gòu)建1個字符串跳躍表和2個哈希表，字符串表存儲模式樹中兩兩相鄰字符組成的字符串及其位置，2個哈希表分別存儲模式樹末層字符串和字符。采用多層跳躍規(guī)則依次查找這3個表，在不發(fā)生漏檢的情況下，使模式樹的最大移動距離為最短模式串長度加3。從模式樹移動次數(shù)、匹配階段時間、各種跳躍距離的概率3個方面測試算法性能。實驗結(jié)果表明，與AC算法相比，AC-TE算法具有更大的模式樹移動距離，消耗的時間更少。

多模式匹配；AC算法；漏檢；移動距離；模式樹

DO I：10.3969/j.issn.1000-3428.2015.10.053

1 概述

隨著互聯(lián)網(wǎng)技術(shù)的發(fā)展，模式匹配技術(shù)被廣泛應(yīng)用于生物醫(yī)學(xué)［1］、網(wǎng)絡(luò)搜索引擎［2］、內(nèi)容過濾防火墻［3］、入侵檢測系統(tǒng)［4］等領(lǐng)域，成為信息領(lǐng)域中重要的研究方向之一。

BF算法［5］是最早的單模式匹配算法，模式串每次移動一個字符的位置，匹配效率低。文獻［6］提出了帶轉(zhuǎn)移函數(shù)的KMP算法，實現(xiàn)模式串跳躍式匹配。文獻［7］提出一種更高效的算法——BM算法，通過引入好后綴規(guī)則和壞字符規(guī)則，增大模式串跳躍距離。文獻［8］改進了BM算法，提出BMH算法，只保留壞字符規(guī)則，降低了預(yù)處理階段復(fù)雜度。文獻［9］進一步改進了BM算法，發(fā)生失配時，只考慮緊靠當(dāng)前匹配窗口的后一個字符，增加了模式串移動距離。

文獻［10］提出AC多模式匹配算法，通過構(gòu)建有限狀態(tài)自動機，實現(xiàn)一次掃描文本完成多個模式匹配。文獻［11］在AC算法基礎(chǔ)上，結(jié)合BM算法思想，采用壞字符和好后綴規(guī)則，實現(xiàn)了模式樹的跳躍式匹配，模式樹最大移動距離為最短模式串長度，因而具有更高的匹配效率。文獻［12］結(jié)合了AC算法和BMH算法，只保留壞字符規(guī)則，但模式樹最大移動距離沒有變。文獻［13］采用字符塊判斷方法，

增大了跳躍的概率，但最大移動距離仍為最短模式串長度。文獻［14］結(jié)合了AC算法和QS算法，盡可能跳過更多的字符，模式樹最大移動距離為最短模式串長度加1。

本文對AC改進算法的模式樹移動規(guī)則進行研究，提出一種高效的多模式匹配算法——AC-TE（Time Efficient AC）。該算法構(gòu)建1個字符串跳躍表和2個哈希表，采用多層跳躍規(guī)則依次查找這3個表，在不發(fā)生漏檢情況下，模式樹最大跳躍距離可達到最短模式串長度加3。

2 AC及其改進算法

2.1 AC算法

2.1.1 預(yù)處理階段

預(yù)處理階段構(gòu)建有限狀態(tài)自動機并計算轉(zhuǎn)移函數(shù)和輸出函數(shù)。

（1）構(gòu)建有限狀態(tài)自動機

對于模式串集P=｛P1，P2，…，Pr｝，構(gòu)建有限狀態(tài)自動機過程描述如下：從狀態(tài)0開始，讀取第1個模式串的第1個字符，生成新狀態(tài)；再從新狀態(tài)開始，讀取第1個模式串的第2個字符，生成新的后繼狀態(tài)，以此類推，直到處理完所有字符；處理完第1個模式串之后，再從0狀態(tài)處理第2個，直到處理完所有模式串。例如，對于模式串集 Pset=｛go，good，get，ago｝，構(gòu)成的有限狀態(tài)自動機如圖1所示。

圖1 有限狀態(tài)自動機

（2）計算轉(zhuǎn)移函數(shù)

轉(zhuǎn)移函數(shù)包括狀態(tài)轉(zhuǎn)移函數(shù)goto和失效轉(zhuǎn)移函數(shù)failure。自動機中，對于狀態(tài)s，若讀入字符c，生成狀態(tài)s’，那么goto（s，c）=s′。對于狀態(tài)s，若讀入字符c，沒有后繼狀態(tài)，那么goto（s，c）=fail。如圖1所示的有限狀態(tài)自動機goto（1，o）=2，goto（1，e）= 5，goto（1，c）=fail。

失效函數(shù)failure用來計算某個字符失配時，應(yīng)轉(zhuǎn)移的狀態(tài)。失效函數(shù)計算規(guī)則：若某狀態(tài)的父狀態(tài)為0，則該狀態(tài)的失效函數(shù)為0；對于其他狀態(tài)m，若其父狀態(tài)為r，標注的字符為“a”，那么failure（m）=goto（failure（r），a）。如圖 1所示有限狀態(tài)自動機failure（7）=0，failure（8）=goto（failure（7），g）= goto（0，g）=1，failure（9）=goto（failure（8），o）= goto（1，o）=2。

（3）計算輸出函數(shù)

構(gòu)造有限狀態(tài)自動機過程中，每當(dāng)處理完一個模式串，就將該模式串加入到當(dāng)前狀態(tài) s的輸出函數(shù)中。計算失效函數(shù)過程中，若failure（s）=s′，則outPut（s）=outPut（s）∪outPut（s′）。如圖1所示有限狀態(tài)自動機，outPut（2）=go，因為failure（9）=2，所以outPut（9）=｛ago｝∪outPut（2）=｛ago，go｝。

2.1.2 匹配過程

匹配過程的步驟如下：

（1）文本串指針P指向文本串首字符，當(dāng)前狀態(tài)s=0。

（2）若P！=NULL，讀取所指字符c；否則匹配結(jié)束。

（3）計算 s′=goto（s，c），若 s′=fail，轉(zhuǎn)步驟（4）；否則當(dāng)前狀態(tài) s=s′，P右移一位；如果outPut（s）==NULL，轉(zhuǎn)步驟（2）；否則，有模式串得到匹配，輸出匹配信息，轉(zhuǎn)步驟（2）。

（4）s=failure（s），轉(zhuǎn)步驟（3）。

2.2 AC改進算法

AC算法不能跳躍，不必要的字符比較次數(shù)多。針對此問題，研究人員提出了多種改進算法。

AC-BM算法是在AC的基礎(chǔ)上，結(jié)合BM算法的啟發(fā)規(guī)則，產(chǎn)生的一種多模式匹配算法。與 AC算法不同，AC-BM算法將模式串集構(gòu)建為Trie樹（模式樹）。模式樹移動方向從右向左，字符比較方向從左向右。此外，AC-BM算法在預(yù)處理階段不考慮失效函數(shù)的問題。匹配階段通過壞字符規(guī)則和好后綴規(guī)則進行跳躍。壞字符和好后綴規(guī)則描述如下：設(shè)當(dāng)前匹配窗口文本串失配字符為c，對應(yīng)模式樹深度為dePth（1≤dePth≤minlen），已匹配部分為字符串S，最短模式串長度為minlen。壞字符規(guī)則考察c在模式樹第dePth層到第minlen層中的出現(xiàn)情況，若未出現(xiàn)，則直接將模式樹移過字符c，移動距離為minlen-dePth+1；若出現(xiàn)在第dePth0層（dePth＜dePth0≤minlen，如果出現(xiàn)多次，取其中深度最小的），則移動模式樹使第dePth0層和字符c對齊，移動距離為dePth0-dePth?？梢钥闯觯谧詈们闆r下，即dePth=1時，當(dāng)前匹配窗口第一個字符即失配，此時最大移動距離為最短模式串長度。好后綴規(guī)則考慮已匹配部分S在模式樹minlen深度內(nèi)出現(xiàn)情況。若模式樹minlen深度內(nèi)有任何模式串以S為前綴，則將模式樹移動minlen-dePth個字符；否則在模式樹minlen深度內(nèi)查找任何以字符串S長度為P的后綴子串作為前綴的模式串，若找到則將模式串移動minlen-P個字符，否則模式樹只移動1個字符。可以看出，最好情況下，即dePth=1或P=1時，最大移動距離為最短模式串長度減1。

文獻［12］將AC算法與BMH算法相結(jié)合，提出了AC-BHM算法，只保留AC-BM的壞字符規(guī)則，但模式樹的最大移動距離沒有變，仍為最短模式串長度。

文獻［13］提出了一種更高效的AC改進算法算法——AC-QSS算法。該算法將當(dāng)前匹配窗口文本串第一個字符以及前一個字符組成字符塊str，發(fā)生失配時，若str不在模式樹minlen深度內(nèi)出現(xiàn)，則直接將模式樹移動minlen個字符。連續(xù)2個字符在模式樹內(nèi)出現(xiàn)的概率要小于單個字符出現(xiàn)的概率，特別是在大字符集、短模式串環(huán)境下，連續(xù)2個字符未出現(xiàn)的概率往往能達到100%，模式樹往往能達到最大移動距離。該算法提高了達到最大移動距離的概率，但沒有提高最大移動距離，仍為最短模式串長度。

文獻［14］將AC算法與SUNDAY算法結(jié)合，提出了AC-SUNDAY算法，在發(fā)生失配時關(guān)注的是文本串當(dāng)前匹配窗口的前一個字符c。AC-SUNDAY算法基于這樣的考慮，當(dāng)發(fā)生失配時，模式樹移動距離至少為1，那么字符c必然會參與下一次比較，如果c不在minlen深度內(nèi)出現(xiàn)，則可以直接跳過，使得模式樹最大移動距離達到minlen+1。如果c出現(xiàn)在minlen深度內(nèi)，且深度為dePth（1≤dePth≤minlen，若c出現(xiàn)多次，取其中最小深度值），則移動距離為dePth。AC-SUNDAY算法模式樹最大移動距離為最短模式串長度加1。

上述4種AC改進算法的模式樹最大移動距離為最短模式串長度或最短模式串長度加1，但仍不夠大。

3 AC-TE算法

針對AC-BM等算法模式樹移動距離不足的問題，本文考慮當(dāng)前匹配窗口前3個字符，設(shè)計新的模式樹移動規(guī)則，在不發(fā)生漏檢情況下，模式樹最大移動距離可達最短模式串長度加3。在此基礎(chǔ)上，設(shè)計一種更高效的多模式匹配算法——AC-TE算法。

3.1 算法設(shè)計思想

AC-TE算法用1個字符串跳躍表和2個哈希表來確定發(fā)生失配時的移動距離。設(shè)模式串集Pset=｛abc，aef，aaaef｝，當(dāng)前匹配窗口前3個字符分別為χ，y，z，如圖2所示。AC-TE算法模式樹移動規(guī)則描述如下：

（1）若z=模式樹首層字符，移動距離為1。

（2）若yz在模式樹minlen深度內(nèi)出現(xiàn)，移動使之對齊（查找字符串跳躍表）。

（3）若 χy=任一模式串第 minlen-1和第minlen層字符組成的字符串，移動距離為minlen+1（查找哈希表1）。

（4）若χ=任一模式串第minlen層字符，移動距離為minlen+2（查找哈希表2）。

（5）若以上均不滿足，移動距離為minlen+3。

圖2 匹配窗口

3.2 算法步驟

AC-TE算法分為2個階段：預(yù)處理階段和匹配階段。

（1）預(yù)處理階段

1）構(gòu)建模式樹。

2）創(chuàng)建字符串跳躍表（String Shift Table，SST），記作SST。

將模式樹minlen深度內(nèi)兩兩相鄰字符組成字符串。字符串表用來記錄這些字符串在模式樹中的位置，通過到模式樹首層字符的距離來表示，記為dis（S）。對任一字符串S=Pi［k］Pi［k+1］（1≤i≤r，1≤k≤minlen-1），dis（S）=Pi［k］到模式樹首字符距離等于k-1。若某個字符串多次出現(xiàn)，取其中的最小值。SST表創(chuàng)建算法偽代碼具體如下：

算法1創(chuàng)建字符串跳躍表SST

例如，對于模式集Pset=｛abc，aef，aaaef｝，P1= abc，P2=aef，P3=aaaef，minlen=3。minlen深度內(nèi)

所有兩兩相鄰字符構(gòu)成的字符串集合為 S=｛ab，bc，ae，ef，aa｝。以字符串a(chǎn)a為例，在minlen深度內(nèi)出現(xiàn)了2次，均在 P3中。選深度較小的位置計算，由于a=P3［1］，k=1，因此dis（aa）=0。由Pset創(chuàng)建的SST表如表1所示。

表1 SST表

3）創(chuàng)建末層字符串哈希表（Last Two String hashing Table），記作LTST。LTST表存儲每個模式串第minlen-1個字符及第minlen個字符組成的字符串。LTST表創(chuàng)建算法偽代碼如下：

算法2創(chuàng)建LTST

例如，模式集 Pset=｛abc，aef，aaaef｝對應(yīng)的LTST表如表2所示。

表2 LTST表

4）創(chuàng)建末層字符哈希表（Last Character hash Table），記作LCT。LCT表存儲每個模式串第minlen層的字符。LCT表創(chuàng)建算法偽代碼如下：

算法3創(chuàng)建LCT表

例如，模式集Pset=｛abc，aef，aaaef｝對應(yīng)LCT表如表3所示。

表3 LCT表

（2）匹配階段

1）初始狀態(tài)。模式樹的首層節(jié)點對齊文本串的倒數(shù)第minlen個字符，第minlen層節(jié)點對齊文本串的末字符。模式樹移動方向從右向左，字符比較方向從左向右。

2）字符比較。在當(dāng)前匹配窗口內(nèi)，從左向右逐個讀入文本串字符，利用goto函數(shù)進行狀態(tài)轉(zhuǎn)移，當(dāng)outPut函數(shù)不為空時，輸出匹配成功的字符串；當(dāng)發(fā)生失配時，計算移動距離shift length，并將模式樹左移shift length位。移動距離計算算法偽代碼如下：

算法4計算移動距離

3）重復(fù)步驟2），直到模式樹和文本串的首字符對齊，匹配過程結(jié)束。

3.3 AC-TE算法分析

3.3.1 模式樹最大移動距離的增大

已有的改進AC多模式算法模式樹最大移動距離為最短模式串長度加 1。AC-BM 算法和AC-BMH算法的壞字符在匹配窗口內(nèi)，最多能跳過當(dāng)前匹配窗口，距離為最短模式串長度。AC-QSS算法最大安全移動距離也為最短模式串長度，任何大于最短模式串長度的移動都有可能造成漏檢。AC-SUNDAY算法的壞字符是當(dāng)前匹配窗口外前一個字符，跳過這個壞字符能達到最短模式串長度加1的移動距離。之所以沒有出現(xiàn)移動距離超過最短模式串長度加1的算法，是因為按照傳統(tǒng)的移動規(guī)則，會導(dǎo)致不能達到1位或2位的移動距離，從而導(dǎo)致漏檢。以AC-SUNDAY算法跳躍思想為例，若要使

最大移動距離為最短模式串長度加3，則可以考慮匹配窗口前第 3個字符。若該字符不存在于模式樹minlen深度內(nèi)，直接將其跳過，移動距離為minlen+ 3。但是，此時最小跳躍距離為3，遺漏了距離為1和2的移動情況。AC-TE算法移動距離計算算法考慮到較小的跳躍距離，能夠跳躍1～minlen+3的任一距離，所以不會發(fā)生漏檢。AC-TE算法最好情況下能跳過當(dāng)前匹配窗口前3個字符，使得模式樹最大跳躍距離為最短模式串長度加3。最大移動距離的增大使得平均移動距離得到增加，減少了字符比較次數(shù)，提高了匹配速度。

3.3.2 預(yù)處理階段時空復(fù)雜度

算法1的外層循環(huán)次數(shù)等于模式串的數(shù)量r，內(nèi)層循環(huán)次數(shù)為 minlen-1，時間復(fù)雜度為 r×（minlen-1）。算法1字符串表存儲的是所有模式串minlen深度內(nèi)長度為2的字符串及對應(yīng)dis值，空間復(fù)雜度為r×（minlen-1）。算法2只有一層循環(huán)，時間復(fù)雜度是 r。算法 2存儲所有模式串第minlen-1個字符及第minlen個字符組成的字符串，所以空間復(fù)雜度也為r。和算法2類似，算法3時間空間復(fù)雜度均為r。

因此，預(yù)處理階段總的時間復(fù)雜度為 O（r×（minlen-1）+r+r），即O（r×（minlen+1））。預(yù)處理時間空間復(fù)雜度也為O（r×（minlen+1））。

3.3.3 匹配階段時間復(fù)雜度

AC-TE算法匹配階段時間復(fù)雜度分3種情況討論。在最壞情況下，模式樹每次都移動一個字符位置，且最長模式串比較到最后一個字符，時間復(fù)雜度為O（n×maχlen），n為文本串長度，maχlen為最長模式串長度。最好情況下，匹配窗口每次均移動minlen+3個字符，此時時間復(fù)雜度為O（n/（minlen+ 3））。平均情況下，時間復(fù)雜度為O（n）。

最壞情況下，AC-BM，AC-BMH，AC-QSS和ACSUNDAY算法時間復(fù)雜度均為O（n×maχlen）。平均情況下，上述算法時間復(fù)雜度也為O（n）。但是，在最好情況下，上述算法時間復(fù)雜度分別為O（n/minlen），O（n/minlen），O（n/minlen）和O（n/（minlen+1））。

考慮到AC-TE算法最大移動距離大，且采用字符塊判斷規(guī)則，達到超過minlen移動距離的概率也大，故匹配階段時間效率優(yōu)于上述算法。

4 實驗與結(jié)果分析

實驗環(huán)境：Window s 8.1系統(tǒng)，因特爾Core Dual-Core 1.5 GHz，3 GB內(nèi)存。

實驗數(shù)據(jù)：待匹配文本串為路透社Reuters-21578新聞數(shù)據(jù)集，約為28 MB。然后，從紐約時報、中國日報、華盛頓郵報的500個新聞網(wǎng)頁上隨機截取長度分別為4 Byte，8 Byte，16 Byte，24 Byte，32 Byte的模式串各400個。

（1）模式樹移動次數(shù)

固定模式串長度為8 Byte，改變模式串?dāng)?shù)量。實驗結(jié)果如圖3所示，最好情況下，AC-TC算法模式樹移動次數(shù)只有AC-BMH算法的71.0%，ACQSS算法的82.8%，AC-SUNDAY算法的88.9%。模式樹移動次數(shù)越少，平均移動距離越大，時間效率越高。

圖3 固定模式串長度時的模式樹移動次數(shù)

固定模式串?dāng)?shù)量為400，取不同模式串長度進行實驗。實驗結(jié)果如圖4所示，AC-TE算法的模式樹移動次數(shù)始終最少，效率最高。

圖4 固定模式串?dāng)?shù)量時的模式樹移動次數(shù)

（2）匹配階段時間

固定模式串長度為8 Byte，數(shù)量分別為10，20，50，100和400，結(jié)果如圖5所示，可以看出AC-TE算法的時間性能最優(yōu)。

圖5 改變模式串?dāng)?shù)量所用時間

固定模式串?dāng)?shù)量為400，分別取不同模式串長度進行實驗，結(jié)果如圖6所示，可以看出AC-TE算法消耗時間始終最少。

圖6 改變模式串長度所用時間

（3）各種跳躍距離的概率

AC-TE模式樹移動距離有 5種情況，即 1，dis（yz）+2，minlen+1，minlen+2，minlen+3。根據(jù)表4實驗結(jié)果，5種情況出現(xiàn)的平均概率分別為3.0%，17.6%，9.6%，7.0%和62.9%，達到minlen以上跳躍距離的平均概率可達79.5%，時間效率高。

表4 各種跳躍距離下的概率

5 結(jié)束語

本文提出一種高效的多模式匹配算法——ACTE。該算法基于有限狀態(tài)自動機，采用多層判斷規(guī)則查找3個預(yù)處理表，實現(xiàn)了模式樹的跳躍式匹配。理論分析和實驗表明，AC-TE算法的時間性能優(yōu)于已有AC改進算法。下一步將對AC-TE算法如何高效地應(yīng)用于內(nèi)容過濾防火墻進行研究。

［1］ Bergeron B.Bioinformatic Computing［M］.Indianapolis，USA：Prentice Hall，2002.

［2］ 王繼成，蕭 嶸，孫正興，等.Web信息檢索研究進展［J］.計算機研究與發(fā)展，2001，38（2）：187-193.

［3］ 宋 華，戴一奇.一種用于內(nèi)容過濾和檢測的快速多關(guān)鍵詞識別算法［J］.計算機研究與發(fā)展，2004，41（6）：940-945.

［4］ 蔣建春，卿斯?jié)h.網(wǎng)絡(luò)安全入侵檢測：研究綜述［J］.軟件學(xué)報，2000，11（11）：1460-1467.

［5］ 盧開澄.計算機算法導(dǎo)引-設(shè)計與分析［M］.北京：清華大學(xué)出版社，1996.

［6］ Knuth D E，Morris JH，Pratt V R.Fast Pattern Matching in Strings［J］.SIAM Journal on Computing，1977，6（2）：323-350.

［7］ Boyer R S，Moore J S.A Fast String Searching Algorithm［J］.Communications of the ACM，1977，20（10）：762-772.

［8］ Horspool R N.Practical Fast Searching in Strings［J］. Software-Practice&Experience，1980，10（6）：501-506.

［9］ Sunday D M.A Very Fast Substring Searching Algorithm［J］.Communications of the ACM，1990，33（8）：132-142.

［10］ Aho A V，Corasick M J.Efficient String Matching：An Aid to Bibliographic Search［J］.Communications of the ACM，1975，18（6）：333-340.

［11］ Commerntz W R.A String Matching Algorithm Fast on the Average［C］//Proceedings of the 6th Colloquium on Automata，Languages and Programming.Berlin，Germ any：Springer-Verlag，1979.

［12］ 陸琳琳，田 野.基于確定有限狀態(tài)自動機的改進多模式匹配算法研究［J］.計算機應(yīng)用與軟件，2013，30（7）：322-326.

［13］ 舒銀東.基于有限狀態(tài)自動機的多模式匹配算法研究［D］.合肥：合肥工業(yè)大學(xué)，2011.

［14］ 董世博，李訓(xùn)根.一種改進的字符串多模式匹配算法［J］.計算機工程與應(yīng)用，2013，49（8）：133-137.

編輯顧逸斐

An Improved AC Multiple Pattern Matching Algorithm

LIU Chunhui，HUANG Yu，SONG Qi
（School of Computer&Information，Hefei University of Technology，Hefei 230009，China）

A time efficient AC algorithm AC-TE is suggested for multiple pattern string matching based on the analysis of AC and related algorithms.The AC-TE algorithm constructs a string shift table and two hash tables.The string shift table stores every adjacent two characters of pattern tree and their positions，while the two hash tables store last two strings and last character of pattern tree respectively.AC-TE uses multiple level skipping rules to check these three constructed tables.As a result，pattern tree’s shift distance can be shortest pattern length pluses 3 without missing matched position. To analyze the performance of the AC-TE algorithm，some experiments are done from three aspects which are pattern tree shift times，matched time and probability of different shift distance.Experimental results show that compared with AC algorithm，AC-TE has longer pattern tree shift distance and better time performance.

multiple pattern matching；AC algorithm；omission；shift distance；pattern tree

劉春暉，黃 宇，宋 琦.一種改進的AC多模式匹配算法［J］.計算機工程，2015，41（10）：280-285.

英文引用格式：Liu Chunhui，Huang Yu，Song Qi.An Improved AC Multiple Pattern Matching Algorithm［J］.Computer Engineering，2015，41（10）：280-285.

1000-3428（2015）10-0280-06

A

TP301.6

教育部廣東省產(chǎn)學(xué)研基金資助項目（2009B090200049）；安徽省自然科學(xué)基金資助項目（11040606M 138）。

劉春暉（1989-），男，碩士研究生，主研方向：網(wǎng)絡(luò)與信息安全，防火墻技術(shù)；黃 宇、宋 琦，碩士研究生。

2014-10-15

2014-11-11E-mail：742233361@qq.com