一種提高模式匹配速度的新方法

王同軍，趙培君

（信陽(yáng)農(nóng)林學(xué)院 河南 信陽(yáng) 464000）

字符串的模式速匹配是串處理的一種很重要的運(yùn)算，它一直都是計(jì)算機(jī)科學(xué)領(lǐng)域研究的熱點(diǎn)問(wèn)題之一。字符串的模式匹配在眾多領(lǐng)域被廣泛的應(yīng)用，如：拼寫(xiě)檢查、搜索引擎、計(jì)算機(jī)病毒特征碼匹配、入侵檢測(cè)、P2P應(yīng)用特征識(shí)別、圖像處理、數(shù)據(jù)壓縮以及DNA序列匹配等，都離不開(kāi)模式匹配算法[1]。

所謂模式匹配就是在大量的文本串中查找模式串（一個(gè)給定的字符串）的一個(gè)或者多個(gè)匹配的過(guò)程。對(duì)于文本串T[0，1，2…n-1，]，長(zhǎng)度為 n；模式串 P[0，1，2…m-1]，長(zhǎng)度為 m，其中m≤n。如果在文本串T中找到模式串P，則表示匹配成功否則匹配失敗[2]。

單模式匹配算法主要有KMP算法、RK算法、BM算法[3]及相關(guān)改進(jìn)算法等。其中，基于BM改進(jìn)的BMH算法[4]、BMHS算法[5]是目前實(shí)際應(yīng)用中效率較高的一類單模式匹配算法。國(guó)內(nèi)外學(xué)者近年來(lái)在單模式匹配算法及其BM算法的改進(jìn)研究方而取得了豐碩成果，相關(guān)論文主要以BMH和BMHS算法作為研究和實(shí)驗(yàn)對(duì)比分析對(duì)象。基于BMH或BMHS算法的大部分改進(jìn)算法均利用各類降低匹配窗口移動(dòng)次數(shù)和增加匹配窗口移動(dòng)最大距離的啟發(fā)式方法來(lái)改善算法效率[6]。本文從模式串首字母的唯一性及字符在模式串中出現(xiàn)的概率為突破點(diǎn)，提出了一種新的基于首字符檢測(cè)的BM模式匹配改進(jìn)算法。該算法吸收了BMG[7]和BMHS等相關(guān)改進(jìn)算法的優(yōu)點(diǎn)，顯著提高了最大移動(dòng)距離。

1 BM及其改進(jìn)算法

1.1 Boyer-Moore算法分析

該算法采用了兩種啟發(fā)性方法[8]：“壞字符啟發(fā)性方法（Bad char）” 和“好后綴啟發(fā)性方法（Good suffix）”。 在匹配過(guò)程中模式串P[0，1，2…m-1]由左向右移動(dòng)，而字符的比較卻自右向左進(jìn)行，即按照 P[m-1]，P[m-2]，…，P[0]的次序進(jìn)行比較，當(dāng)文本中的字符與模式完全相等時(shí)，則匹配成功；若不匹配時(shí)，則根據(jù)預(yù)先定義的偏移函數(shù)Bad char和Good suffix計(jì)算出偏移量。

1）壞字符啟發(fā)性方法：若匹配失敗發(fā)生在T[i+j]≠P[i]，且T[i+j]不出現(xiàn)在模式串P中，則將模式右移直到P[1]位于匹配失敗位T[i+j]的右邊第一為（即 T[i+j+1]）；若T[i+j]在P中有若干地方出現(xiàn)，則應(yīng)選擇 i=max{k|P[k]=T[i+j]，0≤k≤m-1}，使得P[i]與 T[i+j]對(duì)齊。

2）好后綴啟發(fā)性方法：如果在模式中P[m-j]處發(fā)現(xiàn)不匹配，則已有0個(gè)或多個(gè)字符后綴P[m-j+1]…P[m-1]匹配，在模式串中查找其他相同子串的位置，選取較大的一個(gè)作為滑動(dòng)值。

1.2 Boyer-Mooer-Horspool算法分析

1980年，Horspool發(fā)表了改進(jìn)與簡(jiǎn)化BM算法的論文，即BMH算法。該算法將失配與計(jì)算右移量獨(dú)立，計(jì)算右移量先判斷T[j+m-1]是否等于P[m-1]，若相等則繼續(xù)比較T[j+m-2]和 P[m-2]，如此循環(huán)下去，直到當(dāng) T[j]=P[0]時(shí)，則發(fā)現(xiàn)一個(gè)成功的匹配；若中間比較到P[i]和T[i+j]發(fā)現(xiàn)不相等，T[i+j+1…j+m-1]已比較完畢且等于 P[i+1…m-1]，則在 P[0…m-2]中看是否存在匹配字符，分兩種情況：

