BM模式匹配算法的研究和改進(jìn)

揣錦華，鄭 景，關(guān) 銳

（長(zhǎng)安大學(xué) 信息工程學(xué)院，陜西 西安 710064）

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

所謂模式匹配就是在大量的文本串中查找模式串（一個(gè)給定的字符串）的一個(gè)或者多個(gè)匹配的過程。對(duì)于文本串為T=T0T1…Tn－1，長(zhǎng)度為 n；模式串 P=P0P1…Pm－1，長(zhǎng)度為 m。 如果在T中找到P的出現(xiàn)則表示匹配成功，否則匹配失敗。

關(guān)于模式匹配的算法有很多，比較著名的有2個(gè)：KMP算法和Boyer－Moore算法[1]（簡(jiǎn)稱BM算法）。其中 KMP算法實(shí)現(xiàn)較為復(fù)雜，且效率有限。相比之下，Boyer－Moore算法實(shí)現(xiàn)更為簡(jiǎn)單，且在英文文本及模式較長(zhǎng)的情況下，其效率一般是KMP算法的3～5倍，因此其應(yīng)用更為廣泛。

目前對(duì)于BM算法的改進(jìn)算法有很多，但大體上改進(jìn)都很有限，且穩(wěn)定性并不盡如人意。下面將會(huì)對(duì)經(jīng)典BM算法，以及目前比較流行的兩種改進(jìn)的BM算法進(jìn)行簡(jiǎn)單的介紹，然后提出2點(diǎn)改進(jìn)意見。旨在提升其效率的同時(shí)極大的提高其穩(wěn)定性，最后通過具體的實(shí)驗(yàn)進(jìn)行比較、驗(yàn)證。

1 現(xiàn)有的BM系列算法簡(jiǎn)介

1.1 經(jīng)典BM算法

經(jīng)典 BM（Boyer－Moore）算法[1]的基本思想是：開始時(shí)，將文本串T（長(zhǎng)度為n）與模式串P（長(zhǎng)度為m）左對(duì)齊，然后從模式串的最后一個(gè)字符Pm－1開始，從右至左依此與文本串的相應(yīng)字符 Tm－1Tm－2…T0進(jìn)行比較；當(dāng)某次比較 Ti與 Pi不匹配時(shí)，模式串向右滑動(dòng)一段距離后 k，開始執(zhí)行由 Pm－1與 Ti+k－1起，從右至左的匹配檢查，依此類推直到找到一個(gè)完整匹配或者全文搜索完畢為止。

經(jīng)典BM算法在每次的比較匹配失敗后會(huì)采用兩種啟發(fā)式規(guī)則來決定下一次匹配的位置 （即向右移動(dòng)的距離），即：壞字符規(guī)則（BadChar）和好后綴規(guī)則（GoodSuffix）：

1）好后綴規(guī)則（GoodSuffix）

在BM算法從右向左掃描的過程中，若發(fā)現(xiàn)某個(gè)字符不匹配的同時(shí)，已有部分字符匹配成功，則按如下2種情況討論：

①如果在P中位置t1處已匹配部分P′在P中未匹配部分的某位置t2也出現(xiàn)，且位置t2的前一個(gè)字符與位置t1的前一個(gè)字符不相同，則將P右移，使t2對(duì)應(yīng)t1方才所在的位置。

②如果在P中任何位置已匹配部分P′都沒有再出現(xiàn)，則找到與P′的后綴P″相同的P的最長(zhǎng)前綴x，向右移動(dòng)P，使x對(duì)應(yīng)方才P″后綴所在的位置。

即：P中的已匹配部分或已匹配部分的后綴子串Ps+1…Pm與P中尚未進(jìn)行比較部分中的某一子串Pj-s+1…Pm-s相同，則P右移s位。如公式（1）所示。其中Shift（j）為P右移的距離，m為模式串P的長(zhǎng)度，j為當(dāng)前所匹配的字符位置，s為t1與t的距離（以上情況1）或者x與P″的距離（以上情況2）。

2）壞字符規(guī)則（BadChar）

在BM算法從右向左掃描的過程中，若發(fā)現(xiàn)某個(gè)字符x不匹配，則按如下兩種情況討論：

①如果字符x在模式P中沒有出現(xiàn)，那么從字符x開始的m個(gè)文本顯然不可能與P匹配成功，直接跳過該區(qū)域即可。

②如果x在模式P中出現(xiàn)，則以該字符進(jìn)行對(duì)齊。

設(shè) dest（x）為 P右移的距離，m為模式串 P的長(zhǎng)度，max（x）為字符x在P中最右位置，數(shù)學(xué)公式表示公式（2）所示。

BM算法使用上述壞字符規(guī)則和好后綴規(guī)則計(jì)算得到的移動(dòng)值中的大者來向右移動(dòng)模式P到新的比較位置。實(shí)踐證明在大字母表（相對(duì)于模式長(zhǎng)度）情況下，BM算法效率非常高。

