https://engineeringnote.hateblo.jp/entry/python/algorithm-and-data-structures/bm

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

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

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))

動作確認

それでは上記で作成したスクリプトを実行してみます。

事前にa～zまでランダムに100,000文字を生成し、文字列の最後に"hoge"を追記したものから、"hoge"のパターンを探索します。

自環境で実行した結果を以下にまとめます。

**100,000文字の探索結果**
アルゴリズム名	所要時間（秒）
Python 組込みメソッド（find()）	0.0004
Brute-forcing	0.0414
KMP	0.0379
BM	0.0159

参考書籍

定本 Cプログラマのためのアルゴリズムとデータ構造 (SOFTBANK BOOKS)