模式匹配BM算法改進探討

徐政超

摘 要：研究了BM字符串匹配的算法，并提出了改進算法。借助這些算法的優點，可以判斷結束字符、相鄰字符的存在和唯一性，或者字符串不合理的字符。這些判斷結果增加了新的移動距離，減少了匹配的次數，并提高了字符串匹配的效率，對模式識別的高效發展具有深遠的意義和價值。

關鍵詞：BM算法；模式匹配；字符匹配；字符串

中圖分類號：G354 文獻標識碼：A DOI：10.15913/j.cnki.kjycx.2017.06.059

1 BM算法概述

在計算機科學中，Boyer-Moore字符串搜索算法是一種高效的字符串搜索算法，是實際字符串搜索文獻的標準基準，它是由Robert S. Boyer和J Strother Moore在1977年開發的。算法預處理搜索字符串，但不處理正在搜索的字符，因此，它非常適合于其中模式比文本短得多或在多個搜索中持續存在的應用程序。Boyer-Moore算法使用在預處理步驟期間收集的信息來跳過文本的部分，導致比許多其他字符串搜索算法具有更低的常數因子。

2 BM算法的原理

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

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

3 BM算法的改進

3.1 末字符不匹配

模式串字符與正文串字符從右向左匹配時，如果串末字符與正文串對應字符不匹配，不是查看模式串串末字符對應正文串字符的后繼字符是否在模式串中，而是查看與模式串串末字符對應的正文串中字符的后繼字符是否為模式串串首字符。

3.2 后綴匹配

當模式串字符與正文串字符從右向左匹配時，有部分匹配后，匹配如下：查看模式串的末字符對應正文串中字符的后繼字符是否在模式串中，查看后綴是否存在僅出現一次的字符。

算法實現中包括以下2個步驟。

3.2.1 預處理

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

3.2.2 匹配過程

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

4 總結與展望

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

參考文獻

［1］王天聰，侯整風，何玲.基于BM的模式匹配改進算法［J］.合肥工業大學學報（自然科學版），2011（03）.