一種高效的多模式字符串匹配算法

許家銘，李曉東，金 鍵1,，馬 盈

?

一種高效的多模式字符串匹配算法

許家銘1,2,3，李曉東2，金 鍵1,2，馬 盈4

(1. 中國互聯網絡信息中心，北京 100190；2. 中國科學院計算機網絡信息中心，北京 100190；3. 中國科學院大學，北京 100190；4. 東北師范大學理想信息技術研究院，長春 130117)

在Fan-Su(FS)多模式字符串匹配算法基礎上，結合BM-Horspool(BMH)算法和Quick Search(QS)算法的優點，提出一種高效的多模式字符串匹配算法。該算法能夠充分利用本次匹配失敗和部分匹配成功的信息，一方面增加模式樹根節點失配的概率，提高匹配過程中失配時的跳躍距離。另一方面避免不必要的狀態轉移，實現不匹配時的連續跳轉。分析指出，在最好情況和平均情況下，時間復雜度均優于ACBM算法和FS算法。實驗結果表明，一般情況下該算法的查找時間僅為AC算法的10%~35%， ACBM算法的50%~60%，FS算法的70%左右，FSQB算法的65%左右。

字符串匹配；多模式匹配；有限自動狀態機；算法復雜度；網絡安全；信息檢索

1 概述

模式匹配算法在文本挖掘、信息檢索、模式識別、圖像處理以及網絡安全等領域中被普遍采用。隨著互聯網的迅猛發展，巨大的流量承載著各種信息充斥著網絡，如何高效地實現針對信息內容的檢測過濾，成為網絡安全領域的一個關鍵問題，模式匹配算法正是內容檢測的一項關鍵技術。

經典的單模匹配算法主要包括KMP算法[1]、Boyer- Moore(BM)算法[2]、BM-Horspool(BMH)算法[3]以及Quick- Search(QS)算法[4]。其中，KMP算法利用已匹配信息，實現了無回溯的比較，時間復雜度為()(和分別為文本串和模式串的長度)。BM算法是一種經典的跳躍式匹配算法，平均情況下比KMP更快，最好情況下時間復雜度為(/)。BMH算法是對BM算法的簡化實現。QS算法則在BMH算法基礎上進行改進，最好情況下時間復雜度為(/(+1))。

多模式匹配是從文本串[1:]中一次查找多個模式串1,2,…,P，所有模式串構成集合{}。其中，為{}中模式串的數目；為所有模式串長度之和；m為模式串P的長度；為最短模式串的長度；為最長模式串的長度；是字符集；是字符集大小。多模匹配的經典算法主要包括：Aho-Corasick(AC)算法[5]，ACBM算法[6]，FS算法[7]以及FSQB算法[8]。其中，AC算法通過預處理，將多個模式串轉換為樹型有限自動狀態機(DFSA)，對文本串掃描一次就可完成所有模式串匹配，匹配時間復雜度為()。ACBM算法融合了AC算法和BM算法思想，并在開源入侵檢測系統Snort上實現[9]，平均情況下效率優于AC算法，最好情況下時間復雜度為(/)。FS算法將BM算法與DFSA結合并改進，平均情況下效率優于ACBM算法，最好情況下時間復雜度為(/)。FSQB算法則將QS算法與DFSA結合并改進，最好情況下時間復雜度為(/(1))。

雖然ACBM算法、FS算法和FSQB算法在實際應用中表現優異，但仍未能充分利用匹配不成功的信息，導致跳躍距離有限，匹配效率受模式串數目影響較大。本文在FS算法的基礎上，汲取BMH算法和QS算法思想，并提出進一步的改進，充分利用匹配失敗的信息，跳過更多無需比較的字符，避免無用的狀態轉移。

2 相關算法

2.1 BM算法

BM算法的基本思想是從右向左進行逆向匹配。在預處理時構造壞字符表和好后綴表；在匹配時利用壞字符和好后綴啟發性規則，跳過盡量多的字符。算法基本流程如下：首先從0開始，將文本串的第個字符與模式串的左端對齊。然后從與的最右端字符開始匹配，若匹配則向左依次匹配下一字符，直到匹配成功或發生失配。發生失配時，根據情況將向右移動，若失配發生在的最右端字符，則使用壞字符表跳轉，使字符[]與其在中出現的下一位置對齊；若已匹配部分子串并在[]和[]處失配，則使用好后綴表跳轉，使已匹配子串與其在中出現的下一位置對齊。

