模式匹配ＢＭ算法改進

摘 要:研究BM串匹配算法，分析國內外各種改進算法，結合其優缺點，增加對模式串串末字符或壞字符的鄰接字符在模式串中的首次出現位置、存在性、惟一性的判斷。根據判斷的結果對移動距離重新設置，增加模式串移動距離，減少字符重復比較的次數，以提高匹配效率。

關鍵詞:串匹配; 末字符; 壞字符; 鄰接字符; 惟一性; 存在性

中圖分類號:TP301.6文獻標志碼:A

文章編號:1001-3695(2009)09-3249-04

doi:10.3969/j.issn.1001-3695.2009.09.013

Improved algorithm for BM string matching

ZHANG Hong-mei， FAN Ming-yu

(School of Computer Science Engineering， University of Electronic Science Technology of China， Chengdu 610054， China)

Abstract:This paper researched algorithm for BM string matching. Analyzed kinds of improved algorithms. On the basis of the advantage of these algorithms， the first position， judged the existence and the uniqueness of the neighbor character of the end character or the bad character of the string. By the result of these judges， increased the new shift distance， reduced the times of the match， and enhanced the efficiency of string matching.

Key words:string match; end character; bad character; neighbor character; uniqueness; existence

0 引言

串匹配是文本挖掘、文獻檢索、搜索引擎、IP路由查找、模式識別、圖像處理以及入侵檢測技術等普遍采用的技術策略之一。串匹配算法是系統性能改進中極為重要的部分，系統性能的好壞取決于匹配算法及其實現的效率。學者們已提出大量串匹配算法，如Knuth等人[1]構造出KMP 算法， Boyer等人 [2]于1977 年設計出BM算法。在這些常用的字符串匹配算法中，KMP和BM算法是其中較為著名的兩種算法。這兩種算法在最壞情況下均具有線性的查找時間，KMP算法匹配從左向右進行，移動距離不可能大于一次匹配操作所進行的字符比較次數;而BM算法匹配從右向左進行，當模式串P的末字符P[m]與對應的正文串T中的字符T[i+m]進行比較時，若T[i+m]在模式串P中并不存在，則模式串可以一次向右移動m個字符，使模式串只經一次比較就可以移動模式串的長度，這使BM比KMP算法更快。在實用上，BM要比KMP算法快3~5倍。

本文分析BM算法及其各種相關改進算法，結合其優點對BM算法作出新的改進。針對壞字符在模式串中出現的惟一性，壞字符的前驅以及壞字符在正文串中對應字符的后繼字符在模式串中的存在性，模式串末字符是否為模式串串首字符，以及壞字符與其后繼字符在模式串中是否存在同樣的子串進行分析，作出進一步的改進。

1 BM算法及其相關改進算法

1.1 BM算法原理

BM算法設置如下初始條件:

正文串T={T[0]，T[1]，T[2]，…，T[n]}

模式串P={P[0]，P[1]，P[2]，…，P[m]}

字符集Σ=a，b，…，z

其中:n>m，需要從T中查找出與P完全匹配的子串，并返回該子串在正文串的首字符的位置。

BM算法原理如下:在正文串T第i個位置開始與模式串P第0個位置對齊，從右往左進行比較。首先比較模式串P末字符P[m]與正文串T對應字符T[i+m]是否相匹配。一旦發現不匹配，通過查找預處理好的壞字符移動表Badchar與好后綴移動表GoodBuffer，對所得到的結果進行比較，用移動距離較大值向后移動模式串P的嘗試位置。其中壞字符移動表用式(1)，好后綴移動表用式(2)求出。

Badchar[c]=m+1;c!=P[j];0≤j≤mm-j;j=max{j|P[j]=c;0≤j≤m}(1)

GoodBuffer[i+1]=mins|s>0，i

s

雖然BM算法執行效率較高，由于沒有考慮好后綴與壞字符之間的前驅后繼關系，使得算法在總體上效率不高，仍可以有更多的改進。目前就有多種對BM算法的改進，如BMG、SBM、BMH、IMBM等算法。

1.2 分析已有的BM改進算法

1.2.1 BMH算法

Nigel[3]提出BMH算法。BMH算法在匹配過程中不管壞字符在哪個位置，只根據與模式串P末字符對應的字符在模式串中出現最大的位置來移動模式串，進行下一輪匹配;而未考慮T[m+1]在模式串中是否存在，以及T[m+1]與T[m]在模式串P中的前驅后繼性以及T[m+1]是否在模式串P的串首等特性。以下是匹配比較過程。

1.2.2 BMG算法

文獻 [4]提出BMG算法。該算法結合BMH和BMHS算法的特點，考慮模式串末字符的惟一性，以及串末字符與其對應的正文串字符的后繼字符在模式串中的位置差別。當出現多次時，只是將模式串移動最小距離，而沒有考慮到該字符在串中出現但是其后繼與前驅字符并不一起出現。如果在模式串中并不存在該字符與其后繼前驅的子串，則可以直接跳過，減少匹配次數。

