Boyer-Moore 演算法又稱BM演算法，是1977 年 Robert S. Boyer and J Strother Moore 提出的高效率字串搜尋演算法。
在開始搜尋字串之前，會先對搜尋目標 pattern 進行預處理 preprocessing 的動作，前處理可得到後續要使用的「好後綴位移」(good-suffix shift)和「壞字元位移」(bad-character shift) 兩種資料。
接下來在使用這個 pattern 到原文搜尋字串時，就能利用「好後綴位移」(good-suffix shift)和「壞字元位移」(bad-character shift)，來想辦法讓目前無法與樣本相匹配的文字索引位置，能夠位移最多個字元的索引距離，減少原文字元與樣本字元的判斷是否相同的次數，來加速字串搜尋。
「好後綴」為目前位置之樣本和原文相符的字串後綴；「壞字元」為目前位置之樣本和原文從後面判斷第一個出現的不相符字元，就是好後綴開頭的前一個字元。
定義
bad-character
目前無法與 pattern 匹配的字元，匹配順序是由 pattern 最後面往前找
good-suffix
在匹配遇到 bad-character 之前，跟 pattern 匹配成功的字串
bad-character shift rule
往右移動的字元數 = "bad-character" 在 pattern 中出現的位置 - "bad-character" 在 pattern 中出現最右邊的位置
「把 pattern 往右移動最少幾個索引值後，pattern 本身所含有的『壞字元』能和剛剛在原文中發現的『壞字元』對齊」
如果 pattern 中不存在 bad-character，則最右邊的位置是在 pattern 的前面一個字元。也就是要把 pattern 往右移動最少幾個索引值後，pattern 的第1個字元會在原文的「壞字元」的下一個索引位置。
good-suffix shift rule
往右移動的字元數 = "good-suffix" 在 pattern 中出現的位置 - "good-suffix" 在 pattern 中最右邊出現且 prefix 字元不同的位置
要把 pattern 往右移動最少幾個索引值後，pattern 本身所含有的 good-suffix 或是延伸的good-suffix能和剛剛在原文中發現的 good-suffix 或是延伸的 good-suffix 對齊。
實例
搜尋 pattern:
EXAMPLE原文:
HERE IS A SIMPLE EXAMPLEStep 1
HERE IS A SIMPLE EXAMPLE
EXAMPLE- S 跟 E 不同，這時候的 S 為 bad-character
- 因為沒有一個字元一樣，所以沒有 good-suffix
- 因為 EXAMPLE 裡面不存在 S，無法完成「把
EXAMPLE這個 pattern 往右移動最少幾個索引值後，pattern 本身所含有的『壞字元』能和剛剛在原文中發現的『壞字元』對齊」這個條件 - 現在的 bad-character shift，變成是要把
EXAMPLE這個樣本往右移動最少幾個索引值後，樣本的第1個字元會在原文的「壞字元」的下一個索引位置
Step 2
HERE IS A SIMPLE EXAMPLE
EXAMPLE- 因為 P 跟 E 不同，P 為 bad-character
- 沒有字元匹配成功，故沒有 good-suffix
- 接下來判斷「把
EXAMPLE這個 pattern 往右移動最少幾個索引值後，pattern 本身所含有的『壞字元』能和剛剛在原文中發現的『壞字元』對齊」這個條件，故往右移動 2 個字元
Step 3
HERE IS A SIMPLE EXAMPLE
EXAMPLE- MPLE 一樣，稱為 good-suffix
- I 跟 A 不同，稱為 bad-character
- 因為 EXA 裡面不存在 I，無法完成「把
EXAMPLE這個 pattern 往右移動最少幾個索引值後，pattern 本身所含有的『壞字元』能和剛剛在原文中發現的『壞字元』對齊」這個條件 - 現在的 bad-character shift，變成是要把
EXAMPLE這個樣本往右移動最少幾個索引值後，樣本的第1個字元會在原文的「壞字元」的下一個索引位置，所以是 3 - 同時利用 good-suffix MPLE 以及 PLE, LE, E，計算 good-suffix shift。
- 目標是要把
EXAMPLE這個 pattern 往右移動最少幾個索引值後，pattern 本身所含有的 good-suffix 或是延伸的good-suffix能和剛剛在原文中發現的 good-suffix 或是延伸的 good-suffix 對齊。 - 先看 MPLE，無法在 pattern 右移後，還能跟 MPLE 對齊
- 無法在 pattern 右移後，跟 PLE 對齊
- 無法在 pattern 右移後，跟 LE 對齊
- 可以在 pattern 右移後，跟 E 對齊，pattern 必須右移 6 個字元
- 因為 bad-character shift 為 3，good-suffix shift 為 6，選擇使用 good-suffix shift 為 6
Step 4
HERE IS A SIMPLE EXAMPLE
EXAMPLE- P 與 E 不同，稱為 bad-character
- 接下來判斷「把
EXAMPLE這個 pattern 往右移動最少幾個索引值後，pattern 本身所含有的『壞字元』能和剛剛在原文中發現的『壞字元』對齊」這個條件，故往右移動 2 個字元
Step 5
HERE IS A SIMPLE EXAMPLE
EXAMPLE- EXAMPLE 完全一樣，搜尋完成
References
Boyer-Moore-MagicLen(BM-MagicLen)字串搜尋演算法，超快速的全文搜尋演算法
沒有留言:
張貼留言