張玉新，李成海，白瑞陽

（空軍工程大學(xué) 防空反導(dǎo)學(xué)院，西安 710051）

一種改進(jìn)的單模式匹配算法

張玉新，李成海，白瑞陽

（空軍工程大學(xué) 防空反導(dǎo)學(xué)院，西安 710051）

0 引言

網(wǎng)絡(luò)已成為人們生活、學(xué)習(xí)、生產(chǎn)等諸多領(lǐng)域不可缺少的一部分，但是由于諸多的因素造成了網(wǎng)絡(luò)安全問題的頻發(fā)，在網(wǎng)絡(luò)高速化的時(shí)代，如何從大量數(shù)據(jù)中提取特定的信息，顯得十分重要。模式匹配就是給定字符串T和S，其中字符串T稱為正文，字符串S稱為模式，要求在正文T中找到模式S是否出現(xiàn)。

模式匹配可以分為單模式匹配和多模式匹配，其中單模匹配有著名的BF算法、BM算法、BMH算法、KMP算法，文獻(xiàn)[1]提出的快速單模式匹配算法(FSBM)充分利用已匹配的后綴和字符串后一位字符的信息,已達(dá)到在每一次跳躍中跳躍盡量大的距離，文獻(xiàn)[2]利用模式字符串中存在重復(fù)字符串來獲得最大的移動(dòng)距離。多模匹配有AC算法，AC-BM算法，文獻(xiàn)[3,4]也提出了相關(guān)的一些改進(jìn)。其中Snort2.9中應(yīng)用的就是單模匹配和多模匹配算法。本文重點(diǎn)以單模式匹配為研究內(nèi)容，并結(jié)合傳統(tǒng)的一些匹配算法如BM算法、BMH算法、Sunday(QS)算法，給出一種改進(jìn)后的單模式匹配算法。

1 單模式匹配

單模式匹配算法是指在文本串T=t1t2t3…tn中一次只對一個(gè)模式P=p1p2p3…pn進(jìn)行匹配。

1.1 BF算法

模式匹配最簡單的做法是用模式串P的字符依次與文本串T作對比，這就是BF算法的思想，是最早最簡單的單模匹配算法，其特點(diǎn)是直觀簡單，圖1為BF算法匹配過程。

圖1 BF算法匹配過程

如果p1=t1,p2=t2,p3=t3,p4=t4,…,pm=tm，則表明匹配成功，如果中間有一位匹配不成功，則右移一位從頭再次開始匹配，直到匹配成或移到文本串最右端結(jié)束匹配過程。從匹配過程可以看出指向文本串的指針在一次匹配失敗的情況下，執(zhí)行下次匹配的時(shí)候指針需要返回再次重頭開始，涉及多次回溯，最糟糕的情況下，每一次比較到最后才出現(xiàn)匹配成功，則一次比較需要m次，匹配完成最多需要n-m+1趟，通常n≥m，所以時(shí)間復(fù)雜度為Q(n*m)，算法效率極低。

1.2 BM及BMH算法

BM算法的基本思想是：模式串P以左對齊的方式，從右往左依次和文本串進(jìn)行匹配，發(fā)生匹配失敗時(shí)使用壞字符和好后綴中的最大值實(shí)現(xiàn)最大右移步長。壞字符原則，即一次匹配過程中出現(xiàn)匹配失敗ti1Pj，當(dāng)ti能夠在模式串P中找到，將出現(xiàn)在P中最右端的ti右移與文本串中的ti對齊進(jìn)行下一次匹配，當(dāng)ti不能夠在模式串P中找到，將模式串P右移的距離為已連續(xù)匹配的字符數(shù)。好后綴原則，當(dāng)模式串P的后綴中有子串與文本串T已匹配，模式串P可以右移的距離為子串的長度，當(dāng)模式串P的后綴中有子串與文本串T已匹配且模式串前綴中有子串與以匹配后綴子串相同，將前綴子串與后綴子串右移對齊，實(shí)現(xiàn)一次右移。BM算法的匹配過程如圖2所示。

圖2 BM算法的匹配過程

第1次匹配時(shí)p7=t7,p8=t8且模式串中p4p5=p7p8，采用后后綴原則，第2次匹配和第4次匹配均采用壞字符原則，第3次匹配p6p7p8=t11t12t13采用好后綴原則實(shí)現(xiàn)左移。

