5

私は現在 DAWG を調べていますが、非循環オートマトンを構築する良い方法を見つけることができませんでした。

基本的に、私がやりたいことはこれです:

DAWG

これは基本的にツリーであり、状態の数が減っています。数字で使用しますが、概念はまったく同じです。

どうするのが一番早いのだろうと思いますが、私の実際の計画は、左のようにグラフを作成し、低レベルの状態を見て、それらが類似しているときはそれらをマージすることでした。

ただし、これが最善の方法であるかどうかはわかりませんが、それを構築する方法についてアイデアを持っている人はいますか。

よろしく。

4

1 に答える 1

3

DAWG は、文字列を格納する場合、特定のセットの最小状態の有限オートマトンです。トライを非最小有限オートマトンとして扱い、標準の DFA 最小化アルゴリズムを実行することで、それらを構築できます。これは、おそらく DAWG を構築する最も簡単な方法であり、おそらく最も速い方法でもあります。

お役に立てれば!

于 2013-10-08T18:06:03.123 に答える