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

劉春暉，黃 宇，宋 琦

（合肥工業大學計算機與信息學院，合肥 230009）

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

劉春暉，黃 宇，宋 琦

（合肥工業大學計算機與信息學院，合肥 230009）

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

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

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

1 概述

隨著互聯網技術的發展，模式匹配技術被廣泛應用于生物醫學［1］、網絡搜索引擎［2］、內容過濾防火墻［3］、入侵檢測系統［4］等領域，成為信息領域中重要的研究方向之一。

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

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

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

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

2 AC及其改進算法

2.1 AC算法

2.1.1 預處理階段

預處理階段構建有限狀態自動機并計算轉移函數和輸出函數。

（1）構建有限狀態自動機

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

圖1 有限狀態自動機

（2）計算轉移函數

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

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

（3）計算輸出函數

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

2.1.2 匹配過程

匹配過程的步驟如下：

（1）文本串指針P指向文本串首字符，當前狀態s=0。

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

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

（4）s=failure（s），轉步驟（3）。

2.2 AC改進算法

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

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

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

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

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

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

3 AC-TE算法

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

3.1 算法設計思想

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

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

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

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

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

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

圖2 匹配窗口

3.2 算法步驟

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

（1）預處理階段

1）構建模式樹。

2）創建字符串跳躍表（String Shift Table，SST），記作SST。

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

算法1創建字符串跳躍表SST

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

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

表1 SST表

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

算法2創建LTST

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

表2 LTST表

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

算法3創建LCT表

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

表3 LCT表

（2）匹配階段

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

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

算法4計算移動距離

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

3.3 AC-TE算法分析

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

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

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

3.3.2 預處理階段時空復雜度

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

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

3.3.3 匹配階段時間復雜度

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

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

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

4 實驗與結果分析

實驗環境：Window s 8.1系統，因特爾Core Dual-Core 1.5 GHz，3 GB內存。

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

（1）模式樹移動次數

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

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

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

圖4 固定模式串數量時的模式樹移動次數

（2）匹配階段時間

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

圖5 改變模式串數量所用時間

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

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

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

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

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

5 結束語

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

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

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

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

［4］ 蔣建春，卿斯漢.網絡安全入侵檢測：研究綜述［J］.軟件學報，2000，11（11）：1460-1467.

［5］ 盧開澄.計算機算法導引-設計與分析［M］.北京：清華大學出版社，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］ 陸琳琳，田 野.基于確定有限狀態自動機的改進多模式匹配算法研究［J］.計算機應用與軟件，2013，30（7）：322-326.

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

［14］ 董世博，李訓根.一種改進的字符串多模式匹配算法［J］.計算機工程與應用，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

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

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

2014-10-15

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