BM法（Pythonによるアルゴリズムとデータ構造）

本記事は、ソフトバンクパブリッシングから発行されている「定本 Cプログラマのためのアルゴリズムとデータ構造 (SOFTBANK BOOKS)」を参考にPythonでアルゴリズムとデータ構造について学習していきます。

今回は、文字列の探索としてBM法（Boyer–Moore String-Search Algorithm）について学んでいきます。

BM法とは
PythonでBM法を実装してみる
動作確認
参考書籍

BM法とは

BM法（Boyer–Moore String-Search Algorithm）とは、1977年にR.S.BoyerとJ.S.Mooreにより発表されたアルゴリズムです。

前回のKMP法は、理論的には優れているのですが実用面では難がありました。

しかし、BM法は実用的にも優れており、高速な文字列探索のアルゴリズムになります。

これまでの力まかせのアルゴリズムやKMP法では、何れも文字列とパターンを先頭から比較していきましたが、BM法では末尾から先頭に向かって比較を行い、不一致があった際には事前に作成したずらし表を基に、ずらす分量を決定します。

そのため、パターンの文字数を $m$ とすると、最大で $m$ 文字分ずらすことが可能になるため、うまくいけば $O(\frac{n}{m})$ の計算量に収まります。

PythonでBM法を実装してみる

それでは、PythonでBM法を実装してみます。

# bm.py
import time

def max(a, b):
    return a if a > b else b

def bm_search(string, pattern):
    pat_len = len(pattern)
    skip = [pat_len for _ in range(256)]
    for i in range(pat_len):
        skip[ord(pattern[i])] = pat_len - i - 1
    i = pat_len - 1
    while i < len(string):
        j = pat_len - 1
        while string[i] == pattern[j]:
            if j == 0:
                return i
            i -= 1
            j -= 1
        i = i + max(skip[ord(string[i])], pat_len-j)
    return None

with open("sample_string.txt", "r") as f:
    string = f.read()
pattern = "hoge"
start = time.time()
index = bm_search(string, pattern)
if index:
    print("The pattern starts with at index {}.".format(index))
else:
    print("No pattern matched.")
print("elapsed {} sec.".format(time.time() - start))