博耶-穆爾字串搜尋演算法

在電腦科學里，博耶-穆爾字串搜尋演算法是一種非常高效的字串搜尋演算法。它由羅伯特·史蒂芬·博耶（英語：Robert S. Boyer）和J·斯特羅瑟·穆爾（英語：J Strother Moore）設計於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演算法（頁面存檔備份，存於網際網路檔案館）