壞字符表記錄字符在中出現的最靠右位置，定義為：

好后綴表記錄各后綴在中重復出現的最靠右位置，定義如下：

2.2 BMH算法和QS算法

2.3 FS算法

在匹配時采用改進的啟發規則，匹配算法描述如下[7]：

算法1 FS多模匹配算法

輸入文本串[1:],,,1和2函數

輸出模式串在文本中匹配的位置

i = minlen;

state = 0;

while i ≤ n do

begin

if goto(state, T[i]) == 0 then

begin

if state == 0 then

i = i + skip1(T[i]);

else

i = i + skip2(state, T[i]);

state = 0;

end

else

begin

state = goto(state, T[i]);

if output(state) != NULL then

print i;

i = i–1;

end

end

3 改進的快速多模匹配算法

3.1 壞字符規則的改進

在匹配過程中發生失配時，充分利用失配信息，增加模式串跳躍距離，是進一步提高多模式匹配算法效率的關鍵。分析和實驗表明：模式串數目很少時，壞字符規則起主要加速作用，好后綴規則優化效果不明顯；隨著模式串數目的增加，好后綴和單個字符出現的概率逐漸增加，好后綴規則優化效果逐漸增強，壞字符規則優化效果雖明顯減弱，但仍起主要加速作用，如圖1~圖4所示。

圖1 查找時間隨模式串數目變化的情況

圖2 平均比較數隨模式串數目變化的情況

圖3 函數調用隨模式串數目變化的情況

圖4 函數跳轉距離隨模式串數目變化的情況

在圖1~圖4中，文本串為Reuters-21578[11]，模式串選自Wordfrequency網站[12]，模式串長度在11~15之間。

BMH算法和QS算法僅使用壞字符規則，就獲得了很好的效果。但在失配時，BMH算法僅使用字符[]決定右移量，最大為；QS算法僅使用字符[1]決定右移量，最大為1。但隨著{}的增大，各字符在模式串尾部出現的概率也隨之增加，導致2個算法都很難達到最大的右移距離，優化效果有限。

本文在FS算法的基礎上，吸收BMH算法和QS算法思想，對壞字符規則進行改進，使用雙字符[:1]構造壞字符表，同時增加發現壞字符的概率和達到最大右移距離的概率。但只使用雙字符進行跳轉，會使最大右移距離僅為。

具體分析如下：為保證不遺漏任何可能的匹配，固定匹配窗口大小為，當[:1]在{}中出現時，最大右移距離為；當[:1]未在{}中出現時，分為如下2種情況：

(1)字符[1]未在所有模式串靠右端的第個字符中出現時，模式樹可向右移1個字符，使匹配窗口左端與[2]對齊，右端與[1]對齊。

(2)字符[1]出現在某個模式P的最左端，且P的長度為時，模式樹僅能向右移個字符，使匹配窗口左端與[1]對齊，右端與[]對齊。

基于以上分析，改進的壞字符規則將使用單字符[1]和雙字符[:1]共同決定模式樹右移距離，在增加發現壞字符概率和達到最大右移距離概率的同時，使得最大右移距離為1，增加了失配時的平均右移距離，跳過更多無需比較的字符，進一步減少了匹配過程中的比較次數。定義如下：

可分為如下3種情況，其中，12=[:1]：

(1)當2未在模式串集合中出現時，模式樹可右移1，使匹配窗口左端與[2]對齊，右端與[1]對齊。

(2)當2出現在最短模式串集合的最左端時，模式樹可右移，使匹配窗口左端與[1]對齊，右端與[]對齊。

這樣，既保證了右移過程中不會遺漏任何可能的匹配，又提高了發現壞字符和達到最大跳躍距離的概率，獲得了更大的跳躍距離。實際上還可同時考慮更多字符，進一步增加跳躍距離和達到最大跳躍距離的概率。但同時考慮的字符越多，壞字符表所占空間也越大。可使用哈希技術對壞字符表進行壓縮，以降低空間復雜度。

