文字列探索のアルゴリズム
文字列の探索について
以下ではパターンを 文字、テキストを 文字とします。
力まかせ法
考え方
テキストの先頭とパターンを重ねます。パターンとテキストが一致すれば探索は成功。不一致の場合は、パターンを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; } }
- 作者: 近藤嘉雪
- 出版社/メーカー: SBクリエイティブ
- 発売日: 2011/01/26
- メディア: 単行本
- 購入: 1人 クリック: 15回
- この商品を含むブログ (5件) を見る