ボイヤー・ムーア法

ボイヤー・ムーア法 (BM法) は文字列探索アルゴリズムの一種で、発明者2名の名前を冠しています。 KMP法と同様に、予め余計な探索をを行わなくて済むようにずらし表を作成する必要があります。KMP法では理論上高速とされるわりに実用上速度が出にくいという欠点がありましたが、BM法は実用上高速に動作するとされています。

KMP法との大きな違いは、探索するパターン文字列の先頭ではなく、末尾から照合を行うという点にあります。例えば末尾が一致しなければ、パターン文字数分一気に探索位置を飛ばすことができるかもしれません。

特徴

前述のとおり、このアルゴリズムの特徴はずらし表と末尾から照合です。ずらし表では、不一致の際に探索対象文字列の位置をどこまでずらすかをあらかじめ準備しておく表です。

以下の表は "AAAXABAABBCAC" から "ABBC" を探索する場合のものです。BM法ではこのような順で探索を進めます。

1回目の探索は末尾の位置で不一致になります。この際不一致になった文字がパターン文字列に含まれないため、一気にパターン文字列分探索位置を進めることができます。これはパターンに含まれない文字のため、これを含む位置はすべて調べるまでもなく不一致になると言えるからです。

2回目の探索では末尾の位置 "A" の文字で不一致になります。この場合、ずらし表から "A" に対応する値を取得しずらします。ずらし表については後述しますが、この場合 "A" のずらし位置は 3 となるので探索位置を 3 進めます。

3回目の探索でも同じようにパターン末尾の文字から一致判定を行います。"C", "B", "B", "A" の順にすべて一致するためここで処理終了となります。

A A A X A B A A B B C A C
1 C
2 C
3 A B B C

ずらし表

探索の前に予めずらし表を生成して置かなければなりません。

これは単純にパターン文字列の末尾からの距離で表します。ただし、同じ文字が出てくる場合、より後ろの位置(ずらす大きさが小さい値)を優先します。したがってパターン文字列 "ABBC" の場合、次のようになります。

各文字の末尾からの距離は次のようになるので、これの各文字での最小値をとったものがずらし表となります。

A B B C
3 2 1 0

以下がそのずらし表です。なおずらし表に存在しない文字(つまりパターン文字列に存在しない文字)の場合、パターン文字列文の長さがずらす大きさになります。

A B C その他の文字
3 1 0 4

アルゴリズムの解説

  1. 探索するパターン文字列からずらし表を生成します。
  2. 探索対象文字列上の位置を i=(パターン文字列末尾の位置) , パターン文字列上の位置を p=0 とします。
  3. i が探索対象文字列の文字数を越えない条件でループします。
    • p を パターン文字列末尾の位置にします。
    • 末尾からパターン文字と一致するか判定を行います。
    • すべてパターン文字と一致する場合、現在の i を返します。
    • 不一致になった場合、探索対象の文字でずらし表を参照し、i を進めます。
    • ただしずらし位置が比較開始位置より手前の場合、比較位置の1文字後に i を進めます。
  4. 上記ループで一致しなければ -1(パターン文字列が存在しない) を結果として返します。

サンプルコード

C#

// BM法
public int BMSearch(string target, string pattern)
{
    var table = CreateTable(pattern);

    // 開始位置をパターン末尾に合わせる
    int i = pattern.Length - 1;
    int p = 0;

    while (i < target.Length)
    {
        // パターン末尾に位置を合わせる
        p = pattern.Length - 1;

        while (p >= 0 && i < target.Length)
        {
            if (target[i] == pattern[p])
            {
                i--; p--;
            }
            else
            {
                break;
            }
        }
        // 一致判定
        if (p < 0) return i + 1;

        // 不一致の場合、ずらし表を参照し i を進める
        // ただし、今比較した位置より後の位置とする
        var shift1 = table.ContainsKey(pattern[p]) ? table[pattern[p]] : pattern.Length;
        var shift2 = pattern.Length - p;    // 比較を開始した地点の1つ後ろの文字
        i += Math.Max(shift1, shift2);
    }

    return -1; // 見つからなかった
}

// ずらし表の作成
public Dictionary<char, int> CreateTable(string pattern)
{
    // パターン末尾からの距離(小さい幅を優先)
    var table = new Dictionary<char, int>();
    for (int i = 0; i < pattern.Length; i++)
    {
        table[pattern[i]] = pattern.Length - i - 1;
    }
    return table;
}