3.2 壞前綴規則

FS算法在某些特殊情況下，效率會迅速下降[2,7]。本文針對其中一種特殊情況進行優化，并結合入侵檢測系統中對報文內容的匹配和過濾進行說明。

對URL和郵箱地址中域名[13]關鍵字的檢索和過濾，是入侵檢測系統的一項主要工作。由于域名命名空間呈倒置的樹形結構，域名字串具有從右到左的層次結構，其不同后綴的數目有限，而不同前綴和主體的數目則很大。具有類似特征的文本和模式集合，將導致算法在發現失配之前，進行許多無用的比較；在發現失配之后，右移跳躍很小的距離；在匹配過程中，對同一字符重復比較多次，導致效率迅速下降。

本文引入壞前綴規則，在發現匹配窗口[1:]內包含長度為的壞前綴時，啟用改進的壞字符規則，跳過更多無需比較的字符。壞前綴表標記集合{}中，所有滿足條件的字符串為true，定義如下：

3.3 改進的匹配算法

由于改進的壞字符規則，考察了當前匹配窗口的下一個字符[1]，因此在匹配部分模式后再發生失配時，壞字符表的跳躍距離就有可能大于好后綴表的跳躍距離，此時應選擇兩者中較大的值作為跳躍距離。另外，在發生失配并跳轉后，當前狀態為模式樹根節點，此時可以利用壞前綴和壞字符表進行連續跳轉，避免不必要的狀態轉移。匹配算法描述如下：

算法2 FSA改進的多模匹配算法

輸入文本串[1:],,,1,2和函數

輸出模式串在文本中匹配的位置

i = minlen;

state = 0;

while !ispref(T[i–minlen+1:i–minlen+d]) || goto(state, T[i]) == 0 do

i = i + skip1(T[i], T[i+1]);

while i ≤ n do

begin

if goto(state, T[i]) == 0 then

begin

if state == 0 then

i = i + skip1(T[i], T[i+1]);

else

begin

t = i + state.depth;

i = i + max{skip1(T[t], T[t +1])+ state.depth, skip2(state, T[i])};

end

state = 0;

while !ispref(T[i–minlen+1:i–minlen+d])||goto (state, T[i]) == 0 do

i = i + skip1(T[i], T[i+1]);

end

else

begin

state = goto(state, T[i]);

if output(state) != NULL then

print i;

i = i – 1;

end

end

示例說明：文本串[1:]為"toldsheignorehererrors"，模式串集合{}為{,,,}，=3，取=2。函數轉移圖如圖5所示。

圖5 反向自動機goto函數轉移

各個函數表如表1~表4所示。匹配過程如表5所示，其中，每一行表示在匹配過程中，當前狀態有輸出或輸入字符失配；方括號內為當前匹配窗口，加粗帶下劃線字符為當前比較字符，斜線表示無值。

表1 output函數表

表2 ispref函數表(d=2)

表3 skip1函數表

表4 skip2函數表(minlen=3)

表5 匹配過程

4 時間復雜度分析

4.1 預處理階段

4.2 匹配階段

其中，()為匹配1個字符所花費的代價；()為從右向左匹配到第1個字符才發生失配的概率；(,)為此時右移距離為的概率。

其中，()意義同上；1()和2()分別為此時使用函數1和2跳轉的概率；1(,)和2(,)分別為此時調用函數1和2右移距離為的概率。

本文算法通過改進壞字符規則，引入壞前綴規則，提高了發現壞字符的概率，減少了發現失配所花費的代價，并在失配時提高了使用1函數跳轉的概率1()和取較大值的概率，向右跳過更多無需比較的字符，使最大右移距離達到1。通過改進匹配算法，在失配時避免不必要的狀態轉移，實現了失配時的連續跳轉，在花費相同的代價下，獲得更多的跳轉?？傊疚乃惴ㄊ勾鷥r函數的分子減小分母增大。平均情況下，本文算法較ACBM算法、FS算法和FSQB算法的時間復雜度更優。

