Pythonで視覚的に理解するボイヤームーア法(Boyer-Moore Algorithm)の実装

はじめに

こんにちは！今回は文字列検索アルゴリズであるボイヤームーア法(Boyer-Moore Algorithm)をPythonで実装したプログラムを紹介します。ボイヤームーア法は文字列検索の分野で非常に効率的なアルゴリズムであり、特に検索対象が長い場合に力を発揮します。この投稿では。アルゴリズムの動作をステップごとに視覚化し、内部処理を丁寧に説明します。

ボイヤームーア法とは？

ボイヤームーア法は文字列検索アルゴリズムのひとつであり、テキスト内で特定のパターンを高速に検索するために設計されています。後ろから前に向かって文字を比較するのが特徴で、不一致が見つかった場合に文字の出現位置に基づいて効率的に検索範囲をスキップします。

1. 不一致の際のシフト量を計算するための「不一致処理」
2. パターンの中の文字の最も右の位置を利用する「文字位置テーブル」

実装コード

以下のボイヤームーア法の実装です。adjust_position関数で検索位置を調整し、不一致が発生したときの処理を視覚化しています。

def character_positions(T, pattern):
    # テキストTにおける対象となる各文字に対する位置を格納する辞書を初期化
    L = {char: -1 for char in set(list(T))}

    # パターンの文字ごとの位置を計算
    for j, char in enumerate(pattern):
        L[char] = j  # 複数回現れる場合は最も右の位置が記録される

    return L


def boyer_moore(text, pattern):
    m = len(pattern)
    n = len(text)
    L = character_positions(text, pattern)
    result = []  # 照合結果を保存するリスト

    print(f"\n{'='*50}")
    print(f"テキスト: {text}")
    print(f"パターン: {pattern}")
    print(f"{'='*50}\n")



    k = 0  # テキストの照合開始位置
    trial_count = 0

    while k <= n - m:
        j = m - 1  # パターンの末尾から照合開始
        print(f"\n照合位置 k = {k}")
        print(f"テキスト位置: {text[k:k+m]}")
        print(f"パターン    : {pattern}")

        while j >= 0:
            if text[k + j] != pattern[j]:
                alpha = text[k + j]
                old_k = k
                k = adjust_position(k, j, alpha, L)
                shift = k - old_k

                print(f"不一致: パターン位置 j = {j}, 文字 = {alpha}")
                print(f"右に {shift} 文字ずらします")

                result.append((trial_count, old_k, j, alpha))
                break
            j -= 1
        else:
            print("\nパターンが一致しました！")
            result.append((trial_count, k, j, None))
            break

        trial_count += 1

    return result

def adjust_position(k, j, alpha, L):
    if L[alpha] < j:
        return k + j - L[alpha]
    else:
        return k + 1

使用例

#実行例(変更点)
text = "なまなまずなまなまこなまなめこ"
pattern = "こなま"
results = boyer_moore(text, pattern)

実行結果

==================================================
テキスト: なまなまずなまなまこなまなめこ
パターン: こなま
==================================================


照合位置 k = 0
テキスト位置: なまな
パターン    : こなま
不一致: パターン位置 j = 2, 文字 = な
右に 1 文字ずらします

照合位置 k = 1
テキスト位置: まなま
パターン    : こなま
不一致: パターン位置 j = 0, 文字 = ま
右に 1 文字ずらします

照合位置 k = 2
テキスト位置: なまず
パターン    : こなま
不一致: パターン位置 j = 2, 文字 = ず
右に 3 文字ずらします
...
テキスト位置: こなま
パターン    : こなま

パターンが一致しました！

コードの説明

character_positions(T,pattern)

• テキストT内に含まれる文字に対して、その文字がパターン内で最も右に現れる位置を辞書Lに記録します。
• これにより、不一致が発生した際にスキップ量を計算できます。

boyer_moore(text,pattern)

-ボイヤームーア法を実行するメイン関数です。
-パターンに末から比較し、不一致が発生した場合にadjust_position関数を使って検索位置を調整します。

まとめ

ボイヤームーア法は効率的な文字列検索アルゴリズムです。不一致が発生したときに文字の出現位置を利用して検索範囲をスキップするため、最悪でもO(mn)、平均O(n/m)の計算量となります。最後まで読んでくださり、ありがとうございました。もし改善点や質問があれば、ぜひコメントしてください！