問題タブ [trie]

辞書の単語の一般的なトライが構築されていると仮定すると、スペルミスの4つのケース（トラバーサル中の置換、削除、転置、挿入）をチェックするための最良の方法は何でしょうか？

1つの方法は、特定の単語のn個の編集距離内にあるすべての単語を把握し、Trieでそれらをチェックすることです。これは悪いオプションではありませんが、ここでのより良い直感は、トラバーサル中に単語を変更した後、動的計画法（または再帰的な同等の方法）を使用して最適なサブトライを決定することです。

どんなアイデアでも大歓迎です！

PS、回答のリンクだけでなく、実際の入力をいただければ幸いです。

楽しいという理由だけで、今日はトライを実装しました。現時点では add() と search() をサポートしており、remove() も実装する必要がありますが、それはかなり簡単だと思います。

それは完全に機能しますが、Trie にデータを入力するには少し時間がかかりすぎます。このリストをデータソースとして使用しています: http://www.isc.ro/lists/twl06.zip (SO の別の場所にあります)。読み込みには最大 11 秒かかります。私の最初の実装には約15秒かかったので、すでにパフォーマンスが向上しましたが、まだ満足していません:)

私の質問は、他に何が (実質的な) パフォーマンスの向上をもたらすでしょうか? 私はこの設計に拘束されません。完全なオーバーホールは受け入れられます。

私は Tries と Suffix Trees を研究しており、同じものを実装したいと考えていました。最初に実装の構造と基本的な考え方についてのアイデアを得ることができるいくつかのリンクを共有してください。

含まれている場合、良い例はプラスになります。

C での実装。

OK、試行はしばらく前から行われています。典型的な実装では、データセットのサイズ n (m はメッセージの長さ) とは無関係に、O(m) ルックアップ、挿入、および削除操作を提供する必要があります。ただし、この同じ実装は、最悪の場合、入力バイトごとに 256 ワードを使用します。

他のデータ構造、特にハッシュでは、O(m) ルックアップ、挿入、および削除が期待でき、一定時間のルックアップを提供する実装もあります。それにもかかわらず、最悪の場合、ルーチンは停止しないか、O(nm) 時間かかります。

問題は、O(m) ルックアップ、挿入、および削除時間を提供しながら、ハッシュまたは検索ツリーに匹敵するメモリ フットプリントを維持するデータ構造があるかどうかです。

時間的にも空間的にも、最悪の場合の動作にのみ関心があると言うのが適切かもしれません。

フリー ライセンスでリリースされた ANSI C HAT-trie の実装を探しています。見つけたことがありません。スタンドアロンの実装、または HAT 試行を使用して正しい方法で実装する方法を少しでも理解できるプログラムを教えてください。

HAT-trie に関する元の論文は、http: //crpit.com/confpapers/CRPITV62Askitis.pdfにあります。

PS: 上記の論文が書かれた時点から、文字列に適した構造の高速なキャッシュを意識したデータが進化した場合は、論文またはサンプル ソース コードを参照してください。

文字列が辞書に存在するかどうかに一致するC++関数を作成しようとしています。部分的な文字列でも完全な文字列でもかまいません。だから私はすべての行をトライに読みました

誰かがこれを手伝ってくれませんか。辞書の単語を読むためのコードを追加しました。

私はトライの背後にある概念を理解しています。しかし、実装に関しては少し混乱します。

Trieタイプを構造化するために私が考えることができる最も明白な方法はTrie、内部を維持することDictionary<char, Trie>です。私は実際にこのように書いたので、それは機能しますが...これはやり過ぎのようです。私の印象では、トライは軽量である必要があり、ノードごとDictionary<char, Trie>に個別に設定することは、私にはそれほど軽量ではないように思われます。

私が見逃しているこの構造を実装するためのより適切な方法はありますか？

更新：OK！Jonとleppieからの非常に有益な入力に基づいて、これは私がこれまでに思いついたものです。

（1）Trieタイプのプライベート_nodesメンバーを持つタイプがありTrie.INodeCollectionます。

（2）Trie.INodeCollectionインターフェイスには次のメンバーがあります。

（3）このインターフェースには3つの実装があります。

（4）aTrieが最初に構築されるとき、その_nodesメンバーはnullです。上記の手順に従って、の最初の呼び出しでをAdd作成しSingleNode、その後の呼び出しでそこから移動します。Add

これは意味がありますか？これは、aの「かさばり」をいくらか減らすという意味での改善のように感じます（ノードは、十分な数の子ができるまで、Trie本格的なオブジェクトではなくなります）。Dictionary<char, Trie>ただし、それは非常に複雑になっています。複雑すぎませんか？簡単なはずの何かを達成するために複雑なルートをとったことがありますか？

これは簡単な質問のように聞こえますが、その答えを検索する方法がわかりません。

辞書ファイルから約80Kの単語を保存するC＃のトライ実装があります。これらすべての単語をロードするにはかなりの時間がかかります（5分以上）。アプリケーションを起動するたびにすべての単語をリロードする必要がないように、これらのデータを「永続化」するための最良の方法は何でしょうか。

ありがとう。

最近、私は Patricia の試行を研究しており、STL ソート連想コンテナーとして使用できる非常に優れたC++ 実装を使用しています。パトリシアの試行は、通常のバイナリ ツリーとは異なります。これは、リーフ ノードが内部ノードを指すバック ポインターを持っているためです。それにもかかわらず、リーフ ノード バック ポインターを介して内部ノードのみにアクセスする場合は、順番にトラバーサルを行うことで、パトリシア トライをアルファベット順にトラバースすることができます。

パトリシア トライを使用して STLlower_boundと関数を実装することは可能ですか? upper_bound実際、私が使用している実装はこれらの関数を実装していますが、期待どおりに機能しません。

例えば：

HCDAを出力すると予想される場合、これはBLQを出力します。(std::setたとえば、 は確かにここで HCDA を出力します。)

このライブラリを作成した開発者に電子メールを送信しましたが、応答がありませんでした。いずれにせよ、私はパトリシアがどのように機能しようとしているのかをかなりよく理解していると感じています.lower_boundのようなものがどのように可能になるのかさえわかりません. 問題は、lower_bound が 2 つの文字列を辞書的に比較する機能に依存しているように見えることです。「GG」はツリーに存在しないため、どの要素が GG に対して >= であるかを調べる必要があります。しかし、Radix/Patricia は、ノードからノードへの移動に辞書式比較を使用しないように試みています。むしろ、各ノードは、検索キーでビット比較を実行するために使用されるビット インデックスを格納します。ビット比較の結果は、左に移動するか右に移動するかを示します。これにより、ツリー内の特定のプレフィックスを簡単に見つけることができます。しかし、プレフィックスがツリーに存在しない場合、

私が使用している C++ 実装が lower_bound を適切に実装していないように見えるという事実は、それが可能ではないかもしれないという私の疑いを裏付けています。それでも、ツリーをアルファベット順に反復できるという事実は、それを行う方法があるかもしれないと私に思わせます。

誰もこれを経験したことがありますか、またはパトリシアトライでlower_bound機能を実装できるかどうか知っていますか?

JavaでTrieデータ構造を実装するための詳細情報を提供するライブラリまたはドキュメント/リンクはありますか？

どんな助けでも素晴らしいでしょう！

ありがとう。