5 實驗分析

為測試本文FSA算法的性能，并與AC算法、ACBM算法、FS算法和FSQB算法進行橫向對比，選取以下6個評價指標進行考察：(1)查找時間。(2)文中單個字符平均比較次數，即算法執行字符比較操作總數除以文本長度。 (3)跳轉函數調用次數，即分別調用函數1和2的次數。(4)跳轉函數跳躍距離，即分別調用函數1和2跳過的總字符數。(5)平均收益，即跳躍距離之和除以比較操作數之和。(6)平均代價，即發現失配所花的代價之和除以跳躍距離之和。

實驗環境如下：Windows 7操作系統，Core i7 3.40 GHz CPU，4 GB內存；AC算法和ACBM算法均選用開源軟件Snort中的實現版本，FS算法、FSQB算法和本文算法均采用C++語言實現。

待匹配文本由路透社的Reuters-21578新聞文本數據集組成，共約28 MB。待匹配模式串集合，從Wordfrequency網站提供的高頻詞匯表中隨機選取。為考察模式串長度和數目對算法性能的影響，模式串按長度分為4個部分，各部分再按照串數目分為8組，各組模式串數目從10~150以20為單位遞增。

表6顯示了不同模式串長度和數目下，FSA算法較其他算法都有更好的性能。

表6 查找時間 ms

與FS算法和FSQB算法相比，FSA算法在模式串較長和模式數較少時，性能改進更多。當模式串長度在1~5之間且模式較少時，FSA算法查找時間僅為AC算法的25%~50%，ACBM算法的60%左右，FS算法的75%左右，FSQB算法的60%~80%。當模式串長度大于6時，FSA算法對性能的改進更大。

在實際應用中，大部分模式串的長度都在6以上[7]。為比較一般情況下算法的平均性能，隨機選取長度在6以上模式串進行實驗測試。

圖6中數據顯示，隨著模式串數目增加，AC算法的查找時間基本穩定，其余算法的查找時間和平均比較操作數，均呈亞線性增長，且增長速率逐漸放緩。其中，模式串長度≥6；FSA算法的查找時間是AC算法的10%~35%，ACBM算法的50%~60%，FS算法的70%左右，FSQB算法的65%左右；平均比較操作數是AC算法的10%~17%，ACBM算法的45%~50%，FS算法的55%左右，FSQB算法的65%左右。

圖6 查找時間和平均比較操作數

在算法執行的過程中，比較操作和狀態轉移是十分耗時的。與FS算法和FSQB算法相比，FSA算法進一步減少了比較操作和狀態轉移，進而在性能上獲得了明顯提升，如圖7、圖8所示，其中，模式串長度≥6。

可以看出，在模式串較少時，FS算法、FSQB算法和FSA算法都有較好的性能，但FSA算法平均代價更低，性能也更加穩定。這是因為在模式串較少時，模式串集合中出現的字符較少，FS算法和FSQB算法跳轉函數的值較大，發現壞字符的概率也較大，1函數的優化作用十分明顯；但隨著模式串數的增加，單個字符出現的概率迅速升高，好后綴出現的概率不斷增加，跳轉函數的值和發現壞字符的概率則迅速減小，1函數的優化作用明顯減弱。然而雙字符出現的概率，及其隨模式串數增加而增加的速率，都要比單字符小得多。因此，FSA算法使用改進的壞字符和壞前綴規則，增加了調用1函數的概率，使1函數在模式串較多時仍具有較大的值，且始終起絕大部分的優化作用，大幅減少了比較操作數。

圖7 壞字符規則和好后綴規則優化效果對比

圖8 平均收益和平均代價

6 結束語

本文將BMH算法和QS算法與FS算法相結合，提出了一種快速的多模式匹配算法。在匹配過程中能夠盡可能多地跳過無需比較的字符，實現了不匹配時的連續跳轉，使匹配效率大幅提高。實驗結果表明，平均情況下本文算法有較好的性能，在各項評價指標上均優于ACBM算法、FS算法和FSQB算法，且對模式串數目的增加不敏感，性能更加穩定。本文算法可應用于多種領域，如入侵檢測、信息檢索等。后續研究工作將在提高匹配效率的基礎上，對算法進行改進，以降低最壞情況下的時間復雜度。

