博耶-穆爾字符串搜索算法

在計算機科學里，博耶-穆爾字符串搜索算法是一種非常高效的字符串搜索算法。它由羅伯特·斯蒂芬·博耶和J·斯特羅瑟·穆爾設計於1977年。此算法僅對搜索目標字符串（關鍵字）進行預處理，而非被搜索的字符串。雖然博耶-穆爾算法的執行時間同樣線性依賴於被搜索字符串的大小，但是通常僅為其它算法的一小部分：它不需要對被搜索的字符串中的字符進行逐一比較，而會跳過其中某些部分。通常搜索關鍵字越長，算法速度越快。它的效率來自於這樣的事實：對於每一次失敗的匹配嘗試，算法都能夠使用這些信息來排除儘可能多的無法匹配的位置。

定義

• S[i]為字符串S從1開始排列的第i個字符
• S[i..j]為字符串S的一個子串，始於i，終於j。
• S的前綴定義為S[1..i],1<i<n，n為字符串S的長度。
• S的後綴定義為S[i..n],1<i<=n，小於字符串S的長度。
• 檢索的字符串稱為pattern，用符號P表示。
• 被檢索字符稱為text，用符號T表示。
• P的長度為n
• T的長度為m
• k表示P的最後一個字符在T中的位置。
• 當匹配發生時，P在T中的位置為T[(k-n+1)..k]。

原理

不同於暴力搜尋（brute-force search）的逐個字符對比，博耶-穆爾充分使用預處理P的信息來儘可能跳過更多的字符。通常，我們比較一個字符串都是從首字母開始，逐個比較下去。一旦發現有不同的字符，就需要從頭開始進行下一次比較。這樣，就需要將字串中的所有字符一一比較。博耶-穆爾算法的關鍵在於，當P的最後一個字符被比較完成後，我們可以決定跳過一個或更多個字符。如果最後一個字符不匹配，那麼就沒必要繼續比較前一個字符。如果最後一個字符未在P中出現，那麼我們可以直接跳過T的n個字符，比較接下來的n個字符，n為P的長度（見定義）。如果最後一個字符出現在P中，那麼跳過的字符數需要進行計算（也就是將P整體往後移），然後繼續前面的步驟來比較。通過這種字符的移動方式來代替逐個比較是這個算法如此高效的關鍵所在。

形式化的表述方式為，從k=n開始，也就是P從T的最開始進行比較。緊接着，P的第n個字符和T的第k個字符開始：字符串依次從P的最後一個字符到最開始的字符。結束條件是當比較到達P的最開始（此時匹配完成），或按照規則移動後的字符部匹配發生時。然後，在新的對齊位置重新開始比較，如此反覆，直到到達T的結尾。

移動規則是一張間恆定的查找表，通過對P的預處理產生的。

移動規則

移動字符數是通過兩條規則決定的：壞字符規則和好後綴規則。實際移動為通過這兩條規則計算出的最大移動個數。

壞字符規則

原理

-	-	-	-	X	-	-	K	-	-	-
A	N	P	A	N	M	A	N	A	M	-
-	N	N	A	A	M	A	N	-	-	-
-	-	-	N	N	A	A	M	A	N	-

Demonstration of bad character rule with pattern NNAAMAN.

當T中有字符不匹配時，如果T中的這個不匹配的字符出現在對應P中當前位置的左側，那麼P移動位置將這兩個在字符對齊。如果T中這個不匹配字符不在P中當前位置的左側，那麼將當前位置左側的所有字符均移到該不匹配字符後。右側的例子中，X位置發生了不匹配，我們檢查P中的不匹配字符N（對應T中字符A）在P當前位置（X）的左側存在，因此，將最靠近該不匹配字符位置的N與P中的X位置的N對齊，也就是向右移動兩位。

處理

