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

王同軍，趙培君

（信陽農林學院 河南 信陽 464000）

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

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

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

1 BM及其改進算法

1.1 Boyer-Moore算法分析

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

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)，則應選擇 i=max{k|P[k]=T[i+j]，0≤k≤m-1}，使得P[i]與 T[i+j]對齊。

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

1.2 Boyer-Mooer-Horspool算法分析

1980年，Horspool發(fā)表了改進與簡化BM算法的論文，即BMH算法。該算法將失配與計算右移量獨立，計算右移量先判斷T[j+m-1]是否等于P[m-1]，若相等則繼續(xù)比較T[j+m-2]和 P[m-2]，如此循環(huán)下去，直到當 T[j]=P[0]時，則發(fā)現(xiàn)一個成功的匹配；若中間比較到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]中不存在匹配字符，模式直接向右移動m位；

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

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

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

2 改進算法（BMX算法）

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

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

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

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

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

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

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

表1 BM算法移動過程Tab.1 Transformation in BM algorithm

表2 BMX算法移動過程Tab.2 Transformation in BMX algorithm

3 算法的性能測試及結果分析

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

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

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

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

4 結束語

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

[1]王浩，張霖.基于壞字符序檢測的快速模式匹配算法[J].計算機應用與軟件，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]揚子江，聶瑞華.一種快速的單模式匹配算法[J].華南師范大學學報：自然科學版，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]王浩，張霖，張慶.基于雙字符序檢測的BM模式匹配改進算法[J].計算機工程與科學，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]張娜，張劍.一個快速的字符串模式匹配改進算法[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]揣錦華，鄭景，關銳.BM模式匹配算法的研究與改進[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預測和點模式匹配的多目標跟蹤[J].現(xiàn)代電子技術，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.