在模式匹配中，壞字符產(chǎn)生的概率占94.03%，遠(yuǎn)大于好后綴啟發(fā)規(guī)則，BMH算法就是在匹配時(shí)只考慮壞字符啟法規(guī)則，在大部分情況下，BMH算法的性能要優(yōu)越于BM算法。BMH算法的思想是首先匹配模式串末尾所對應(yīng)文本串的字符，若果匹配成功則再匹配其余的m-1位字符。只要文本串T中的任何字符造成匹配失敗，都將由文本中和模式串最后一個(gè)位置對應(yīng)的字符來啟發(fā)模式向右的移動(dòng)。BMH算法的最大右移距離為m。BMH算法匹配過程如圖3所示。

圖3 BMH算法匹配過程

1.3 QS算法

Sunday提出的QS算法，任然只采用了壞字符規(guī)則，與BMH不同的是QS算法在匹配過程中考慮與模式串T對齊的最后一個(gè)字符的下一個(gè)字符，最大跳躍距離為m+1。

當(dāng)發(fā)生不匹配時(shí)，QS算法用下一個(gè)字符來計(jì)算右移量，即使用T[i+l]，當(dāng)該字符不出現(xiàn)在模式串中時(shí)，可以直接跳過T[i+1]，右移距離比BMH大，但當(dāng)T[i+l]在模式串中出現(xiàn)時(shí)，而T[i]不在模式串中出現(xiàn)時(shí)，這時(shí)右移距離BMH要大于QS算法，QS效率就不如BMH了。

2 改進(jìn)的一種算法

2.1 算法思想

受BMH和QS的啟發(fā)，結(jié)合二者的優(yōu)點(diǎn)提出一種改進(jìn)的匹配算法。該算法的基本思想是：采用模式串P與文本串T左對齊，匹配時(shí)從右向左匹配。定義i（i=1，2，…，n）為指向文本串T的指針，j（j=1，2，…，m）為指向模式串的指針。改進(jìn)的算法也采用QS算法中與模式串T對齊后的下一個(gè)字符T[i+m]位，依據(jù)T[i+m]位生成壞字符表，同時(shí)利用連續(xù)的兩組字符T[i+m-1]T[i+m]和T[i+m]T[i+m+1]生成右移距離表。

2.2 匹配過程

首次匹配時(shí)由T[i+m]位生成壞字符表，如果T[i+m]不在模式串P中按照QS算法思想模式串將會(huì)右移m+1位；若T[i+m]在模式串P中能夠找到，計(jì)算連續(xù)的T[i+m-1]T[i+m]和T[i+m]T[i+m+1]兩個(gè)字符是否在模式串中有連續(xù)出現(xiàn)的，兩組連續(xù)的子串只要有一個(gè)出現(xiàn)就將模式串P中最右端中出現(xiàn)的子串右移與其中跳躍距離最大的對齊，即跳躍距離=max{( T[i+m-1]T[i+m]),( T[i+m]T[i+m+1])}，如果T[i+m-1]T[i+m]和T[i+m]T[i+m+1]直接跳過T[i+m-1]T[i+m]和T[i+m]T[i+m+1]，此時(shí)跳躍距離可達(dá)m+2。圖4是改進(jìn)算法的匹配過程。

圖4 改進(jìn)算法的匹配過程

在第一次匹配中可以看出T[9]=P[3]，且T[8]T[9]=P[2]P[3]，T[9]T[10]=T[3]T[4]，二者右移距離都為2，將模式串P右移2位；第二次匹配T[15]=P[8]，且T[14]T[15]=P[1]P[2]，T[15]T[16]在模式串P中沒有找到對應(yīng)的子串，模式串P右移7位；依次在第4次完成整個(gè)匹配。

從上圖4可以看出，整個(gè)匹配過程主需要循環(huán)4次就可以完成，該算法同時(shí)獲得了較大的移動(dòng)距離，提高了匹配效率，從圖2、圖3的對比中可以發(fā)現(xiàn)該算法在某些情況下比BM算法、BHM算法匹配速度更快。

3 實(shí)驗(yàn)結(jié)果及結(jié)論

本實(shí)驗(yàn)在windows XP，Pentium Dual-Core E5800，2GB RAM環(huán)境下對BM算法，BMH算法、QS算法和改進(jìn)的算法分別編程測試，在一篇純英文文章153KB，149829個(gè)字符的情況下，以4、6、8、12長度的模式串進(jìn)行測試得到如圖5匹配比較次數(shù)和圖6匹配經(jīng)歷時(shí)間所示的結(jié)果。從圖中比較次數(shù)和運(yùn)行時(shí)間可以看出改進(jìn)后的算法具有一定的優(yōu)越性。