1）若P[0…m-2]中不存在匹配字符，模式直接向右移動(dòng)m位；

2）發(fā)現(xiàn) P（k）=T[j+m-1]（0≤k≤m-2）則，模式串右移 m-1-k位，接著繼續(xù)從右向左開(kāi)始新一輪的比較。

1.3 Boyer-Mooer-Horspool-Sunday算法分析

1990年，Sunday在BMH算法的基礎(chǔ)上又提出了改進(jìn)算法BMHS算法。該算法的思路是：在計(jì)算壞字符啟發(fā)性方法時(shí)。根據(jù)文本串中與模式串末位對(duì)齊的字符的下一位字符的出現(xiàn)情況來(lái)確定移動(dòng)距離。當(dāng)比較進(jìn)行到文本串j位置，失配發(fā)生在T[i+j]與P[i]處。只使用T[j+m]決定右移量，當(dāng)下一個(gè)字符T[j+m]不在模式串中出現(xiàn)時(shí)。它的右移量比BMH算法的右移量大，BMHS算法右移m+1位。BMH算法只能右移Badchar[j+m-1]位置，即便是T[j+m-1]不出現(xiàn)在模式串中也最多移動(dòng)m位。所以通常情況下，BMHS算法比BMH算法移動(dòng)快，但當(dāng)T[j+m-1]不出現(xiàn)在模式串中，而T[j+m]卻出現(xiàn)在模式中時(shí)，即當(dāng) Badchar[j+m-1]>Badchar[j+m]時(shí)，BMHS算法的效果就不如BMH算法。

2 改進(jìn)算法（BMX算法）

根據(jù)以上對(duì)BM算法匹配過(guò)程的分析，結(jié)合其他幾個(gè)改進(jìn)的BM算法（如BMH算法、BMHS算法）的優(yōu)點(diǎn)，提出一種新的BMX算法。該算法主要是考慮了字符串后一位字母及模式串首字符的唯一性。通過(guò)其唯一性，使得最大位移量能夠達(dá)到m+x，繼而能大大提高匹配的效率。

其主要的思路是：當(dāng)T[i+j]≠P[i]時(shí)，表示這一輪匹配失敗，然后觀察T[j+m]位在模式串中是否出現(xiàn)且是否唯一。

1）若T[j+m]位在模式串中出現(xiàn)且唯一，則按照BMG算法的結(jié)論將模式串右移m+1位；若T[j+m]在模式串中出現(xiàn)多次，則按照BMH算法的計(jì)算方法來(lái)確定右移量；

2）若T[j+m]位在模式串中未出現(xiàn)，則表明T[j+m]位與模式串中任何一位匹配都不會(huì)成功，則繼續(xù)觀察T[j+m+1]與P[0]是否相等；

3）若相等，則因T[j+m]不在模式串中，直接跳過(guò)該位將T[j+m+1]與P[0]對(duì)齊進(jìn)行新一輪的比較，右移量為m+1位；

4）若不相等，因 T[j+m]不在模式串中出現(xiàn)，T[j+m+1]與P[0]不相等，表明模式串右移m+1位進(jìn)行匹配也不會(huì)成功；則可繼續(xù)觀察 T[j+m+2]與 P[0]是否相等，重復(fù)（3）、（4）的步驟，直到匹配成功為止，其最大位移量可到達(dá)m+x。

將表1和表2對(duì)比可以看出，對(duì)于相同的字符串，BM算法匹配了7次才匹配成功，模式串的最大位移為m，且m僅出現(xiàn)過(guò)2次，即在整個(gè)匹配過(guò)程中，最大位移出現(xiàn)的概率小于百分之三十。而B(niǎo)MX算法只匹配了4次就能匹配成功，模式串的位移量為m+3、m+2、m+1，且出現(xiàn)的概率為百分之百。不難看出，BMX算法無(wú)論是在最大位移量還是在最大位移量出現(xiàn)的概率上，都大大優(yōu)越于BM算法。

表1 BM算法移動(dòng)過(guò)程Tab.1 Transformation in BM algorithm

表2 BMX算法移動(dòng)過(guò)程Tab.2 Transformation in BMX algorithm

3 算法的性能測(cè)試及結(jié)果分析