1.2 BMH算法

在實(shí)際應(yīng)用中，BM算法的BadChar應(yīng)用次數(shù)遠(yuǎn)遠(yuǎn)超過GoodSuffix，BadChar在匹配過程中起到移動(dòng)指針的主導(dǎo)作用。因此在實(shí)際應(yīng)用中，只使用BadChar也非常有效。為此，1980年Hompool提出了BM算法的簡(jiǎn)化改進(jìn)算法，即BMH算法[2]。

BMH算法的基本思想是：將匹配失敗與計(jì)算右移量獨(dú)立。計(jì)算右移量時(shí)不關(guān)心文本中哪個(gè)字符匹配失敗，而是直接使用與模式串最右端的字符對(duì)齊的那個(gè)文本字符Ti+m-1在模式串P中出現(xiàn)的位置來決定右移量。此時(shí)其移動(dòng)距離可由上述公式1求得，只不過此時(shí)公式中的x變成了Ti+m-1而已。即移動(dòng)距離為dest（Ti+m-1）。所以當(dāng)Tm+i-1不在模式串中出現(xiàn)時(shí)，模式串獲得最大移動(dòng)距離m。

1.3 BMHS算法

1990年，Sunday在BMH算法的基礎(chǔ)上又提出了一種改進(jìn)的算法—BMHS算法[3]，其主要的改進(jìn)思想是：在一次匹配失敗時(shí)，考慮下一個(gè)字符Tm+j的情況。即利用與模式串P對(duì)齊的文本字串的下一個(gè)字符Tm+j來決定右移量的大小。如果Tm+j不在模式串中出現(xiàn)時(shí)。則直接跳過該字符，即將模式串P可以達(dá)到最大的移動(dòng)距離m+1。如果Tm+j出現(xiàn)在模式串中，則將該字符在模式串P中最右側(cè)出現(xiàn)的位置與文本中的字符Tm+j對(duì)齊，然后進(jìn)入下一次匹配。即移動(dòng)距離skip=m-last（Tm+j）。 當(dāng) last（Tm+j）=-1，即 Tm+j不在模式串中出現(xiàn)時(shí)，模式串獲得最大移動(dòng)距離m+1。

試驗(yàn)表明，一般情況下BMH以及BMHS算法比BM算法有更好的性能[4-5]。

2 改進(jìn)的IBMH（Im proved BMH）算法

2.1 IBMH算法的思想

從上述算法可以看出，BMH只考慮了文本串T一次匹配的最后一個(gè)字符Ti+m-1在模式串P中出現(xiàn)的情況，而BMHS算法則只考慮了文本串的一次匹配的下一個(gè)字符Ti+m在模式串P中出現(xiàn)的情況。二者都有一個(gè)共同的缺點(diǎn)，就是如果文本串的比較字符在模式串P中多次出現(xiàn)時(shí)，二者沒有太大的差別，且效率也沒有太大的提高。

根據(jù)對(duì)以上算法的分析，結(jié)合BM、BMH算法和BMHS算法的優(yōu)點(diǎn)，在考慮失配位置字符產(chǎn)生的最大移動(dòng)距離dest1的同時(shí)，考慮字符串最后一個(gè)字符及其下一字符的組合特性所產(chǎn)生的最大移動(dòng)距離dest2。最終移動(dòng)距離為二者中的最大者。

當(dāng)發(fā)生失配時(shí)，若模式失配位置為i，文本串失配位置為j，失配字符為c。則由失配字符引導(dǎo)的最大移動(dòng)距離dest1如下所示：

dest2由BMH以及BMHS的組合決定，即通過Ti+m-1Ti+m在模式串P中是否出現(xiàn)以及出現(xiàn)的位置決定。為此我們可以定義函數(shù)dest2（c1c2），用于計(jì)算有字符串Ti+m-1Ti+m所確定移動(dòng)距離。其定義如下所示。

最終移動(dòng)距離skip=max{dest1，dest2}。一種拿空間換時(shí)間的做法能夠更有效地提高改算法的效率，即對(duì)于給定的模式串P，在開始匹配之前將字母表中的所有c的dest1的值都計(jì)算出來并放在一張表中，在使用時(shí)就可以直接從表里面取，這樣就省去了很多的計(jì)算操作。

2.2 BM算法的復(fù)雜度分析

