改進的K步長多模式匹配算法

杭州電子科技大學電子信息學院　焦鵬飛　李訓根

?

改進的K步長多模式匹配算法

杭州電子科技大學電子信息學院焦鵬飛李訓根

【摘要】K步長狀態機存在失效函數，一部分存儲空間被用來存儲失效狀態。為了提高K步長狀態機的空間性能，該文通過K步長狀態機的轉移函數和失效函數f構建了新的轉移函數，消除了K步長狀態機的“失效鏈”。對改進算法進行性能分析表明，模式串數量和長度越大，改進后算法的空間優化效果越明顯。

【關鍵詞】多模式匹配；K步長狀態機；失效鏈

0　引言

網絡通信的高速發展使得網絡安全防范顯得愈加重要，模式匹配成為當前的研究熱點。K步長算法的設計原理是基于Aho-Corasick狀態機，以下簡稱AC狀態機。AC狀態機的匹配步長是每次一個字符，而K步長狀態機則是每次K個，如果不考慮其他因素，K步長狀態機性能是AC狀態機的K倍。但是K步長狀態機存在失效函數，一部分存儲空間被用來存儲失效狀態。當模式串集合中出現長度很長的模式串時，則可能出現失效鏈很長的情況，在為存儲轉移表分配空間時，只能以失效鏈最長的那條記錄為參照開辟空間。基于K步長狀態機存儲方面的這個缺陷，本文提出了一種消除失效鏈的改進K步長多模式匹配算法。

1　K步長匹配算法

K步長算法生成狀態機過程如下：把待匹配的模式串按照從左向右的順序，順次分割成若干個長度一樣的、包含K個字符的單元，如果最后少于K個字符，則補齊通配符*當作K個字符處理；分割完畢，參照AC狀態機的生成方法，生成K步長狀態機。K步長狀態機產生失效函數f、轉移函數goto和輸出函數output。表示當前狀態為s，輸入狀態為a，則當前狀態會轉移到；表示當前狀態為s，當匹配失敗時，當前狀態會轉移到；表示當前狀態為s，輸入狀態為a，匹配成功，輸出狀態為p。goto函數、f函數、output函數經過整合，得到狀態機的狀態轉移表。

2　改進方法

K步長匹配算法不僅要對尾部的字符進行單獨處理，而且還存在“失效鏈”。當模式串集合中出現長度很長的模式串時，則可能出現失效鏈很長的情況，在為存儲轉移表分配空間時，只能以失效鏈最長的那條記錄為參照開辟空間，這無疑很大地浪費了有限的存儲資源。為了降低存儲空間，本文對K步長狀態機的轉移函數進行了重定義，生成消除了“失效鏈”的K步長狀態機。

2.1改進思想

定義：M為按步長K將模式串分割后組成的集合；Q表示用來存放狀態機中狀態的隊列；狀態轉移函數表示：當前狀態為s，輸入狀態為a，則當前狀態會轉移到。

{

}

while Q≠empty //遍歷Q中的所有狀態

{

{

圖1　改進后的 K 步長狀態機及狀態存儲結構

{

//狀態s移入隊列Q

}

}}

由以上分析可以得到，改進算法的空間優化率q與模式串長度n以及模式串數目m成正比。當m=200，n=30時，節省的內存開銷能夠達到11%左右。實際上，隨著模式串數量和模式串長度的繼續增大，改進算法的空間優化效果將更加明顯。

3　算法性能和結果分析

測試環境：Windows 7操作系統，CPU為Intel T6670 2.20G，內存為4.00GB的個人PC機。搜索文本為VC6.0隨機生成的20.4M的英文文本。令K=4，選取50到200條長度在5到30字節之間的模式串，與原始的K步長算法進行比較。測試結果如表1所示。

表1　算法空間性能比較　　單位：MB

參考文獻

[1]Dharmapurikar S,Lockwood J.Fast and scalable pattern matching for content filtering. In:Berenbaum A,ed. Proc.of the 2005 Symp.on Architecture for Networking and Communications Systems.New York:ACM Press,2005. 183-192.

[2]舒銀東.基于有限狀態自動機的多模式匹配算法研究[D].合肥工業大學,2011.

[3]王培鳳,李莉.基于Aho-Corasick算法的多模式匹配算法研究[J].計算機應用研究,2011,04:1251-1253+1259.