比KMP高效的Boyer-Moore字元串比對算法

       在這裡我所要想說的比KMP算法高效的算法是Boyer-Moore算法。

       在講解Boyer-moore算法之前，在這裡先回顧一下KMP算法。

       比如說有一個字元串"BBC ABCDAB ABCDABCDABDE"，我想知道，裡面是否包含另一個字元串"ABCDABD"。大部分情況下我們會使用KMP算法去解：

1. 

首先，字元串"BBC ABCDAB ABCDABCDABDE"的第一個字元與搜尋詞"ABCDABD"的第一個字元，進行比較。因為B與A不比對，是以搜尋詞後移一位。 2.

B與A不比對，搜尋詞向後移一位。直到有一位搜尋詞相同。 3.

可以看到前6個數都是相同的，但是最後一個數D與空格不相同。根據KMP算法，搜尋詞向後移動一位。但是這就是KMP算法效率低的地方，之前的6個數我們已經比較過了，已經不可能比對了，但是KMP算法還是重複的比對。在後面講的Boyer-Moore算法會有優化。 4.

     其實KMP在這裡是有優化的，KMP算法的想法是，設法利用這個已知資訊，不要把"搜尋位置"移回已經比較過的位置，繼續把它向後移，這樣就提高了效率。     利用《部分比對表》（Partial Match Table）可以根據公式：              移動位數 = 已比對的字元數 - 對應的部分比對值；  算出向後移動的位數。

5. 部分比對表執行個體：

     "部分比對"的實質是，有時候，字元串頭部和尾部會有重複。比如，"ABCDAB"之中有兩個"AB"，那麼它的"部分比對值"就是2（"AB"的長度）。搜尋詞移動的時候，第一個"AB"向後移動4位（字元串長度-部分比對值），就可以來到第二個"AB"的位置。

Boyer-Moore算法：

壞字元算法：            其實Boyer-Moore算法使用最多的是大部分軟體裡的“查找算法”。crtl+F4的功能。

注意：Boyer-Moore算法是從後向前比對的。這是一個很聰明的想法，因為如果尾部字元不比對，那麼隻要一次比較，就可以知道前7個字元（整體上）肯定不是要找的結果。

如上面的情況： Boyer-Moore是怎麼處理的呢？

我們看到，"C"與"D"不比對。這時，"C"就被稱為"壞字元"（bad character），即不比對的字元。我們還發現，"C"包含在搜尋詞"ABCDABD"之中，這意味着可以把搜尋詞直接移到"C"的後一位。

我們看到，"D"與"空格不比對。這時，空格就被稱為"壞字元"（bad character），即不比對的字元。我們還發現，空格不包含在搜尋詞"ABCDABD"之中，這意味着可以把搜尋詞直接移到空格的後一位。

而後面的“C”和“D”不相同，但是我們可以注意到壞字元“C”在搜尋詞“ABCDABD”中，根據規則我們将搜尋詞中的“C”移動到壞字元處：

這樣，我們就找到了比對的字元串了。。

我們可以總結Boyer-Moore的壞字元算法：

後移位數 = 壞字元的位置 - 搜尋詞中的上一次出現位置

即：壞字元“C”（上面的那一個C）出現在搜尋詞的第6位（從0開始），在搜尋詞中上一次出現的位置是2。是以6-2=4。

向後移動4位。

注意：如果"壞字元"不包含在搜尋詞之中，則上一次出現位置為 -1。

Boyer-Moore算法除了有”壞字元算法“還有

”好字尾算法“：

   那麼好字尾算法是什麼樣的情況呢？這裡，我們得換個例子：    如果出現這種情況：

    "MPLE"與"MPLE"比對。我們把這種情況稱為"好字尾"（good suffix），即所有尾部比對的字元串。注意，"MPLE"、"PLE"、"LE"、"E"都是好字尾。

      比較"I"與"A"不比對，那麼"I"就是壞字元。根據"壞字元規則"，此時搜尋詞應該後移 2 - （-1）= 3 位。但是在這裡我們采用"好字尾算法": 後移位數 = 好字尾的位置 - 搜尋詞中的上一次出現位置 此時，所有的"好字尾"（MPLE、PLE、LE、E）之中，隻有"E"在"EXAMPLE"還出現在頭部，是以後移 6 - 0 = 6位。

"壞字元規則"隻能移3位，"好字尾規則"可以移6位。是以，Boyer-Moore算法的基本思想是，每次後移這兩個規則之中的較大值。

繼續從尾部開始比較，"P"與"E"不比對，是以"P"是"壞字元"。根據"壞字元規則"，後移 6 - 4 = 2位。

比對完成。。。