2

Book Algorithms 4thで KMP アルゴリズムを学んでいます。アルゴリズムのほとんどは理解できましたが、dfa 構築のプロセスで数日間立ち往生しています。

ABABACたとえば、パターンを見てみましょう。(dfa の状態が 5) で不一致がある場合C、テキスト内の文字を右にシフトする必要があります。したがって、私たちが知っているパターン文字はBABA. しかし、建設中にdfaの次の状態をどのように把握するのでしょうか? 以下のテキストが理解できませんでした。

たとえば、j=5 で不一致がある場合に DFA が何をすべきかを決定するにはABABAC、DFA を使用して、フル バックアップを行うと状態 3 になることを学習します。BABAしたがって、にコピーできdfa[][3]ますdfa[][5]。

「フル バックアップを実行すると状態 3 になる」とはどういう意味BABAですか? また、指定された入力がない場合にこの結論を得るにはどうすればよいですか? そして文章に残されているグラフが理解できません。誰がそれが何を意味するのか説明できますか? 数日間自分で理解しようとしましたが、まだ理解できませんでした。ありがとうございました！

また、アルゴリズム 4 のセグメントはこちらで読むことができます。

DFA 建設

4

1 に答える 1

5

入力文字列を照合する場合、パターンの最初の 5 文字を照合した後にのみ状態 5 に入ることができ、パターンの最初の 5 文字はABABA. したがって、どの入力文字列を使用しても、状態 5 の前のテキストは "ABABA" であることがわかります。

したがって、状態 5 で不一致が発生した場合は、4 文字をバックアップして、もう一度一致を試みることができます。しかし、状態 5 の前にどのテキストを表示する必要があるかはわかっているので、何が起こるかを理解するために入力テキストは実際には必要ありません。同じ場所に戻ったときにどのような状態になるかを事前に把握できます。

4 文字をバックアップし、状態 0 に移動します。

0 : ババ

A が一致しないので、進み、状態 0 に移動します

0: あば

A が一致するので、状態 1 に移動します。

1: バ

B マッチ、ステート 2 へ

2: あ

A が一致し、状態 3 に進む

3:

ここで、以前に状態 5 を見た入力の場所に戻りましたが、現在は状態 3 です。

これは、状態 5 で不一致が発生したときに必ず発生するため、実際にこれを行う代わりに、「状態 5 で不一致が発生した場合は状態 3 に進む」というメモを作成するだけです。

ほとんどの KMP 実装では、実際には障害テーブルが作成されることに注意してくださいfailure_table[5]=3。実装例はDFA[char][state]代わりに完全なものを構築しているため、失敗の場合に状態 3 から状態 5 へのすべての遷移をコピーします。これは、「状態 5 で不一致が発生した場合は、状態 3 で行うことをすべて行う」ということであり、結果は同じです。

先に進む前に、上記のすべてを理解してください

それでは、これらの故障状態の計算を高速化しましょう...

状態 5 で不一致が発生した場合、これまでの DFA を使用して、DFA を "BABA" に適用することにより、次の可能な一致から入力をバックアップして再スキャンした場合に何が起こるかを把握できます。最終的に状態 3 になるので、状態 3 を状態 5 の「失敗状態」と呼びましょう。

状態 5 の障害状態を計算するには、4 つのパターン文字を処理する必要があるように見えますが、状態 4 の障害状態を計算したときに、その作業のほとんどを既に行っています。DFA を「BAB」に適用すると、状態 2。

したがって、状態 5 の失敗状態を把握するには、状態 4 (状態 2) の失敗状態から開始し、パターン内の次の文字 (入力で状態 4 の後に来る "A") を処理します。

于 2016-04-30T12:14:15.413 に答える