當我們發現不匹配字符時，假設這個字符在T中為c，位置在T的i。字符c在P中出現的最靠近i位置，假設為j，j<i或j=-1（如果P不存在字符c）。那麼移動位數為i - j，複雜度是O(1)。i，j的起點為P在T中位置的開始T[(k-n+1)..k]的(k-n+1)。 大多網站都只建立一個一維壞字符數組來保存，但事實這只能保存最靠左或最靠右的字符c，明顯與英文的wikipedia裡面要求一個二維數組來保存信息的不一樣。

好後綴規則

原理

好後綴規則要更複雜一點。

假設有P和T，T中字串t匹配到了P的一個後綴，但在比較位置i時發生不匹配。設匹配到的好後綴在T中為t，在P中為t'（t = t'）。

分兩種情況來討論：

1，在P中i位置的左側最靠近i位置查找字串t'使得t'=t（此時t'不是P的後綴，實際上也就是查找匹配到的字串除了在P的後綴中存在，是否在P的其他位置存在），若存在，則移動相應的位數將找到的t'與T中的t對齊。

2，如果t'不存在，那我們繼續查找t的某一個後綴是否為P的前綴，若存在，則移動相應的位將P的前綴與t的後綴位置對齊。否則，將P向後移動n個字符。

好後綴規則的實質是，將不匹配位置右側匹配到的字符串t的所有字符後綴組合，用於查找它們在P的不匹配位置左側是否存在。

通俗的理解是，最長的好後綴t是否存在於i的左側（情況1），其他後綴組合中是否存在與P的前綴相同的情況（情況2）。

舉例

假設被檢索文字列是「1234567890」，檢索文字列是「MOORE」。簡單的比較需要執行十次才得到結論不匹配。被檢索文字列：1234567890

  第一次比较：M....         （M和1比较，不匹配）
  第二次比较： M....        （M和2比较，不匹配）
  第三次比较：  M....       （M和3比较，不匹配）
        ...
  第十次比较：         M....（M和0比较，不匹配）

※未參與比較的文字用【.】占位。

BM算法只需要2次比較。

被檢索文字列：1234567890

  第一次比较：....E        （E和5比较，不匹配，并且5不是MOORE中任何文字）
  第二次比较：     ....E   （E和0比较，不匹配，并且0不是MOORE中任何文字）

第一次從檢索文字的末尾開始，因為如果被檢索文字的第5文字位置不是E，則無論前4個文字是什麽，都絕不可能匹配了。這一點比較容易理解。

而之所以不用E和6比較，則是因在E和5進行比較的時候不僅知道他們不相等，而且還知道了5不和檢索文字MOORE中的任何一個文字相等，這使得下面這些比較都可以省略掉。

被檢索文字列：....5......

不需要的比较： ...R.       （E和5比较时也同时发现5不等于R，于是这个比较是不必要的）
不需要的比较：  ..O..      （E和5比较时也同时发现5不等于O，于是这个比较是不必要的）
不需要的比较：   .O...     （E和5比较时也同时发现5不等于O，于是这个比较是不必要的）
不需要的比较：    M....    （E和5比较时也同时发现5不等于M，于是这个比较是不必要的）

另見

• 克努斯-莫里斯-普拉特算法
• 後綴樹

外部連結

• String Searching Applet animation（頁面存檔備份，存於網際網路檔案館）
• Original article（頁面存檔備份，存於網際網路檔案館）
• An example of the Boyer-Moore algorithm（頁面存檔備份，存於網際網路檔案館） from the homepage of J Strother Moore, co-inventor of the algorithm
• An explanation of the algorithm (with sample C code)（頁面存檔備份，存於網際網路檔案館）
• Cole et al., Tighter lower bounds on the exact complexity of string matching（頁面存檔備份，存於網際網路檔案館）
• An implementation of the algorithm in Ruby（頁面存檔備份，存於網際網路檔案館）
• Scala functional implementation（頁面存檔備份，存於網際網路檔案館） with source code（頁面存檔備份，存於網際網路檔案館）
• 字符串匹配的Boyer-Moore算法（頁面存檔備份，存於網際網路檔案館）