文字列探索のアルゴリズム

文字列の探索について

以下ではパターンを 文字、テキストを 文字とします。

力まかせ法

考え方

テキストの先頭とパターンを重ねます。パターンとテキストが一致すれば探索は成功。不一致の場合は、パターンを1文字分だけ後ろにずらして、再びパターンとテキストを比較します。この手順をテキストの最後尾になるまで繰り返します。

計算量

最悪のケースは、テキストが"aaaaaaaab"で、パターンが"aaab"というようになっている場合です。 パターンとテキストを重ね合わせる位置が つあり、そのすべての位置で 回比較が行われます。合計で、 回比較が行われます。 ただし は よりも十分に大きいと仮定できるので、 は とみなせます。 よって、計算量は となります。 また、自然言語の場合は使用される文字数が多いと仮定できるため、テキストとパターンの比較は、先頭の数文字のみで判断できることが多く、実質比較回数の は とみなせ、計算量は 程度となります。

実装

以下の実装については「Javaプログラマのためのアルゴリズムとデータ構造」*1より自分の理解のために写経したものになります。 ステップ実行で動作を確認することで理解が深まります。

public class BruteForce {

    /**
    * 文字列textから文字列patternを探索する（力任せ法）
    *
    * @param text       テキスト
    * @param pattern    パターン（探し出す文字列）
    * @return          見つかった位置
    *
    * */
    public static int search(String text, String pattern) {

        int patLen = pattern.length();
        int textLen = text.length();
        int i = 0;        // 注目しているテキストの位置を表すポインタ
        int j = 0;        // 注目しているパターンの位置を表すポインタ

        // テキストの最後尾に行き当たるか、パターンが見つかるまで繰り返す
        while (i < textLen && j < patLen) {

            // テキストとパターンの1文字比較する
            if (text.charAt(i) == pattern.charAt(j)) {
                // 一致した
                i++; j++;
            } else {
                // 一致しなかった
                i = i - j + 1;
                j = 0;
            }
        }
        return (j == patLen) ? (i -j) : -1;
    }
}

BM法

考え方

パターンとテキストを重ね合わせて、末尾から先頭に向かって順番に文字を比較していき、パターンとテキストの不一致が見つかったら、不一致の原因になった文字に応じてパターンをずらす分量を決めます。

不一致の場合にパターンをずらす文字数について

1.パターンに含まれない文字の場合
パターンを 文字分ずらせばよい

2.パターンに含まれる文字の場合
その文字がパターンの末尾から見て 文字目(末尾を 文字目とします)に当たるとすると、パターンを 文字ずらせばよい

3.不一致になった文字がパターンに存在し、パターンの注目点よりも末尾にある場合
パターンを現在の位置より つずらす

計算量

最悪のケースは、テキストが"aaaaaaaaaaaa"で、パターンが"baaaa"というようになっている場合です。この場合の計算量は力まかせ法と同様に となります。 一般的には、1回の比較で 文字分、注目点をずらすことが可能であるため計算量としては 程度になります。

実装

import java.util.Arrays;

public class BoyerMoore {

    /**
    * 文字列textから文字列patternを探索する（BM法）
    *
    * @param text       テキスト（探索の対象となる文字列）
    * @param pattern    パターン（探し出す文字列）
    * @return          見つかった位置
    *
    * */
    public static int search(String text, String pattern) {

        int patLen = pattern.length(); // パターンの長さ
        int textLen = text.length();   // テキストの長さ

        // テキストとパターンの不一致が見つかった時に、
        // どれだけずらすかを示す表
        int[] skip = new int[65536];

        // 表skipを作成する
        Arrays.fill(skip, patLen);
        for (int x = 0; x < patLen - 1; x++) {
            skip[pattern.charAt(x)] = patLen - x - 1;
        }

        // 注目しているテキストの位置を表すポインタ
        // パターンを後ろから前に向かって比較するので、
        // 「パターンの長さ-1」に初期化する
        int i = patLen - 1;

        // テキストの最後尾に行き当たるまで繰り返す
        while (i < textLen) {

            // 注目しているパターンの位置を表すポインタ
            // パターンの最後の文字を指すようにする
            int j = patLen - 1;

            // テキストとパターンが一致する間、繰り返す
            while (text.charAt(i) == pattern.charAt(j)) {

                // 最後まで文字が一致したら、探索は成功である
                if (j == 0) return i;

                // ポインタiとjをそれぞれ1文字文戻す
                i--; j--;
            }

            // 一致しなかったので、パターンをずらす
            i = i + Math.max(skip[text.charAt(i)], patLen - j);
        }

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

定本Javaプログラマのためのアルゴリズムとデータ構造

*1:近藤嘉雪著,「定本Javaプログラマのためのアルゴリズムとデータ構造」,SBクリエイティブ,2011