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

杭州電子科技大學(xué)電子信息學(xué)院　焦鵬飛　李訓(xùn)根

?

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

杭州電子科技大學(xué)電子信息學(xué)院焦鵬飛李訓(xùn)根

【摘要】K步長狀態(tài)機存在失效函數(shù)，一部分存儲空間被用來存儲失效狀態(tài)。為了提高K步長狀態(tài)機的空間性能，該文通過K步長狀態(tài)機的轉(zhuǎn)移函數(shù)和失效函數(shù)f構(gòu)建了新的轉(zhuǎn)移函數(shù)，消除了K步長狀態(tài)機的“失效鏈”。對改進算法進行性能分析表明，模式串?dāng)?shù)量和長度越大，改進后算法的空間優(yōu)化效果越明顯。

【關(guān)鍵詞】多模式匹配；K步長狀態(tài)機；失效鏈

0　引言

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

1　K步長匹配算法

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

2　改進方法

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

2.1改進思想

定義：M為按步長K將模式串分割后組成的集合；Q表示用來存放狀態(tài)機中狀態(tài)的隊列；狀態(tài)轉(zhuǎn)移函數(shù)表示：當(dāng)前狀態(tài)為s，輸入狀態(tài)為a，則當(dāng)前狀態(tài)會轉(zhuǎn)移到。

{

}

while Q≠empty //遍歷Q中的所有狀態(tài)

{

{

圖1　改進后的 K 步長狀態(tài)機及狀態(tài)存儲結(jié)構(gòu)

{

//狀態(tài)s移入隊列Q

}

}}

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

3　算法性能和結(jié)果分析

測試環(huán)境：Windows 7操作系統(tǒng)，CPU為Intel T6670 2.20G，內(nèi)存為4.00GB的個人PC機。搜索文本為VC6.0隨機生成的20.4M的英文文本。令K=4，選取50到200條長度在5到30字節(jié)之間的模式串，與原始的K步長算法進行比較。測試結(jié)果如表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]舒銀東.基于有限狀態(tài)自動機的多模式匹配算法研究[D].合肥工業(yè)大學(xué),2011.

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