模式匹配BM算法改進(jìn)探討

徐政超

摘 要：研究了BM字符串匹配的算法，并提出了改進(jìn)算法。借助這些算法的優(yōu)點(diǎn)，可以判斷結(jié)束字符、相鄰字符的存在和唯一性，或者字符串不合理的字符。這些判斷結(jié)果增加了新的移動(dòng)距離，減少了匹配的次數(shù)，并提高了字符串匹配的效率，對(duì)模式識(shí)別的高效發(fā)展具有深遠(yuǎn)的意義和價(jià)值。

關(guān)鍵詞：BM算法；模式匹配；字符匹配；字符串

中圖分類號(hào)：G354 文獻(xiàn)標(biāo)識(shí)碼：A DOI：10.15913/j.cnki.kjycx.2017.06.059

1 BM算法概述

在計(jì)算機(jī)科學(xué)中，Boyer-Moore字符串搜索算法是一種高效的字符串搜索算法，是實(shí)際字符串搜索文獻(xiàn)的標(biāo)準(zhǔn)基準(zhǔn)，它是由Robert S. Boyer和J Strother Moore在1977年開發(fā)的。算法預(yù)處理搜索字符串，但不處理正在搜索的字符，因此，它非常適合于其中模式比文本短得多或在多個(gè)搜索中持續(xù)存在的應(yīng)用程序。Boyer-Moore算法使用在預(yù)處理步驟期間收集的信息來(lái)跳過(guò)文本的部分，導(dǎo)致比許多其他字符串搜索算法具有更低的常數(shù)因子。

2 BM算法的原理

Boyer-Moore算法通過(guò)在不同比對(duì)中執(zhí)行顯式字符比較來(lái)搜索P在T中的出現(xiàn)，而不是對(duì)所有對(duì)齊的暴力搜索。Boyer-Moore使用通過(guò)預(yù)處理P獲得的信息跳過(guò)盡可能多的對(duì)齊。在引入這個(gè)算法之前，在文本內(nèi)搜索的常用方式是檢查文本每個(gè)字符模式的第一個(gè)字符。一旦發(fā)現(xiàn)相同，文本的后續(xù)字符將與模式的字符進(jìn)行比較。如果沒有匹配，則再次逐個(gè)字符檢查文本，以便找到匹配。因此，文本中幾乎每個(gè)字符都需要檢查。該算法的關(guān)鍵點(diǎn)是，如果將模式的結(jié)束與文本相比較，則可以沿著文本跳躍而不是檢查文本的每個(gè)字符。這樣做的原因是，在將模式與文本對(duì)齊時(shí)，將模式的最后一個(gè)字符與文本中的字符進(jìn)行比較。如果字符不匹配，則無(wú)需繼續(xù)沿著模式向后搜索。如果文本中的字符與模式中的任何字符不匹配，則要檢查的文本中的下一個(gè)字符沿著文本位于更遠(yuǎn)的n個(gè)字符，其中，n是模式的長(zhǎng)度。如果文本中的字符在模式中，則沿著文本進(jìn)行模式的部分移位，以沿匹配字符排列，并且重復(fù)該過(guò)程。沿著文本跳躍以進(jìn)行比較而不是檢查文本中的每個(gè)字符，減少了必須比較的數(shù)量。這是算法效率的關(guān)鍵。更正式地，算法從對(duì)齊{k＝n}開始，因此P的開始與T的開始對(duì)齊。然后，P和T中的字符從P中的索引n和T中的k開始，向后移動(dòng)。字符串從P的結(jié)尾到P的開始匹配。比較繼續(xù)，直到達(dá)到P的開始或者發(fā)生不匹配，其中對(duì)齊向前移動(dòng)（向右）根據(jù)多個(gè)規(guī)則允許的最大值。在新對(duì)準(zhǔn)時(shí)再次執(zhí)行比較，并且重復(fù)該過(guò)程，直到對(duì)準(zhǔn)被移位經(jīng)過(guò)T的結(jié)束。這意味著找不到進(jìn)一步的匹配。移位規(guī)則被實(shí)現(xiàn)為使用在P預(yù)處理期間生成的表進(jìn)行常數(shù)查找。

