跳轉到

2.3 Boyer-Moore演算法#

概念說明#

Boyer-Moore（BM）是實務上最快的單樣式字串比對演算法。它與 KMP 相反的兩個設計選擇：從右往左比對（樣式建置時與文本對齊後，先看樣式的最後一個字元）、以及失配時右移多格而非一格。這帶來兩個規則：

壞字元規則（bad character rule）：文本中失配的字元是 c（在對齊位置）。查 c 在樣式中最後出現的位置；把樣式右移，使該出現與文本的 c 對齊。若 c 不在樣式中，直接把整個樣式移過該字元，右移 j+1 格。預處理只要替每種字元存最後出現位置。

好後綴規則（good suffix rule）：當樣式後半某段已比對成功（好後綴 S），失配發生在其左邊。此時把樣式往右移，使得樣式中「另一個與 S 相同（或與 S 的後綴相同且前方字元不同）的片段」對齊到文本的 S 位置。若不存在，移動整個樣式距離。預處理可用類似 KMP 失敗函數的陣列達成。

BM 的平均效能驚人：在隨機字母表的文本上，期望比較次數只有約 n/m（次線性！），因為一次失配常能跳過近 m 格。最壞情況（加好好後綴規則）為 O(n)；若只用壞字元規則，最壞可能退化為 O(nm)（如文本全 A、樣式 A...B...A）。簡化版 Horspool 演算法只用「末字元查表」一個規則，實作容易、效能接近，是實務常用版本。

BM 的思想被廣泛吸收：grep、編輯器的全文尋找、防毒引擎與第 10 章的敏感詞掃描，都以類似「查表跳躍」為核心。

演算法步驟（簡化 Horspool 版 + 說明擴充）#

  1. 預處理：建表 shift = {字元: 離樣式末端的距離}，處理「末字元本身」特例；未見字元距離為 m。
  2. 對齊樣式於位置 s，從樣式末字元開始往左比對。
  3. 全部相符：回報位置 s；否則令 s += shift[T[s+m-1]]（Horspool 永遠以窗口末字元查表）。
  4. 重複至樣式超出文本末端。

Python 程式碼範例#

def build_shift(pat):
    m = len(pat)
    shift = {ch: m for ch in set(pat)}
    for i in range(m - 1):           # 最後一個字元不記錄
        shift[pat[i]] = m - 1 - i
    return shift

def boyer_moore_horspool(text, pat):
    n, m = len(text), len(pat)
    if m == 0 or m > n:
        return []
    shift = build_shift(pat)
    ans, s = [], 0
    while s <= n - m:
        j = m - 1
        while j >= 0 and text[s + j] == pat[j]:
            j -= 1                    # 從右往左比對
        if j < 0:
            ans.append(s)
            s += 1
        else:
            # 以「當前窗口最右端字元」查表右移，這是一次跳多格的來源
            s += shift.get(text[s + j], m)
    return ans

T = "HERE IS A SIMPLE EXAMPLE AND EXAMPLE AGAIN"
P = "EXAMPLE"
print(boyer_moore_horspool(T, P))

# 比較跳躍效率：統計 Horspool 的字元比較次數
def counted_horspool(text, pat):
    m, n, s, cmp = len(pat), len(text), 0, 0
    shift = build_shift(pat)
    if m > n:
        return [], cmp
    while s <= n - m:
        j = m - 1
        while j >= 0:
            cmp += 1
            if text[s + j] == pat[j]:
                j -= 1
            else:
                break
        if j < 0:
            s += 1
        else:
            s += shift.get(text[s + j], m)
    return cmp

import random, time
long_text = "".join(random.choices("ABCDE", k=200000))
t0 = time.time()
c = counted_horspool(long_text, "ABDCE")
t1 = time.time()
print(f"比較次數: {c}，文本長 {len(long_text)}，比對率 {c/len(long_text):.3f}")

執行可見比較次數常遠低於文本長度，展現「次線性」特性。

複雜度分析#

  • 預處理：O(m + |Σ|) 時間與空間。
  • Horspool：平均約 O(n) 且常數極小（實務近似 n/m 次「窗口級」檢查）；只用壞字元規則的最壞情況 O(nm)。
  • 完整 Boyer-Moore（含好後綴規則）：最壞 O(n)。
  • 與 KMP 的取捨：KMP 保證線性且不回讀文本（適合串流），BM 平均更快但需要隨機取樣文本（適合記憶體內）。

練習#

  1. 以全 A 文本與樣式 A*10B（例如 AAAAAAAAABA）測量 Horspool 與 KMP 的比較次數，解釋差距來源。
  2. 實作完整壞字元規則改良版：失配時若窗口中位置 p 的字元在樣式更左邊存在，取「最後出現位置」對齊，驗證跳躍距離不小於原 Horspool 表。
  3. 用 Horspool 實作 str.replace 子字串置換（先找出全部出現位置，再一次性拼接新字串）。