本實(shí)驗(yàn)使用的硬件為：處理器Intel Pengtium（R）D CPU 2.80 GHz，內(nèi)存 2GB，軟件為Windows7 32位操作系統(tǒng)，Microsoft Visual C++2010集成開(kāi)發(fā)環(huán)境。采用C語(yǔ)言編程，實(shí)驗(yàn)采用大小為10 MB的英文文本內(nèi)容作為文本串，隨機(jī)取模式串50個(gè)，長(zhǎng)度為3-30字符，算法比較次數(shù)統(tǒng)計(jì)通過(guò)在程序中增加變量實(shí)現(xiàn)。在匹配不同長(zhǎng)度的模式串的情況下，4種算法的字符匹配次數(shù)（見(jiàn)圖1），完成匹配所需時(shí)間（見(jiàn)圖2）對(duì)比測(cè)試結(jié)果如下圖所示。

圖1 字符匹配次數(shù)Fig.1 Number of character matching

圖2 完成匹配所需時(shí)間Fig.2 Time needed to complete the matching

從上述實(shí)驗(yàn)結(jié)果可以看出，四種算法在模式串長(zhǎng)度一樣的條件下，無(wú)論是字符的匹配次數(shù)還是完成匹配所需的時(shí)間，BMX算法的性能明顯好比其他3種算要好很多。

4 結(jié)束語(yǔ)

模式匹配[9]算法效率高低由相關(guān)算法的移動(dòng)距離來(lái)決定，本文通過(guò)對(duì)比分析BM及其改進(jìn)算法的最大移動(dòng)距離和匹配字符的順序，利用壞字符和模式串首字符唯一性的特點(diǎn)，增大了模式串的移動(dòng)距離，較低了匹配次數(shù)。通過(guò)對(duì)算法的分析和實(shí)驗(yàn)證明，該算法能夠有效地增加模式串的右移量，大幅度提高匹配速度，降低匹配時(shí)間。

[1]王浩，張霖.基于壞字符序檢測(cè)的快速模式匹配算法[J].計(jì)算機(jī)應(yīng)用與軟件，2012， 29（5）:114-116.WANG Hao，ZHANG Lin.Quick pattern matching algorithm based on bad character sequence checking[J].Computer Applications and Software，2012，29（5）:114-116.

[2]揚(yáng)子江，聶瑞華.一種快速的單模式匹配算法[J].華南師范大學(xué)學(xué)報(bào)：自然科學(xué)版，2013，45（5）:31-35.YANG Zi-jiang，NIE Rui-hua.A fast single-pattern match algorithm[J].Journal of South China Normal University：Natural Science Edition，2013，45（5）:31-35.

[3]Boyer R S，Moore JS.A Fast String Searching Algorithm[J].Communications of the ACM，1977（20）:762-772.

[4]Horspool R N.Practical Fast Searching in Strings[J].Software Practice&Experience，1980，10（6）:501-506.

[5]Sunday D M.A Very Fast Substring Search Algorithm[J].Communication of the ACM，1990，33（8）:132-142.

[6]王浩，張霖，張慶.基于雙字符序檢測(cè)的BM模式匹配改進(jìn)算法[J].計(jì)算機(jī)工程與科學(xué)，2012，34（3）:113-117.WANG Hao，ZHANG Lin，ZHANG Qing.An improved BM pattern matching algorithm based on double character sequence checking[J].Computer Engineering&Science，2012，34（3）:113-117.

[7]張娜，張劍.一個(gè)快速的字符串模式匹配改進(jìn)算法[J].微電子學(xué)與計(jì)算機(jī)，2007，24（4）:102-105.ZHANG Na，ZHANG Jian.A fast improved algorithm for pattern matching in string[J].Microelectronics&Computer，2007，24（4）:102-105.

[8]揣錦華，鄭景，關(guān)銳.BM模式匹配算法的研究與改進(jìn)[J].電子設(shè)計(jì)工程，2012，20（19）:52-54.CHUAIJin-hua，ZHENGJing，GUAN Rui.Study and improve of BM pattern matching algorithms[J].Electronic Design Engineering，2012，20（19）:52-54.

[9]馬英輝，高磊，徐效文.基于Kalman預(yù)測(cè)和點(diǎn)模式匹配的多目標(biāo)跟蹤[J].現(xiàn)代電子技術(shù)，2013（14）：27-30.MA Ying-hui，GAO Lei，XU Xiao-wen.Multi-object tracking based on Kalman filtering prediction and point matching algorithm[J].Modern Electronics Technique，2013（14）：27-30.