2

DAWG を使用して、各パスに関連する補助情報 (英語の単語の頻度など) を保存できますか? はいの場合、どうすればそれを行うことができますか?

4

3 に答える 3

2

はい、一般に、有向非巡回加重グラフ（DAWG）は、ノード、エッジ、またはノードとエッジのシーケンスを取得する特定のパスなどのより複雑な構造のいずれかによって注釈を付けることができます。既存の構造をサブクラス化してこの情報を含めることができます。これが不可能な場合は、構造から注釈にハッシュすることができます。

于 2012-12-24T20:29:12.390 に答える
2

通常、トライやその他のデータ構造の場合と同じように、単語ごとの情報を DAWG に格納することはできません。この理由は、DAWG 内の複数の異なる単語がすべてノードを共有する可能性があるため、ある単語の情報が他の単語の情報に「漏れる」リスクがあるためです。

簡単な例として、「is」、「as」、「i」、および「a」という単語の DAWG があるとします。その場合、DAWG は次のようになります。

                     START
                  a /     \ i
                   ACC    ACC
                 s  \     / s                        
                      ACC

「as」と「is」という単語を表すノードは、まったく同じノードであることに注意してください。したがって、「as」という単語に情報を注釈付けしようとすると、その情報を保持するノードも「is」のノードと同じになります。つまり、「as」と「is」はどちらも同じものを取得します。情報のセット。

「as」および「is」のノードにマップを保存することで、これを回避しようとすることができます。このマップは、そのノードで終わる単語からその単語に関する追加情報にマップされますが、これにより、DAWG のメモリ使用量が劇的に増加します。各文字を単語に保存しているため、メモリ使用量が大幅に増加します (DAWG の全体的なポイントは、一連の単語を保存するために必要なメモリ使用量を削減することです)。単語から情報にマップするハッシュ テーブルを格納するだけのほうがよいでしょう。

この情報を保存しようとする別のオプションは、DAWG を通る各パスを独自のブランチに展開して、異なる単語のノードが常に異なるようにすることです。ただし、このアプローチの問題点は、DAWG を効果的にトライに変換しているため、関連するメモリ使用量が劇的に増加することです。

つまり、メモリ使用量を大幅に増加させずに、DAWG 内の単語にメタ情報で注釈を付ける簡単な方法はありません。これを行う必要がある場合は、別のデータ構造を使用することをお勧めします。

お役に立てれば！

于 2012-12-24T21:38:19.250 に答える