圖5 匹配比較次數(shù)

圖6 匹配經(jīng)歷時(shí)間

4 結(jié)束語

改進(jìn)后的匹配算法通過實(shí)驗(yàn)證實(shí)提高了匹配效率，在網(wǎng)絡(luò)數(shù)據(jù)高速增長的時(shí)代，只有高效的算法才能勝任實(shí)時(shí)入侵檢測的需求，本文提出的改進(jìn)算法為下一步在入侵檢測中的應(yīng)用奠定了基礎(chǔ)。

[1]王天聰,侯整風(fēng),何玲.基于BM的模式匹配改進(jìn)算法[J].合肥工業(yè)大學(xué)學(xué)報(bào),2011,34(3):363-366.

[2]丁國強(qiáng),趙國增,李傳鋒.改進(jìn)BM算法策略的網(wǎng)絡(luò)入侵檢測系統(tǒng)設(shè)計(jì)[J].計(jì)算機(jī)測量與控制,2011,11(19):2661-2664.

[3]汪永進(jìn),顧乃杰,任開新.一種按字長匹配的Wu－Manber多模式匹配算法[J].小型微型計(jì)算機(jī)系統(tǒng),2013,34(7):1650-1653.

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

[5]張宇,劉萍,劉燕兵,譚建龍,郭莉.對模式串匹配算法WuManber的復(fù)雜度攻擊[J].計(jì)算機(jī)研究與發(fā)展,2011,48(8):1381-1389.

[6]嵩天,李冬妮,汪東升,薛一波. 存儲(chǔ)有效的多模式匹配算法和體系結(jié)構(gòu)[J]. 軟件學(xué)報(bào),2013,24(7):1650-1665.

[7]王英,左祥麟,左萬利,王鑫. 基于本體的Deep Web查詢接口集成[J]. 計(jì)算機(jī)研究與發(fā)展,2012,49(11):2383-2394.

[8]梁棟,朱明,唐俊,范益政,顏普. 基于局部相對形狀上下文與Q-譜的點(diǎn)模式匹配算法[J].電子學(xué)報(bào),2012,40(4):636-641.

[9]朱映映,吳錦鋒,明仲. 基于網(wǎng)絡(luò)事件和深度協(xié)議分析的入侵檢測研究[J].通信學(xué)報(bào),2011,32(8):171-178.

[10]Tan GM, Liu P, Bu DB et al. Revisiting multiple pattern matching algorithms for multi-core architecture[J].Journal of computer science and technology,2011,26(5):866-874.

[11]Dong Liang,PuYan,MingZhu, Yizheng Fan, Kui Wang.Spectral matching algorithm based on nonsubsampled contourlet transform and scale-invariant feature transform[J]. Journal of Systems Engineering and Electronics,2012,23(3):453-459.

[12]李艷鵾,付維娜,劉帥,祝明. 并行系統(tǒng)中KMP串匹配算法的實(shí)現(xiàn)[J].制造業(yè)自動(dòng)化,2011,33(1):189-191.

[13]梁威,葉猛. 海量數(shù)據(jù)過濾系統(tǒng)中匹配算法的研究[J].電視技術(shù),2013,37(1):87-90.

[14]侯寶劍,謝飛,胡學(xué)鋼,劉應(yīng)玲,王海平. 基于后綴樹的帶有通配符的模式匹配研究[J].計(jì)算機(jī)科學(xué),2012,39(12):177-180,194.

[15]朱西講.一種改進(jìn)的BM算法在網(wǎng)絡(luò)安全控制中應(yīng)用[J].科技通報(bào),2012,28(6):49-51.

Improved single pattern matching algorithm

ZHANG Yu-xin, LI Cheng-hai, BAI Rui-yang

模式匹配算法在病毒特征碼檢測、入侵檢測、生物信息等諸多領(lǐng)域有著廣泛的應(yīng)用，如何提高匹配的效率是制約模式匹配算法的決定因素，本文通過分析傳統(tǒng)的模式匹配算法提出一種改進(jìn)的單模式匹配算法，通過對比分析和驗(yàn)證，該算法提高了匹配效率。

模式匹配；BM算法；BMH算法

張玉新（1990 -），男，甘肅民樂人，碩士研究生，研究方向?yàn)榫W(wǎng)絡(luò)信息安全。

TP393.08

A

1009-0134(2014)06(上)-0015-03

10.3969/j.issn.1009-0134.2014.06(上).04

2014-03-08

國家自然科學(xué)（61272486）