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

?

改進(jìn)的K步長多模式匹配算法

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

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

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

0　引言

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

1　K步長匹配算法

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

2　改進(jìn)方法

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

2.1改進(jìn)思想

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

{

}

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

{

{

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

{

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

}

}}

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

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

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

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

參考文獻(xiàn)

[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òng)機(jī)的多模式匹配算法研究[D].合肥工業(yè)大學(xué),2011.

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