基本介紹
- 中文名：BM字元串搜尋算法
- 外文名：BM String Searching Algorithm
- 學科：計算機科學
- 算法類型：字元串搜尋算法
- 發明人：Bob Boyer和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）的逐個字元對比，Boyer-Moore充分使用預處理P的信息來儘可能跳過更多的字元。通常，我們比較一個字元串都是從首字母開始，逐個比較下去。一旦發現有不同的字元，就需要從頭開始進行下一次比較。這樣，就需要將字串中的所有字元一一比較。Boyer-Moore算法的關鍵在於，當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 patternNNAAMAN.
當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)。
好後綴規則
原理
好後綴規則要更複雜一點。
假設有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）。
