Boyer-Moore字符串搜索算法

在電腦科學里，**博耶 - 穆爾字串搜尋演算法**是一種非常高效的字串搜尋演算法。它由羅伯特・史蒂芬・博耶和 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** 的預處理產生的。

## 移動規則

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

### 壞字元規則

#### 原理

當 **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 演算法（頁面存檔備份，存於網際網路檔案館）