1.2.3 SBM算法

文獻[5]中提出一種面向入侵檢測的BM模式匹配改進算法。采用對模式串從兩邊向中間進行匹配。但對匹配未成功的字符進行移動時，只考慮末字符的對應正文串中字符的后繼字符，沒有考慮該末字符在模式串中的位置以及末字符對應正文串中字符的后繼字符在模式串中的位置相關性。由于在語言中每個字符出現的幾率一樣，從兩邊向中間匹配和從右往左匹配效率相當。該算法針對串匹配中如果存在特殊情況，即模式串為“aabaa”正文串為 “aaaaaaaaaaaaa”時，算法的復雜度與BM算法針對模式串為“baaaa”正文串為 “aaaaaaaaaaaaa”時匹配次數一樣。

1.2.4 PBM算法

文獻[6]中提出了PBM算法，其基本思想是:在長為m的模式串P中找出一個最長的前綴子串subp，k是subp長度，n是正文串的長度，令該子串的末字符Pk為模式串所有字符中最后一個首次出現的字符，根據subp末字符Pk的惟一性，確定Pk在正文T中每次出現的位置，并對Pk的位置加以標注，在正文T中僅就每兩個被標注的相鄰Pk之間長度不小于subp的字段，對subp進行模式匹配。若subp匹配成功，則對模式P余下的部分endp=P-subp進行匹配;若匹配不成功，則在正文T中尋找下兩個相鄰的被標注的Pk之間長度不小于subp的長度的字段，這樣模式P從正文中每次滑過的字段長度不小于subp的長度。

PBM算法的時間復雜度為(qmn/k+mn(l-q))。PBM算法在對最長前綴進行匹配時，只查找一個表即可得到模式串的移動值;而BM算法在匹配過程中需要查找兩個表并對這兩個查找值進行比較取其中的較大值。因此，每次在向后移動模式串時，PBM都要比BM算法少查一次表，同時少作一次比較。PBM算法的匹配最長前綴時計算出來的移動值不小于BM算法的移動值，從而減少了匹配時間。

此算法只是對模式串預處理時構造末字符僅出現一次，但對該前綴模式子串subp的匹配并未采用任何改進。對模式串P滿足末字符只出現一次的情況下，該算法僅僅是BM算法，效率顯然低下。而且在自然語言中模式串P末字符只出現一次的情況很普遍，因此需要對subp的匹配中采取更有效的算法。

1.2.5 其他改進算法

文獻[7]中提出一種新的BM改進算法，算法時間復雜度為O(m(n-m))。該算法與BM算法的結構基本相同，在原有模式串移動的基礎上，通過對模式串與正文串匹配時比較模式串末字符的下一個字符對應的正文串字符在模式串中出現的位置，加速了在匹配失敗后向后跳躍的幅度，減少了比較次數，提高了運算效率。但該算法并未對模式串末字符以及壞字符的惟一性及是否為首字符的特性進行判斷。假設如下:

文本串:perfeceed searching example

模式串:search

這里根據判斷字符“c”不在模式串中，查看“c”的后繼字符“e”，“e”在模式串中，但“e”并非模式串首字符，因此若按照“e”在模式串中的位置來確定模式串往后移動的距離顯然要多比較和移動一些次數。這里可以根據查看“e”在模式串中存在，但“e”不是模式串首字符，因此模式串可以跳過m+2的距離。

以下是匹配比較過程。

文本串:perfected searching example

模式串:search

a)對齊文本串和模式串，從右向左比較。第一次匹配從文本串第六個字符處開始比較，發現不匹配，需要把模式串往后移動。改進后的算法是根據緊跟在當前子串之后的那個字符“t”獲得位移量，而“t”沒有出現在模式串“search”中，則按照skip[i]=m+1可以直接跳過6+1的距離，從“c”之后的那個字符開始作下步的比較。

文本串:perfected searching example

模式串:search

b)從“a”開始比較，又不匹配，再看其后的字符“c”，它在子串中出現在第四位，按照skip[p[i]]=m-i，把子串向右移動6-3位，使得兩個“r”對齊，因此，整個匹配過程移動兩次模式串就找到了匹配位置。在查找階段的時間復雜度為O(m(n-m))。但是該算法并未對模式串末字符對應的正文串中的字符的后繼字符以及模式串壞字符的惟一性進行判斷，如在以下情況。

2 本文對BM算法的改進

2.1 算法改進

2.1.1 算法改進要點

1)末字符不匹配

當模式串字符與正文串字符從右向左進行匹配，若串末字符與正文串對應字符不匹配，不是查看模式串末字符對應正文串字符的后繼字符是否在模式串中，而是查看與模式串串末字符對應正文串中字符的后繼字符是否是模式串串首字符。

