string - KMPパターンマッチングアルゴリズムの背後にある理論は何ですか？

Question

KMPパターンマッチングアルゴリズムの理論的根拠は何ですか？

アルゴリズム自体は理解していますが、クヌース、モリス、プラットがこのアルゴリズムをどのように発明したのかわかりません。

数学的な証明はありましたか？

リンクをお願いします。

Answer 1

KMPマッチングアルゴリズムは有限オートマトンに基づいており、文字列に一致するオートマトンの遷移表を暗黙的に作成することで機能します。検索する文字列の非常に巧妙な線形時間前処理を使用して、一致するオートマトンを構築し、次にオートマトンを文字列上でシミュレートして線形時間で検索することができます。最終的な結果は、文字列照合の線形時間アルゴリズムです。

構築されたオートマトンは、これまでに一致した文字列の量ごとに1つの状態を持つことによって機能します。デフォルトでは、遷移は、次の文字の一致がマシンの次の状態に進み、無効な文字の読み取りが最初に戻るようなものです。ただし、検索する文字列の特定の部分が重複する構造を共有している可能性があるため、文字が読み取られたときにオートマトンを以前の（最初ではない）状態に戻すいくつかの新しい遷移が追加されます。

このアルゴリズムは、一度に複数の文字列を検索するために、より複雑なオートマトンを構築するAho-Corasickアルゴリズムによって一般化されています。

私の個人的なサイトにこのアルゴリズムの実装があり、アルゴリズムがどのように機能するかについての実際の詳細についての広範な議論が含まれています。これには、正当性の証明、アルゴリズムの背後にあるより正式な直感、および第一原理からアルゴリズムを導出する方法の説明が含まれます。まとめるのに少し時間がかかりましたが、アルゴリズムについてもっと学ぶ良いリソースになることを願っています。

お役に立てれば！

Answer 2

モリスは第一原理からアルゴリズムを発見しましたが、クヌースはスティーブンA.クックにより、決定論的な双方向プッシュダウンオートマトンを線形時間でシミュレートできるという定理について独自に学び、シミュレーションをに特化することで「KMP」の初期バージョンを抽出しました。文字列照合オートマトン。プラットは効率の改善に貢献しました。Knuthの再話を参照してください。