DAWGはどのように作成できますか? 2 つの方法があることがわかりました。1 つはトライを dawg に変換し、もう 1 つはすぐに新しい DAWG を作成しますか? どれが一番簡単ですか?2つについて詳しく説明し、いくつかのリンクを提供していただけますか?
1 に答える
DAWG について考える 1 つの方法は、単語リスト内のすべての単語の最小状態の DFA と見なすことです。その結果、DAWG を構築するための従来のアルゴリズムは次のようになります。
- 単語のコレクションのトライを構築することから始めます。
- すべての入力でそれ自体からそれ自体へのエッジを持つ新しいノードをトライに追加します。
- トライに欠落している文字遷移ごとに、開始ノードからこの新しいデッド ノードへの遷移を追加します。
- (この時点で、単語セットの (おそらく最小ではない) DFAが得られます。)
- DFA 状態最小化の標準アルゴリズムを使用して DFA を最小化します。
これが完了すると、関心のある単語セットの DAWG が残ります。
このアルゴリズムの実行時間は次のとおりです。最初の DFA の構築は、すべての元の単語のトライを構築し (O(n) の時間がかかります。ここで、n はすべての入力文字列の文字の総数です)、不足しているトランジションを埋めます (時間がかかります)。 O(n|Σ|)、|Σ| はアルファベットの異なる文字の数です)。そこから、最小化アルゴリズムは時間 O(n 2 |Σ|) で実行されます。これは、アルゴリズムの全体的な実行時間が O(n 2 |Σ|) であることを意味します。
私の知る限り、DAWG を段階的に構築するための簡単なアルゴリズムはありません。通常、すべての単語が事前に用意されている場合にのみ、一連の単語に対して DAWG を作成します。直観的には、DAWG に既に存在するいくつかの接尾辞を持つ新しい単語を挿入すると、特定の古い受け入れ状態を受け入れないようにするために DAWG の多くの再構築が必要になる可能性があるため、これは真実です。理論的に言えば、新しい単語を挿入すると、DFA の識別可能性関係の等価クラスが劇的に変化し、DFA の構造に大幅な変更が必要になる可能性があるためです。
お役に立てれば!