私は現在DAWGを調べていますが、私は非循環オートマトンを構築する良い方法を見つけることができませんでした。Directed Acyclic Word Graph（DAWG）を構築する最善の方法
だから、基本的に、私がやりたいことはこれです：それは基本的に状態の数が減少している木、ある
。私は数字でそれを使用しますが、コンセプトはまったく同じです。
これを実行する最も速い方法は何だろうと思います。私の実際の計画は、左のようにグラフを作成し、低レベルの状態を見て、類似したものをマージすることでした。
私はこれを実行する最善の方法であるとは思っていませんが、誰でもそれを構築する方法について考えていますか？
よろしくお願いいたします。
DAWGは、格納されている文字列の場合、特定のセットの最小状態有限オートマトンです。あなたは、最小限の有限オートマトンとして持っているトライを扱い、その上で標準的なDFA最小化アルゴリズムを実行することでそれらを構築することができます。おそらくこれはDAWGを構築する最も簡単な方法で、おそらく最も速い方法です。
希望すると便利です。
ええ、ええ、複数の最小化アルゴリズムがありますが、私はDAWGを自分で構築する方が好きです。いくつかのポイント。私は実際には、ツリー→DAWGを得るための擬似コードを探しています。 – Anoracx
@ Anoracx-私はあなたが求めていることについて混乱していると思います。トライ→DAWGステップは、DFA最小化ステップです。 「DAWGを自分で作る」という意味はどうですか？ – templatetypedef
私は、ウィキペディアから、DAWG（DAFSA）は通常のツリー/ DFAから構築されたタイプのツリーであると考えました。だから私は実際にそれを行う特定のアルゴリズムがあると思っていました。最小化アルゴリズムだけではありません。だから私は自分でやりたいと言ったときに、実際にDFAからDAFSA（DAWG）に変換する方法を探していました。 – Anoracx
DFAの表現があります。あなたはそれを最小限のDFA（かなり標準的なアルゴリズムがあります）に減らすことができます – SheetJS
私は知っていますが、私は実際にその1つ（または擬似コード）を行う方法を探しています – Anoracx
https://en.wikipedia.org/wiki /DFA_minimization#Hopcroft.27s_algorithm – SheetJS