模式匹配BF算法分析及實現

任憲臻 任美玲

(1.北京信息職業技術學院 軟件與信息學院，北京 100018;2.煙臺南山學院 工學院計算機系，山東 煙臺 265700)

字符串是以字符作為數據元素的線性表，是非常重要的非數值處理對象。目前大量地處理非數值計算問題都給通過計算機來實現，例如，文字編輯、信息檢索、詞法掃描、符號處理、自然語言翻譯等。在事務處理程序中，如客戶信息、貨物產地等一般也都是作為字符串處理，因此字符串在很多領域都得到了廣泛應用。字符串的邏輯結構與線性表的邏輯結構相同，但是它的基本操作卻和線性表的基本操作有著很大的差別。線性表的基本操作主要是以“單個數據元素”作為操作對象，比如在線性表中的某個位置插入或刪除一個元素、在線性表中按位查找或者按值查找某個元素等；而字符串的基本操作的操作對象卻通常是一個“字符串整體”，比如在字符串的某個位置插入或者刪除一個子串、在字符串中定位查找某個子串等。

字符串被廣泛應用在非數值處理領域，其中字符串的查找定位操作是最經常用到的。字符串的查找定位也經常被稱為字符串的模式匹配，是指在主串中尋找子串的一個過程。例如，如果給定兩個字符串：S=“s1s2…sn”，T=“t1t2…tm”（1 ≤m ≤n），在主串S 中尋找子串T 的過程就稱為模式匹配，其中字符串T 稱為模式。如果在主串S 中找到了一個和模式T 相同的字符子串，則表示在主串S 中查找模式T 成功，也稱模式T 匹配成功。當模式T 匹配成功時，返回模式T 的首字符在主串S 中的位置（本文設定字符的位置序號從1 開始計數）；如果在主串S 中找不到與模式T 相同的子串，則表示在主串S 中查找模式T 失敗，即模式T 匹配失敗。當模式T 匹配失敗時，返回數值0。

字符串的模式匹配操作被頻繁應用在郵件過濾、搜索引擎、文本處理以及數據庫系統中。在模式匹配的過程中，問題的規模通常會很大，所以常常需要在大量信息中執行匹配操作，因此模式匹配算法的一次執行時間是不容忽視的。此外，因為模式匹配操作經常被調用，所以匹配操作的執行頻率非常高，因此模式匹配算法改進所取得的效益累積效應往往比表面上看起來要大的多。在字符串的模式匹配算法中，有兩種主要的模式匹配算法：Brute-Force 算法（簡稱BF 算法）和KMP 算法，本文主要論述BF 算法。

BF 算法是一種非常簡單而又直觀的模式匹配算法，“蠻力匹配”是BF 算法的基本思想：從主串S 的第一個字符開始和模式T 的第一個字符開始進行比較，若比較相等，則繼續比較主串S 和模式T 的后續字符；否則，從主串S 的第二個字符開始和模式T 的第一個字符重新進行比較……重復上述過程，直至字符串S 或模式T 中所有字符均被比較完畢。若BF 算法的模式匹配過程結束時，模式T 中的字符全部被比較完畢，則表示模式T 匹配成功，返回本趟匹配的開始位置，即模式T 的首字符在主串S 中的序號；否則模式T 匹配失敗，返回數值0。

模式匹配BF 算法的偽代碼描述如下所示：

算法：BF

輸入：主串S，模式T

輸出：T 在S 中的位置序號(從1 開始計數)

1.設定S 和T 比較的開始下標 i=0，j=0（從0 開始）；

2.重復2.1 和2.2 兩步操作，直到S 或T 的所有字符均被比較完畢：

2.1 如果S[i]==T[j]，則繼續比較S 和T 的下一對字符；

2.2 否則(即S[i]!=T[j])，則將S和T比較的下標i和j進行回溯，準備下一趟比較；

3.如果T中所有字符均比較完，則匹配成功，返回本趟匹配的起始位置；否則返回 0；

我們通過主串S=“ababcabcacbab”，模式T=”abcac”來看一下BF 算法匹配過程，串S 和串T 的表示如圖1 所示：

第一趟匹配：開始下標i=0，j=0，當i=2，j=2 時匹配失敗，這時i回溯到 1，j 回溯到 0；

第二趟匹配：開始下標i=1，j=0，當i=1，j=0 時匹配失敗，這時i回溯到 2，j 回溯到 0；

第三趟匹配：開始下標i=2，j=0，當i=6，j=4 時匹配失敗，這時i回溯到 3，j 回溯到0；

第四趟匹配：開始下標i=3，j=0，當i=3，j=0 時匹配失敗，這時i 回溯到 4，j回溯到0；

第五趟匹配：開始下標i=4，j=0，當i=4，j=0 時匹配失敗，這時i回溯到 5，j回溯到 0；

第六趟匹配：開始下標i=5，j=0，當i=10，j=5時，模式T中的全部字符都被比較完畢，所以模式匹配成功，此時應該返回模式T 在主串S 中的位置序號6。

通過以上分析，用java 程序設計語言實現的BF 算法及對算法進行的測試如圖2、圖3、圖4 所示：

從以上BF 算法的分析與實現我們可以發現，BF 算法簡單，但是其實效率比較低。通過分析BF 算法的執行過程，我們可以得知造成BF 算法效率比較低的最重要的原因就是每趟匹配失敗后的下標回溯，即在某趟匹配失敗后，對于主串S 要回溯到本趟匹配開始字符的下一個字符，而模式T要回溯到第一個字符，而在有些情況下，這些回溯往往是不必要的。由 Knuth、Morris 和Pratt 三位科學家共同提出并設計的KMP 算法對BF 算法做了很大的改進，它主要消除了匹配不成功的情況下主串指針不必要的回溯，從而使模式匹配算法的效率在某種程度上有了很大的提高。