1. 概要

コンピュータサイエンスでは、多くの文字列検索アルゴリズムがあります。 この記事では、大きなテキスト内の単語の出現を検索するKMP（Knuth-Morris-Pratt）アルゴリズムを紹介します。

まず、素朴な探索アルゴリズムについて説明します。

次に、KMPアルゴリズムの背後にある理論的考え方について説明します。

最後に、それがどのように機能するかをよりよく理解するために例を見ていきます。

2. ナイーブ検索アルゴリズム

素朴な検索アルゴリズムは非常に単純です。 テキスト内のすべての可能なインデックスから始まる単語を一致させようとします。 次のアルゴリズムは、テキスト内の単語を検索するための単純なアプローチを表しています。

単語が、で、テキストが。であるとします。 ナイーブアルゴリズムの手順を示す次の表を見てみましょう。

ご覧のとおり、アルゴリズムはテキスト内の単語のすべての可能な場所をチェックします。 ただし、2番目と3番目のステップでは、アルゴリズムは単語の一部がすでに一致しているという事実を使用しませんでした。 代わりに、アルゴリズムは最初から完全な単語の照合を開始しました。

素朴なアプローチの複雑さはであることが簡単にわかります。ここで、はテキストの長さ、は単語の長さです。

3. KMPアルゴリズム

素朴なアプローチの問題は、不一致を発見すると、テキスト内の次の位置に移動し、単語の最初から比較を開始することです。 KMPアルゴリズムは、テキスト内での出現を見つける前に、単語に対していくつかの分析を実行します。

3.1. 定義

単語に対して実行される分析にジャンプする前に、いくつかの基本的な定義を見てみましょう。

  1. プレフィックス：文字列のプレフィックスは、の先頭から始まり、の任意の位置で終了する任意のサブストリングです。 つまり、範囲内の文字を取得することによって形成されるサブ文字列です。ここで、は文字列のすべての可能なインデックスを表します。
  2. サフィックス：文字列のサフィックスは、の任意の位置から始まり、の終わりで終わる任意のサブストリングです。 つまり、範囲内の文字を取得することによって形成されるサブ文字列です。ここで、は文字列のすべての可能なインデックスを表します。
  3. 適切なプレフィックス：適切なプレフィックスとは、完全な文字列と等しくないプレフィックスです。
  4. 適切なサフィックス：適切なサフィックスは、完全な文字列と等しくないサフィックスです。

3.2. LPSの理論的アイデア

お気づきのように、素朴なアプローチで不一致が見つかった場合は、次のステップで最初から開始する必要がありました。 これを回避するために、KMPアルゴリズムは、LPS配列を計算するために、最初に単語に対していくつかの計算を実行します。 LPSという用語は、適切なサフィックスでもある最長の適切なプレフィックスを指します。

単語のインデックスごとに、LPSの長さを格納する配列を作成しましょう（この配列の使用については、セクション3.4で説明します）。 後で簡単に使用できるように、単語はゼロベースのインデックス付きであると見なし、インデックス1から始まる配列内にLPS値を格納します。 つまり、インデックスごとに、範囲のLPSを格納します。

単語のLPS配列を示す次の表を見てください。

ご覧のとおり、考慮すべき適切なプレフィックスがないため、空の文字列のLPSは-1になります。 また、プレフィックスに対応するインデックス3は、適切なサフィックスが適切なプレフィックスと一致しないため、LPSがゼロになります。 ただし、プレフィックスに対応するインデックス2は、文字列が適切なプレフィックスと適切なサフィックスの両方であるため、LPSが1に等しくなります。

同じことが、プレフィックスに対応するインデックス7にも当てはまります。 文字列は適切なサフィックスでもある最長の適切なプレフィックスであるため、LPSは4になります。

3.3. LPSアルゴリズム

LPS配列を計算するためのアルゴリズムは、少し注意が必要な場合があります。 その擬似コードを見てみましょう。

まず、ベースインデックスを-1で初期化します。 次に、単語を繰り返し処理します。 前のインデックスのLPSがに等しいと仮定します。 現在のインデックスには2つのオプションがあります。 i th文字がjth 文字と一致する場合、LPSはに等しくなります（ゼロベースのインデックスが付けられていると想定します）。

ただし、一致するものがない場合は、2番目に優れたLPSに戻る必要があります。 2番目に良いLPSを計算しなかったという問題が残っています。

最後のLPSがだったので、これまでの最初の文字が最後の文字と一致することを意味します。 最初の文字に戻って、それらに対して計算されたLPSを調べてみましょう。 j th の位置に格納されているLPSは、適切な接頭辞でもある最長の適切な接尾辞に対応します。 したがって、この値は2番目に優れたLPSです。

その後、i th文字とjth文字を比較します。 それらが一致する場合、LPS配列のi thインデックスの値を更新します。 それ以外の場合は、一致するものが見つかるか、-1の値に達するまで、この手順を繰り返します。

アルゴリズムの複雑さは2乗のように見えますが、時間計算量はです。ここで、はの長さです。 この背後にある理由は、各値が1ずつ増加するためです。 どれだけ後退しても、消費量は増えた分だけになります。 したがって、ネストされた2つのwhileループは、線形の複雑さを持っています。

3.4. KMP検索

KMPアルゴリズムはLPSアレイに依存します。 単語の最初の部分をテキストと照合し始めたとします。 ある時点で、不一致に気づきました。 最初からマッチングを開始する代わりに、計算されたLPS配列を使用します。

あるステップで、テキスト内のi thインデックスと単語内のjthインデックスにいたとします。 これは、現在、単語の長さの接頭辞を一致させることができたことを意味します。 不一致が見つかった場合は、単語の2番目に長い一致するプレフィックス（。）を見つける必要があります。

不一致が続く場合は、常にに戻って再度一致を試みます。 このステップは、一致するものが見つかるか、最初の-1値に達するまで続きます。

一致するものが見つかったら、次のステップに進みます。 また、一致するパーツの長さが1つ増えたため、増加します。

説明されているアルゴリズムの擬似コードを見てみましょう。

記述されたアルゴリズムの複雑さはです。ここで、はテキストの長さです。 この複雑さの理由は、配列を計算したときと同様です。 は、ごとに1回ずつ増加するため、どれだけ戻っても、以前に実行された増分のみを消費することを意味します。 したがって、最悪の場合、合計ステップを戻します。

KMPアルゴリズムの合計時間計算量は、です。ここで、はテキストの長さであり、は単語の長さです。 これは、KMP検索ごとに、最初にLPS配列を計算してから、KMP検索プロセスを実行するためです。

4. 例

KMP検索アルゴリズムを小さな例に簡単に適用してみましょう。 テキストがに等しく、単語がに等しいと仮定します。 まず、単語のLPSテーブルを見てみましょう。

次に、KMP検索アルゴリズムを指定されたテキストに適用した結果を見てみましょう。

ご覧のとおり、3番目と4番目のステップでは、アルゴリズムは配列を使用して正しい位置に設定しました。 したがって、不一致が検出されたときに、アルゴリズムは最初から単語の照合を開始する必要はありませんでした。 これは、アルゴリズムが最後のステップで単語の出現を効率的に見つけるのに役立ちました。

5. 結論

この記事では、KMP検索アルゴリズムを紹介しました。 まず、単純なアルゴリズムについて簡単に説明しました。 次に、KMP検索アルゴリズム自体について説明します。 後でKMP検索に使用されるLPS配列について説明しました。

最後に、KMPアルゴリズムを適用して、テキスト内の特定の単語を検索する例を示しました。