KMP法とは
前回の力まかせ法では、不一致の文字に出会った場合、
パターンを移動して、パターンの先頭からテキストとの照合を行なっていましたが、
移動の度に照合結果が先頭に戻ってしまうので、その点は非効率であるといえます。
そんな非効率な部分を有効活用したのがこのKMP法らしいです。
ZABCABXACCAD というテキストから ABCABDというパターンを探索するとして、
まず最初はテキストとパターンの先頭文字から順に照合を行います。
テキストの先頭文字 Zは、パターンには含まれない文字なので、不一致として、パターンを1文字進めます。
パターンの先頭から順に照合していくと、パターンの末尾文字DがテキストXと一致しません。
ここで改めて文字列を見てみると、テキスト側のABと、パターンの先頭にあるABが一致していることが分かります。
力まかせであれば、そのままパターンを1文字進めるだけですが、
このAB部分を照合済とみなせれば
テキスト側のX以降の部分から、
パターンのCABDと一致するかを調べれば良いことになります。
そこで、次のようにABが重なるようパターンを一気に3文字ズラすと、
パターンの3文字目であるCからテキストとの照合を開始することができます。
このように、KMP法はテキストとパターン中の重なっている部分をうまく見つけ出し、
照合を再開する位置を求め、パターンの移動をなるべく大きくしようというアルゴリズムだそうです。
何文字目から照合を再開するのかを、パターンを移動するたびに計算し直していると、高い効率は望めないので
その値を事前に<表>として作成しておけば、照合結果によってズラす文字数を決めることができます。
この表の作成にあたっては、パターン内の ”重複した文字の並び”を見付ける必要があります。
もし、パターンの1文字目が不一致の場合、
パターンを1文字ずらして先頭文字から照合を合わせなければならないのは自明なので、
パターンがテキストの2文字目以降に移動した時を考えていきます。
また、パターン内で同じ文字列があった場合の移動なので、パターン同士を重ね合わせて計算します。
まずはパターンABCAD同士を1文字ずらして重ね合わせてみましょう。
この時点で、青文字部分に重なりはないので、
もしパターンの2文字目がテキストと不一致だった場合は、
パターンの頭から照合を再開しなければいけないことが分かるので
、2文字目Bの再開値を0とします
。
この再開値は、パターンの1文字目のインデックスが0であり、その位置から照合を再開するという見方になります。
またパターンを1文字ズラします。
やはり文字は一致しないので、3文字目Cの再開値も0となります。
もう1文字ずららしたところで初めてABが一致し他ので、次のことが分かります。
- もし、パターンの4文字目の
Aまで一致していれば、パターン移動後にAをスキップして 2文字目から照合できる - もし、パターンの5文字目の
Bも一致してれば、パターン移動後にABをスキップして3文字目から照合できる
そこで、これらの文字の再開値は、パターンの配列上インデックスでは 1 と 2ということになります
。
Aが一致していれば、 Bからなので、1 ABが一致していれば、Cからなので 2 ということです。
最後のDと比べてみると、ここでは一致しないので、末尾文字の再開値は0となります。
つまり、パターンの文字列の中に、同じ文字列が含まれていた場合、(ABCABDのようにABが2つある場合)
テキスト内のカーソルをスキップさせることができるので、そこで何文字スキップするのかという表を作成することができました。
コードに落とし込んでみる
static int kmpMatch(String target, String pat) {
int pt = 1; // targetをなぞるカーソル
int pp = 0; // patをなぞるカーソル
int[] skip = new int[pat.length() + 1]; // スキップテーブル
// スキップテーブルの作成
skip[pt] = 0;
while (pt != pat.length()) {
System.out.println(pt + "," + pp);
if (pat.charAt(pt) == pat.charAt(pp)) {
skip[++pt] = ++pp;
} else if (pp == 0) {
skip[++pt] = pp;
} else {
pp = skip[pp];
}
for(int a : skip)
System.out.print(a + ",");
System.out.println();
}
KmpMatchメソッドが受け取る引数や返り値は、力まかせ法の関数bfMatchと変わりません。
最初にスキップテーブルを作成し、その後探索を行うという流れになります。
スキップテーブルの作成は
まず、patの長さ + 1のテーブルを作成し、ptは1 ppは0として、ずらして比較できるようにしています。
最初はif (pat.charAt(pt) == pat.charAt(pp))にて 1文字ずらした状態で照合を行い、
一致していれば、1,2,3とインクリメントした値を追加、
不一致であり、パターンの1文字目であればそのまま0を代入（パターンの最初から）
不一致であり、カーソルがパターンの2文字目以降であった場合、表の値をそのままパターンのカーソルに代入するという流れです。
ABAABDCというパターンで実際に流れを追っていきましょう。
1文字ズラしだけでは不一致なので、ppは0となり、表に0を代入し、ptは前置インクリメントして2となります。
3文字目のAと一致したので、skip[3]に 1を代入し、pt 3 pp 1で比較します。
ここは不一致ですが、ppは1なので、 skip[1]の値である 0を ppに代入し、pt 3 pp 0で比較します。
一致したので、skip[4]に 1を代入し、（ppを前置インクリメント）pt 4 pp 1で比較します。
一致したので、skip[5]に 2を代入し、pt5 pp 2で比較します。
不一致で、ppは2なので、skip[2]の0を ppに代入し、pt 5 pp 0で比較します。
不一致で ppは0なので、表に0を代入し、ptは6 ppは0で比較します。
不一致でppは0なので、表に0を代入した時点で、表が完成します。
この表を見る限り、
もしABAorABAAまで一致していれば、先頭のAをスキップして、2文字目のBから
ABAABまで一致してれば、 先頭のABをスキップして3文字目のAから探索を再開すればいいということになります。
ここまで表がわかれば、あとは同様に探索を行うだけです。
// 探索
pt = pp = 0;
while (pt != target.length() && pp != pat.length()){
if (target.charAt(pt) == pat.charAt(pp)) {
pt++;
pp++;
} else if (pp == 0)
pt++;
else
pp = skip[pp];
}
if (pp == pat.length()) // パターンの全文字を照合
return pt - pp;
return -1; // 探索失敗
}
一致していればターゲットも、パターンのカーソルも1個ずつ進め、
不一致かつ、パターンの1文字目で不一致であれば、ターゲットのカーソルだけを1個進める。
不一致かつ、パターンの2文字目以降であれば、パターンのカーソルを表に合わせて進めるという流れになります。
このように、KMP法では、テキストを走査するカーソルptは前進するだけで後退することはありません。
プログラム自体は複雑ですが、Boyer-Moore法と同等以下の性能しか発揮できないので、それほど利用されないらしいです汗
学んだこと
- パターン内に同様の文字列があった場合、照合カーソルをいちいち後退させる必要がなくなるのがKMPの特徴
- パターン内に繰り返される文字がなければ、あまり効果がないのも事実。
パターン内に繰り返しがあれば、一致した位置によっては無駄な照合をする必要がなくなる
という方法はなるほどと思いましたが、実際に探索するパターンに都合よく繰り返しがあるとも限らないので
そういう考え方もあるよということで、引き続き頑張っていきます！