【初心者向け🔰】力任せ法との違いで確認するKMP法
文字列検索のアルゴリズムで有名なKMP法（Knuth-Morris-Pratt法）は、無駄な比較を減らし効率的にパターンマッチングを行う手法です。私自身の理解促進も兼ねて、KMP法の基本アイディアと動作を解説します。
なお、本記事では、検索したい文字列パターンをクエリ、クエリが存在するかを調べたい文字列をテキストと表記します。
力任せ法の限界
文字列検索アルゴリズムの一番単純な形は力任せ法(別名:ナイーブ法)であることに異論を挟む人はほぼいないのではないでしょうか。ここに文字数nのテキストと文字数mのクエリがあります。テキストの先頭から一文字ずつクエリと比較し、一致するまで進めます。
しかし、この方法では最悪計算量がO(nm)となり、長い文字列では非効率的です。例えば、以下の例では20回の比較が必要です。
text: ABABAABABAB
query: ABABAB
KMP法は、これを14回の比較にまで減らします。
アルゴリズムの要: Failure Table
KMP法の核となるアイディアは、比較に失敗したときでも、すでにマッチングした部分を最大限利用することです。そのために「Failure Table」を用いて次の比較位置を決定します。(そのほかに移動量テーブル/部分マッチテーブルなど複数の呼び方あり)
Failure Tableには2つの特徴があります。1つ目の特徴は、元のクエリから1文字ずつ追加しながら行数が増加している点です。これは各行がテキスト/クエリがどのタイミングで一致するかの場合分けです。2つ目の特徴は、各行のパターンからprefix/suffixを抽出し、一致した文字数をshiftを算出している点です。この数値は、パターン別にクエリ内で同一の文字列が再出現する最長の長さを表しています。つまりテキスト/クエリの不一致が発生した際、どれくらいまでスキップして次の調査を始めてよいかをこの数値で決定しているのですね。
Failure Tableはクエリのみから作成されます。1文字-m文字まで一文字ずつ文字を増やしていった場合、prefix/suffixがどれくらい一致するかという代物です。実際の計算例を見ていただけると理解が早いと思います。
query: ABABAB
| PATTERN | PREFIX + (others) | (others) + SUFFIX | SHIFT |
|---|---|---|---|
| A | - | - | 0 |
| AB | A + (b) | (a) B | 0 |
| ABA | A + (ba) | (ab) + A | 1 |
| ABAB | AB + (ab) | (ab) + AB | 2 |
| ABABA | ABA + (ba) | (ab) + ABA | 3 |
| ABABAB | ABAB + (ab) | (ab) + ABAB | 4 |
具体例でみるFailureTableの使い方
実際にこの表を利用しながら、KMP法でのパターンマッチングを図示するとこのようになります。text,queryは前述のものと同様のものとします。
1回目の試行では、アルゴリズムは5文字目までマッチングに成功します。しかし、最後の1文字でアンマッチが発生します。このとき、テキストの次の文字から比較を再開するのではなく、KMPアルゴリズムはFailure Tableを使って、現在の位置から続けるか、少し戻るかを判断します。
以下はその手順です：
- アルゴリズムは、最後に一致した文字が5文字目（
A）であることを特定します。これはFailure Tableのインデックス4に対応します。 - Failure Tableによれば、
FailureTable[4] = Aとなり、部分的な重複がある可能性が示されています。この位置のシフト値は3です。 - つまり、次の比較は
text[5]とpattern[3]から再開でき、無駄な比較をスキップします。
この効率的なスキップにより、既に一致した部分を再確認することなく、計算コストを削減できます。今回は力任せ法20回、KMP法は14回となり、比較回数の削減を達成しました。なお、計算量の観点では、Failure Tableの構築はO(m),検索プロセスはO(n)なので、最悪計算量はO(n + m)となります。
覚えておきたいポイントとしては、KMP法では、テキスト側のインデックスは後戻りしません。この特徴を意識すると、実装時に混乱を防ぐことができるかと思います。
KMP法は、一見複雑に見えるかもしれませんが、その核となるアイディアは「無駄な比較を減らす」というシンプルなものです。Failure Tableを理解し、活用することで、効率的な文字列検索が可能になります。この記事を通じて、KMP法の基本をつかんでいただけたなら幸いです。
Discussion