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

Question

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

私は、アルゴリズム自体を理解し、しかし、どのようにクヌース、モリスとプラットは、このアルゴリズムを考案したのを理解していません。

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

リンクをお願いできますか？

Answer 1

KMPマッチングアルゴリズムはfinite automataに基づいて暗黙的に文字列と一致するオートマトンのための遷移テーブルを構築することによって動作されます。検索する文字列の非常に賢い線形時間の前処理を使用すると、一致するオートマトンを構築することができ、その後、オートマトンをその文字列上でシミュレートして線形時間で検索することができます。正味の結果は、文字列マッチングのための線形時間アルゴリズムです。これまでに一致した文字列の各量のための一つの状態を持つことで作品を構築しています

オートマトン。デフォルトでは、次の文字とのマッチングがマシンの次の状態に進み、無効な文字の読みが先頭に戻ります。しかし、検索する文字列の一部が重なり合った構造を共有している可能性があるため、文字を読み込んだときにオートマトンを元の状態（最初の状態ではない）に戻す新しい遷移がいくつか追加されます。

このアルゴリズムは、一度に複数の文字列を検索するために、より複雑なオートマトンを構築エイホ - コラシック法によって一般化されます。

私はアルゴリズムが正しさの証明、アルゴリズムの背後にあるより正式な直感、および第一原理からのアルゴリズムを導出する方法の説明を含め、どのように動作するかの実際の内容の広範な議論が含まれていan implementation of this algorithm on my personal siteを持っています。まとめにはしばらく時間がかかりましたが、アルゴリズムについてもっと知るには良いリソースになると思います。

希望すると便利です。

Answer 2

モリスはアルゴリズムを第1の原理から発見したが、Knuthはスティーブン・A・クックによる定理について独立に学んだ。決定論的2ウェイプッシュダウンオートマトンを線形時間でシミュレートし、シミュレーションはオートマトンに一致する文字列に変換されます。 Prattは効率改善に貢献しました。 Knuth's retellingを参照してください。