由上文所述可知，BM、BMH、BMHS、IBMH算法的最大移動(dòng)量分別是m、m、m+1、m+1。影響模式匹配算法效率的除了最大移動(dòng)量外還有產(chǎn)生最大移動(dòng)量的概率和窗口比較次數(shù)等。對(duì)于BM、BMH及BMHS算法，它們的最大移動(dòng)量均發(fā)生在一次匹配的末位字符或者其下一個(gè)字符在模式串中未出現(xiàn)的情況下。而對(duì)于IBMH算法，其最大移動(dòng)量發(fā)生在這兩個(gè)字符的組合串在模式串中未出現(xiàn)的情況下。顯然，兩個(gè)字符的組合串在模式串中出現(xiàn)的概率要比一個(gè)字符在模式串中出現(xiàn)的概率低很多。因此IBMH算法獲得最大移動(dòng)距離的概率要比其他幾種算法的概率大很多。

盡管在最壞情況下，BM算法的時(shí)間復(fù)雜度均為O （nm+|Σ|）。但是BM算法是平均時(shí)間復(fù)雜度可以達(dá)到O（m+n+|Σ|）[6]。可見，在最好情況下，BM算法的時(shí)間復(fù)雜度將是低于線性的。在實(shí)際應(yīng)用中，BM算法往往能夠跳過很大一部分文本。此外，由于IBMH算法在進(jìn)行失配跳躍時(shí)不僅考慮了還未進(jìn)行比較的字符出現(xiàn)的情況，還將已經(jīng)完成的匹配結(jié)果考慮了進(jìn)去，因此其穩(wěn)定性方面較其他幾種算法也有很大提高。

3 實(shí)驗(yàn)測(cè)試及結(jié)果比較

實(shí)驗(yàn)環(huán)境為Windows XP Professional操作系統(tǒng)，系統(tǒng)的配置為Intel P4 CPU 2.8 GHz，內(nèi)存 512M，編譯器采用Microsoft Visual C++6.0。4種算法均用C語言編寫，實(shí)驗(yàn)采取5.05 MB的英文文本內(nèi)容作為正文串。

試驗(yàn)主要對(duì)上述4種算法在進(jìn)行匹配時(shí)的模式串移動(dòng)次數(shù)、字符的比較次數(shù)以及同樣進(jìn)行10 000次匹配所花費(fèi)的時(shí)間進(jìn)行了采集，采集后的比較結(jié)果分別如圖1～3所示：（其中橫軸為模式串字符個(gè)數(shù)，圖1縱軸為模式串移動(dòng)次數(shù)，圖2縱軸為字符比較次數(shù)，圖3縱軸為完成1萬次匹配所耗費(fèi)時(shí)間，單位為ms）

圖1 模式串移動(dòng)次數(shù)Fig.1 Number of pattern string moves

圖2 字符比較次數(shù)Fig.2 Number of character comparisons

從上述實(shí)驗(yàn)結(jié)果可以看出，在同等條件下，4種算法在模式串移動(dòng)次數(shù)、字符比較次數(shù)、以及完成1萬次匹配所用運(yùn)行時(shí)間上，IBMH算法在大多數(shù)情況下其性能明顯要比其他3種算法要好很多，尤其是在穩(wěn)定性方面，IBMH算法要比其他算法更加穩(wěn)定。

圖3 10000次匹配所用運(yùn)行時(shí)間Fig.3 Time-consuming of 10000 times match

4 結(jié)束語

目前對(duì)于BM算的改進(jìn)算法有很多，且各有特點(diǎn)。在對(duì)不同文本模式進(jìn)行匹配時(shí)也有各自的優(yōu)勢(shì)。文中在對(duì)已有的3種BM算法的研究的基礎(chǔ)上提出了兩點(diǎn)改進(jìn)意見，并通過實(shí)驗(yàn)驗(yàn)證表明：該改進(jìn)算法在性能及穩(wěn)定性上確實(shí)有一定的提高。因此，在模式匹配算法的應(yīng)用領(lǐng)域中，該算法也必將能帶來更好的性能。

[1]Boyer R S，Moore J S.A fast string searching algorithm[J].Communications of the ACM，1977，20（10）：762.

[2]Nigel H R.Practical fast searching in strings[J].Software-Practice and Experience，1980，10（6）:501－506.

[3]Daniel M S.A very fast substring search algorithm[J].Communications of the ACM，1990，33（8）:132－142.

[4]楊薇薇，廖翔.一種改進(jìn)的BM模式匹配算法[J].計(jì)算機(jī)應(yīng)用，2006，26（2）：318－319.YANG Wei-wei，LIA0 Xiang.Improved pattern matching algorithm of BM[J].Computer Applications，2006，26（2）:318－319.

[5]袁靜波，鄭吉森，丁順利.一種BM模式匹配算法的改進(jìn)[J].計(jì)算機(jī)工程與應(yīng)用，2009，45（17）：105－107.YUAN Jing-bo，ZHENG Ji-sen，DING Shun-li.Improvement of BM pattern matching algorithm[J].Computer Engineering and Applications，2009，45（17）:105－107.

[6]古德里奇，塔瑪西亞.算法分析與設(shè)計(jì)[M].霍紅衛(wèi)，譯.人民郵電出版社，2006.