[1] Knuth D E, Morris J H, Pratt V R. Fast Pattern Matching in Strings[J]. SIAM Journal on Computing, 1977, 6(2): 323-350.

[2] Boyer R S, Moore J S. A Fast String Searching Algorithm[J]. Communications of the ACM, 1977, 20(10): 762-772.

[3] Horspool R N. Practical Fast Searching in Strings[J]. Software Practice & Experience, 1980, 10(6): 501-506.

[4] Sunday D M. A Very Fast Substring Searching Algorithm[J]. Communications of the ACM, 1990, 33(8): 132-142.

[5] Aho A V, Corasick M J. Efficient String Matching: An Aid to Bibliographic Search[J]. Communications of the ACM, 1975, 18(6): 333-340.

[6] Walter B C. A String Matching Algorithm Fast on the Ave- rage[C]//Proc. of the 6th International Colloquium on Automata, Languages, and Programming. Graz, Austria: [s. n.], 1979.

[7] Fan Jang-Jong, Su Keh-Yih. An Efficient Algorithm for Matching Multiple Patterns[J]. IEEE Transactions on Knowledge and Data Engineering, 1993, 5(2): 339-351.

[8] 王永成, 沈 州, 許一震. 改進的多模式匹配算法[J]. 計算機研究與發展, 2002, 39(1): 55-60.

[9] Coit C J, Staniford S, McAlerney J. Towards Faster String Matching for Intrusion Detection or Exceeding the Speed of Snort[C]//Proc. of DARPA Information Survivability Conference. [S. l.]: IEEE Press, 2001.

[10]Lecroq T. Experimental Results on String Matching Algorithms[J]. Software Practice & Experience, 1995, 25(7): 727-765.

[11]Lewis D. Reuters-21578 Text Categorization Collection[EB/OL]. (1999-02-16). http://kdd.ics.uci.edu/databases/reuters21578/ reuters21578.html.

[12] Davies M. Word Frequency and Collocates Data[EB/OL]. (2012-04-20). http://www.wordfrequency.info.

[13] Albitz P, Liu C. DNS and BIND[M]. 5th ed. [S. l.]: O’Reilly Media, 2006.

編輯 顧逸斐

An Efficient Multiple Patterns String Matching Algorithm

XU Jia-ming1,2,3, LI Xiao-dong2, JIN Jian1,2, MA Ying4

(1. China Internet Network Information Center, Beijing 100190, China; 2. Computer Network Information Center, Chinese Academy of Sciences, Beijing 100190, China; 3. University of Chinese Academy of Sciences, Beijing 100190, China; 4. Ideal Research Institute of Information Technology, Northeast Normal University, Changchun 130117, China)

Combined with the advantages of BM-Horspool(BMH) algorithm and Quick-Search(QS) algorithm, an effective algorithm to perform multiple patterns matching in a string is proposed on the concept of Fan-Su(FS) algorithm. To reduce the number of comparisons, and improve the efficiency of matching, the proposed algorithm skips as many characters as possible and avoids useless state transitions, by making full use of the successful and failing information during the matching. Experimental results show that the proposed algorithm can achieve more excellent performance than the ACBM algorithm and FS algorithm. The time it takes for the proposed algorithm to search a string is only 10%~35% of the AC algorithm, 50%~60% of the ACBM algorithm, 70% of the FS algorithm, and 65% of the FSQB algorithm.

string matching; multiple patterns matching; finite state automata; algorithm complexity; network security; information retrieval

1000-3428(2014)03-0315-07

A

TP301.6

國家自然科學基金資助項目“多模態Web作弊間的統計機器學習方法研究”(61005029)。

許家銘(1987－)，男，碩士研究生，主研方向：網絡安全，下一代互聯網技術；李曉東，研究員；金 鍵，高級工程師；馬 盈，碩士研究生。

2013-01-15

2013-03-13 E-mail：xujiaming@cnnic.cn

10.3969/j.issn.1000-3428.2014.03.067