v_JULY_v · 更新于 2017-12-22 09:00:57

4. 擴展 1：BM 算法

KMP 的匹配是從模式串的開頭開始匹配的，而 1977 年,，德克薩斯大學的 Robert S. Boyer 教授和 J Strother Moore 教授發(fā)明了一種新的字符串匹配算法：Boyer-Moore 算法,，簡稱 BM 算法。該算法從模式串的尾部開始匹配,，且擁有在最壞情況下 O(N) 的時間復雜度,。在實踐中，比 KMP 算法的實際效能高,。

BM 算法定義了兩個規(guī)則：

• 壞字符規(guī)則：當文本串中的某個字符跟模式串的某個字符不匹配時,，我們稱文本串中的這個失配字符為壞字符，此時模式串需要向右移動,，移動的位數(shù) = 壞字符在模式串中的位置 - 壞字符在模式串中最右出現(xiàn)的位置,。此外，如果"壞字符"不包含在模式串之中,，則最右出現(xiàn)位置為 -1,。
• 好后綴規(guī)則：當字符失配時,，后移位數(shù) = 好后綴在模式串中的位置 - 好后綴在模式串上一次出現(xiàn)的位置，且如果好后綴在模式串中沒有再次出現(xiàn),，則為 -1,。

下面舉例說明 BM 算法,。例如,，給定文本串“HERE IS A SIMPLE EXAMPLE”,，和模式串“EXAMPLE”,，現(xiàn)要查找模式串是否在文本串中,，如果存在,，返回模式串在文本串中的位置。

1.首先,，"文本串"與"模式串"頭部對齊,，從尾部開始比較。"S"與"E"不匹配,。這時,，"S"就被稱為"壞字符"（bad character）,，即不匹配的字符，它對應著模式串的第 6 位,。且"S"不包含在模式串"EXAMPLE"之中（相當于最右出現(xiàn)位置是 -1）,，這意味著可以把模式串后移 6-(-1)=7 位,，從而直接移到"S"的后一位。

2.依然從尾部開始比較,，發(fā)現(xiàn)"P"與"E"不匹配，所以"P"是"壞字符",。但是,，"P"包含在模式串"EXAMPLE"之中。因為“P”這個“壞字符”對應著模式串的第 6 位（從 0 開始編號）,，且在模式串中的最右出現(xiàn)位置為 4,，所以，將模式串后移 6-4=2 位,，兩個"P"對齊,。

3.依次比較，得到 “MPLE”匹配,，稱為"好后綴"（good suffix）,，即所有尾部匹配的字符串。注意,，"MPLE",、"PLE"、"LE",、"E"都是好后綴,。

4.發(fā)現(xiàn)“I”與“A”不匹配：“I”是壞字符。如果是根據(jù)壞字符規(guī)則,，此時模式串應該后移 2-(-1)=3 位,。問題是，有沒有更優(yōu)的移法,？

5.更優(yōu)的移法是利用好后綴規(guī)則：當字符失配時,，后移位數(shù) = 好后綴在模式串中的位置 - 好后綴在模式串中上一次出現(xiàn)的位置，且如果好后綴在模式串中沒有再次出現(xiàn),，則為 -1,。

所有的“好后綴”（MPLE、PLE,、LE,、E）之中，只有“E”在“EXAMPLE”的頭部出現(xiàn),，所以后移 6-0=6 位,。

可以看出，“壞字符規(guī)則”只能移3位,，“好后綴規(guī)則”可以移 6 位,。每次后移這兩個規(guī)則之中的較大值。這兩個規(guī)則的移動位數(shù),，只與模式串有關,，與原文本串無關,。

6.繼續(xù)從尾部開始比較，“P”與“E”不匹配,，因此“P”是“壞字符”,，根據(jù)“壞字符規(guī)則”，后移 6 - 4 = 2 位,。因為是最后一位就失配,，尚未獲得好后綴。

由上可知,，BM 算法不僅效率高,，而且構思巧妙，容易理解,。