問題タブ [dawg]

TrieではなくDAWG（Directed Acyclic Word Graph）で使用されるようにAho-Corasick文字列マッチングアルゴリズムを変更できるかどうか誰かが知っていますか？

私はトライと DAWG (直接非巡回ワード グラフ) に興味があり、それらについて多くのことを読んできましたが、出力トライまたは DAWG ファイルがどのように見えるべきかわかりません。

• トライはネストされた辞書のオブジェクトであるべきですか? 各文字が文字などに分割されている場所はどこですか?
• 100k または 500k のエントリがある場合、そのような辞書で実行されるルックアップは高速でしょうか?
• -またはスペースで区切られた複数の単語で構成される単語ブロックを実装する方法は?
• 単語の接頭辞または接尾辞を構造内の別の部分にリンクする方法は? (DAWG用)

出力構造を作成して使用する方法を理解するために、最適な出力構造を理解したいと考えています。

また、 DAWGとtrieの出力がどうあるべきかを評価します。

バブルが相互にリンクされたグラフィカルな表現を見たくありません。一連の単語が試行または DAWG に変換された後の出力オブジェクトを知りたいのです。

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

特定の単語が辞書 (英語の単語リスト) にあるかどうかをすばやく確認できる必要があります。メンバーシップをチェックする速度 (要素の追加や削除ではありません) だけに関心があり、メモリの使用は実際には問題ではありません。

もともと私はこのようなセットを使用していました：

私のプログラムは約かかりました。テスト入力で実行するのに 4 秒。次に、DAWG ( http://pypi.python.org/pypi/pyDAWG ) を使用して、代わりに DAWG を事前計算して酸洗いすることで最適化を試みました。

同じテスト入力で、プログラムの実行に約 40 秒かかりました (私が気にしない DAWG をロードするのに数秒かかりました)。私は、DAWG を使用すると物事がより速く実行されることを望んでいました!

python がどのように物事をハッシュするかについての理解が欠けているのかもしれません - DAWG や Trie ではなく、私が取得しようとしているセット (O(1) メンバーシップ テスト?) はすでに最高ですか? DAWG はメモリを節約しますが、計算は節約しませんか?

どうもありがとう！

語彙のトライを作成したところ、同じ構造体を共有する多くのブランチがあることがわかりました。それらを組み合わせて、結果をDAWGにしたい。

トライを DAWG に変換するには、どのアルゴリズムを使用しますか?

ユーザーが入力した単語を検証する DAWG 構造を作成しようとしています。これは、Android アプリで使用されます。私の最善の選択肢は、アプリの外部で DAWG 構造をシリアル化し、開始時にロードすることでしょうか? または、DAWG を使用するためのより良い方法はありますか?

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

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

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

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

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

よろしく。

長い文字列の一部を効率的なツリーのような構造に格納しようとしています。検索しましたが、ほとんどの実装は単語内を検索するためのものです...例を挙げて説明します。 :

私の最初の考えは、これはこのように見えるべきだということでした

私が検索した限り、本当に効率的な検索ツリー (DAWG や Tries など) は単語を文字として保存するためのものであり、どのように使用すればよいかわかりません。何か案は？

よろしくお願いします！

編集:永続性に関する限り、ツリーを保存する必要はないので、プログラムが実行されている限りメモリに保持することを考えました。

Edit2:子の格納に関する限り、私はHybridDictionariesを使用することになりました。これは Dictionaries よりも効率的であり、すべてが非常に高速に動作するようになりました。どうもありがとう!

効率的な検索と挿入をサポートする、動的文字列用の文字列ルックアップ データ構造を実装したいと考えています。現在、トライを使用していますが、可能であればメモリ フットプリントを減らしたいと考えています。 このウィキペディアの記事では、DAWG/DAFSA について説明しています。これは、接尾辞を圧縮することで、試行よりも明らかに多くのスペースを節約します。ただし、文字列が合法かどうかは明確にテストされますが、違法な文字列を除外する方法があるかどうかはわかりません。たとえば、「cite」と「cat」という単語を使用すると、「t」と「e」は最終状態であり、DAWG/DAFSA は次のようになります。

また、"cit" と "cate" は、メタ情報を持たない正当な文字列として誤って認識されます。

質問:

1) 文字列/パス (合法性など) に関するメタ情報を DAWG/DAFSA に格納するための推奨される方法はありますか?

2) DAWG/DAFSA が要件 (効率的な検索/挿入およびメタ情報の保存) と互換性がない場合、使用するのに最適なデータ構造は何ですか? 最小限のメモリ フットプリントがあればよいのですが、絶対に必要というわけではありません。