2)后綴匹配

當模式串字符與正文串字符從右向左進行匹配時，有部分匹配后，匹配如下:

a)查看模式串的末字符對應正文串中字符的后繼字符是否在模式串中。

b)查看好后綴是否存在僅出現一次的字符。

c)查看還未匹配的模式串前綴是否存在僅出現一次的字符。

d)查看壞字符的前驅、后繼字符以及末字符對應的正文串字符的前驅后繼字符在模式串中是否有其他位置出現。

2.1.2 算法實現要點

算法實現中包括以下兩個步驟:

a)預處理

計算字符集中每個字符在模式串P中首次出現的位置，若不存在則為-1，若存在，則記錄其位置;計算模式串P={P[0]，P[1]，…，P[m]}中每個字符首次出現的位置first[P[i]](i為0~m);計算模式串中每個字符在模式串中出現的次數，time[i](i為0~m);計算在模式串中出現不只一次的字符個數num;計算模式串中每個在串中出現不只一次字符的前驅和后繼字符數組:front[i][]，next[i][](i為0~m)。

b)匹配過程

針對該改進算法進行如下七個步驟:

(a)初始化。首先定義變量tlen、plen，表示模式串和正文串的長度;定義變量num用于統計在模式串中出現不只一次的字符個數;定義循環變量i用于進行正文串與模式串的起始位置對齊;定義循環變量j用于模式串字符匹配;定義數組time[]用于存儲每個字符在模式串中出現次數;定義變量onlyOne用于統計已匹配好的字符中存在僅出現一次的字符個數;定義max用于表示已匹配好字符中僅出現一次字符的最大序號。

(b)判斷i的值，若i>tlen-plen+1，則失敗退出;否則初始化j=m，max=0，onlyOne=0。正文串字符T[i+j]與模式串字符P[j]進行比較。若匹配，則j--;且判斷time[j]是否等于1。如果等于1，則取出該已匹配好的字符中只出現一次的字符的最大序號，并且統計只出現一次字符的個數，即if(time[j]==1){max=(j>max?j:max);onlyOne+=1}。

(c)循環(b)，直到T[i+j]與P[j]不相等。

(d)判斷j的值，若j=-1，則匹配成功，返回i值。若j=m，則判斷后繼字符T[i+m+1]是否為模式串串首字符;若是，則i=i+m+1，返回(b);否則，i=i+m+2，返回(b)。若0

(e)若onlyOne≥1，即已匹配好的字符僅出現一次的個數存在。若有，則i=i+max+1，返回(b);否則，繼續(f)。

(f)判斷num-onlyOne是否大于0，即判斷還未進行比較的模式串前部分是是否存在模式串中僅出現一次的字符。若num-onlyOne大于0，判斷字符T[i+m+1]是否是模式串首部。若是，則i=i+m+1，j=0，返回(b);否則，i=i+m+2，j=0，返回(b)。若num-onlyOne等于0，繼續(g)。

(g)判斷壞字符T[i+j]的前驅后繼字符以及T[i+m]的前驅是否在P[j]與P[m]的相應位置上，并根據其位置進行移動，返回(b)。實際匹配流程如圖1所示。

2.2 算法實現關鍵

a)計算模式串P={P[0]，P[1]，…，P[m]}每個字符在模式串中的首次出現位置first[P[i]]，如式(3)所示:

first[P[i]]=min{j|P[i]=P[j]，0≤i，j≤m，i≠j}(3)

b)計算字符集E={}中每個字符在模式串中的首次出現位置first[x]，如式(4)所示:

first[x]=-1 x不在P中jx在P中，j=mini|P[i]=x，0≤i≤m(4)

c)計算模式串中每個字符出現的次數time[i]，如式(5)所示:

time[i]=time[i]+1{k|P[i]=P[k]，0≤k≤m，i≠k} time[i]{k|P[i]≠P[k]，0≤k≤m，i≠k} (5)

d)計算字符在模式串中出現大于1次的字符個數num，如式(6)所示:

num=num+1若first[P[i]]≠i;0≤i≤mnum若first[P[i]]=i;0≤i≤m(6)

e)計算模式串中每個出現不只一次的字符的前驅和后繼字符front[][]、next[][]，如式(7)所示:

front[first[P[i]]][time[i]]={first[P[j-1]]，…} next[first[P[i]]][time[i]]={first[P[j+1]]，…}j=min{j|P[j]=P[i]，0≤j≤m，time[i]>1}(7)

若前驅或后繼不存在，則記為-1。

