c++ - DAWG の作成方法

Question

DAWGはどのように作成できますか? 2 つの方法があることがわかりました。1 つはトライを dawg に変換し、もう 1 つはすぐに新しい DAWG を作成しますか? どれが一番簡単ですか？2つについて詳しく説明し、いくつかのリンクを提供していただけますか?

Answer 1

DAWG について考える 1 つの方法は、単語リスト内のすべての単語の最小状態の DFA と見なすことです。その結果、DAWG を構築するための従来のアルゴリズムは次のようになります。

1. 単語のコレクションのトライを構築することから始めます。
2. すべての入力でそれ自体からそれ自体へのエッジを持つ新しいノードをトライに追加します。
3. トライに欠落している文字遷移ごとに、開始ノードからこの新しいデッド ノードへの遷移を追加します。
4. (この時点で、単語セットの (おそらく最小ではない) DFAが得られます。)
5. DFA 状態最小化の標準アルゴリズムを使用して DFA を最小化します。

これが完了すると、関心のある単語セットの DAWG が残ります。

このアルゴリズムの実行時間は次のとおりです。最初の DFA の構築は、すべての元の単語のトライを構築し (O(n) の時間がかかります。ここで、n はすべての入力文字列の文字の総数です)、不足しているトランジションを埋めます (時間がかかります)。 O(n|Σ|)、|Σ| はアルファベットの異なる文字の数です)。そこから、最小化アルゴリズムは時間 O(n ² |Σ|) で実行されます。これは、アルゴリズムの全体的な実行時間が O(n ² |Σ|) であることを意味します。

私の知る限り、DAWG を段階的に構築するための簡単なアルゴリズムはありません。通常、すべての単語が事前に用意されている場合にのみ、一連の単語に対して DAWG を作成します。直観的には、DAWG に既に存在するいくつかの接尾辞を持つ新しい単語を挿入すると、特定の古い受け入れ状態を受け入れないようにするために DAWG の多くの再構築が必要になる可能性があるため、これは真実です。理論的に言えば、新しい単語を挿入すると、DFA の識別可能性関係の等価クラスが劇的に変化し、DFA の構造に大幅な変更が必要になる可能性があるためです。

お役に立てれば！