一個(gè)簡(jiǎn)單但重要的優(yōu)化Boyer-Moore是由Galil在1979年提出的。與移位相反，Galil規(guī)則通過(guò)跳過(guò)已知匹配的部分來(lái)加速在每個(gè)對(duì)齊處進(jìn)行的實(shí)際比較。假設(shè)對(duì)齊k1、P與T下降到T的字符c，如果P被移位到k2，使得其左端在c和k1之間，則在下一比較階段中，P的前綴必須匹配子串T[（k2－n）…k1]。因此，如果比較向下到達(dá)T的位置k1，則可以記錄P的發(fā)生而不明確比較過(guò)去的k1。除了提高Boyer-Moore的效率之外，Galil規(guī)則可以在最差的情況下利用線性時(shí)間執(zhí)行。

3 BM算法的改進(jìn)

3.1 末字符不匹配

模式串字符與正文串字符從右向左匹配時(shí)，如果串末字符與正文串對(duì)應(yīng)字符不匹配，不是查看模式串串末字符對(duì)應(yīng)正文串字符的后繼字符是否在模式串中，而是查看與模式串串末字符對(duì)應(yīng)的正文串中字符的后繼字符是否為模式串串首字符。

3.2 后綴匹配

當(dāng)模式串字符與正文串字符從右向左匹配時(shí)，有部分匹配后，匹配如下：查看模式串的末字符對(duì)應(yīng)正文串中字符的后繼字符是否在模式串中，查看后綴是否存在僅出現(xiàn)一次的字符。

算法實(shí)現(xiàn)中包括以下2個(gè)步驟。

3.2.1 預(yù)處理

計(jì)算字符集中每個(gè)字符在模式串P中首次出現(xiàn)的位置，如果不存在，則為-1；如果存在，則記錄其位置。計(jì)算模式串P＝{P[0]，P[1]，…，P[m]}中每個(gè)字符首次出現(xiàn)的位置first[P[i]]（i為0～m），計(jì)算模式串中每個(gè)字符在模式串中出現(xiàn)的次數(shù)。

3.2.2 匹配過(guò)程

匹配過(guò)程如下：①初始化。定義變量tlen、plen表示模式串和正文串的長(zhǎng)度，定義變量num用于統(tǒng)計(jì)在模式串中出現(xiàn)不只一次的字符個(gè)數(shù)，定義循環(huán)變量i則用于進(jìn)行正文串與模式串的起始位置對(duì)齊，定義循環(huán)變量j用于模式串字符的匹配。②判斷i的值。如果i＞tlen－plen＋1，則失敗退出；否則，初始化j＝m，max＝0，onlyOne＝0.③循環(huán)②，直到T[i＋j]與P[j]不相等。④判斷j的值。如果j＝-1，則匹配成功，返回i值。⑤如果onlyOne≥1，即已匹配好的字符僅出現(xiàn)一次的個(gè)數(shù)存在。如果有，則i＝i＋max＋1，返回②；否則，繼續(xù)⑥。⑥判斷num－onlyOne是否大于0，即判斷還未進(jìn)行比較的模式串前部分是否存在模式串中僅出現(xiàn)一次的字符。⑦判斷壞字符T[i＋j]的前驅(qū)后繼字符以及T[i＋m]的前驅(qū)是否在P[j]與P[m]的相應(yīng)位置上，并根據(jù)其位置移動(dòng)，返回②。

4 總結(jié)與展望

古典字符串匹配算法的本質(zhì)是順序字符匹配，它總是從左到右或從右到左。在主字符串中，如果有許多子串具有與模式字符串相同的前綴或后綴，則算法效率低。移位的最大長(zhǎng)度是模式字符串的長(zhǎng)度。改進(jìn)后的算法使用兩串分離比較方法，有效地節(jié)省了由于子串和模式串的相同前綴或后綴的無(wú)意義的比較時(shí)間。在改進(jìn)的版本中，不執(zhí)行前綴移位，改善壞字符移位功能，還修改Goto過(guò)程，其不保持好的前綴移位和壞字符移位的參數(shù)。由于算法根據(jù)改進(jìn)的不良字符規(guī)則計(jì)算模式串的移動(dòng)距離，因此增加了模式串的移動(dòng)距離。實(shí)驗(yàn)結(jié)果表明，改進(jìn)的字符串匹配算法可以有效地減少字符串匹配次數(shù)和移動(dòng)次數(shù)來(lái)改進(jìn)算法，有利于提高模式識(shí)別的效率。

參考文獻(xiàn)

［1］王天聰，侯整風(fēng)，何玲.基于BM的模式匹配改進(jìn)算法［J］.合肥工業(yè)大學(xué)學(xué)報(bào)（自然科學(xué)版），2011（03）.