f)匹配過程中關鍵函數find(first[T[i+m]，first[T[i+m+1]]，first[T[i+m-1]])表示從字符T[i+m]的后繼字符數組和前驅字符數組中查找是否有字符T[i+m+1]、T[i+m-1]，并返回它的位置。

3 實驗對比分析

實驗采用Windows XP操作系統，編譯器采用Microsoft Visual C++6.0，算法所耗CPU周期使用C庫函數clock()所得。實驗采取100MB全英文文本內容作為正文串，查找其模式串所需用時比較。表1是各種算法對文本匹配時間(ms)的比較。

從表1中可以看出，各種改進算法均在原有的BM算法中作了一些改進，但是本文改進算法更加有效地減少了匹配次數，提高了模式匹配的速度。同時可以看出，在文本長度固定時，算法的執行時間隨著需要匹配的模式串長度的增加相應地縮短，也可以看出，當模式串足夠長時，其匹配時間相差不大，但都比BM算法耗時少，而本文算法相對有明顯優勢。

4 改進算法復雜度分析

4.1 改進算法匹配過程

模式串為“ebampamp”正文串為“nowenbmpeawbeebampamp”針對其進行模式匹配，匹配過程如表2所示。該算法首先匹配到“a”與“b”不匹配，查看末字符對應正文串中字符的后繼字符“e”是否在模式串中存在，查看末字符的前驅“p”和后繼“e”在模式串中是否存在，計算它們的移動距離k1;查看壞字符的前驅后繼在字符串中是否存在，計算它們的移動k2，比較其大小，若不相等，則取最大移動距離。

4.2 預處理時間復雜度

first[P[i]]，time[i]時間復雜度均為O(1/2 m2);num，front[P[i]]，next[P[i]]時間復雜度均為O(m);預處理總的時間復雜度為O(m2)。

4.3 匹配過程時間復雜度

該算法有三種特殊情況如下:設正文串長n、模式串長m、除去預處理時間。若正文串為“aaaaaaaaaa”模式串為“baaaa”，其時間復雜度為O(n+1-(n/m))，若正文串為“aaaaaaaaaaaa”模式串為“aabaa”，其時間復雜度為O(n-(m-1)/2)。模式串存在相同子串如正文串為“tepaepatpatpaepatp”，模式串為“aepaep”。其中最壞情況是存在相同的子串，且首尾相接存在循環。其匹配過程如表3所示。

由分析得知，最壞情況下移動m/k個距離，需要比較m/k-1次;移動m個距離，需要比較m-1次，時間復雜度為O(n)。根據預處理時間復雜度和匹配過程的時間復雜度，整個算法時間復雜度為O(n)+O(m2)。當n很大，且n遠大于m2預處理時間復雜度可忽略不計。first[P[i]]，time[i]，front[P[i]]，next[P[i]空間復雜度均為O(m)?？偟目臻g復雜度為4×O(m)，而實際上模式串的長度不會太長，所以預處理的時間和空間的開銷與串匹配相比均可以忽略不計。

5 結束語

算法分析以及實驗結果表明，該算法最大特點是利用字符串中壞字符、末字符、及其后繼字符的存在性、惟一性、它們的前驅后繼關系、好后綴字符的惟一性、未比較前綴字符的惟一性來增加其移動距離，提高匹配速度。改進后的算法在模式串長遠遠小于正文串長時，以及模式字符串中字符或子字符串重復出現較少的情況下，其效率明顯提高。針對模式串中存在重復較多以及循環的情況下，該算法仍可以大大提高其匹配速度。

參考文獻:

[1]KNUTH D E，MORRIS J H，PRATT V R. Fast pattern matching in string[J]. SIAM Journal on Computing， 1977，20(6):323-350.

[2]BOYER R S， MOORE J S. A fast string searching algorithm[J].Communications of ACM，1977，20(10):762 -772.

[3]HORSPOOL R N. Practical fast searching in strings[J]. Software-Practice and Experience，1980(10):501-506.

[4]張娜，侯整風.一種快速的BM模式匹配改進算法[J].合肥工業大學學報:自然科學版，2006，29(7):834-838.

[5]徐成，孫偉，戴爭輝，等.一種面向入侵檢測的BM模式匹配改進算法[J].計算機應用研究， 2006，23(11):89-91.

[6]李志清.基于模式匹配和協議分析的入侵檢測系統研究[D].廣州:廣東工業大學， 2007.

[7]孫寧.入侵檢測系統中模式匹配算法的研究[D].西安:西安科技大學，2008.

[8]冉占軍.基于模式匹配和協議分析的入侵檢測系統研究[D]. 西安:西安理工大學，2008.

[9]王建國，鄭家恒.BM串匹配算法的一個改進算法[J]. 計算機工程與科學，2007，29(5):94-95.

[10]巫喜紅，凌捷.BM模式匹配算法剖析[J]. 計算機工程與設計，2007，28(1):29-30.

[11]王琢，趙永哲，姜占華.網絡處理模式匹配算法研究[J].計算機應用研究，2007，24(12):310-312.