問題タブ [trie]

Trieを構築しようとしていますが、メモリ容量が非常に限られている携帯電話を使用しています。

数回のディスク読み取りを許容できるため、構造全体をディスクに保存し、必要に応じてのみロードするのがおそらく最善であると考えました。しかし、何度か試してみると、これは非常に複雑なことのように思えます。

Trie をディスクに保存し (つまり、部分的にのみロード)、高速ルックアップ プロパティを保持する方法にはどのようなものがありますか?
これは最初から良い考えですか？

パトリシア トライは、IPv4 割り当て/割り当てを格納し、ルックアップを実行するための、よく知られた推奨されるデータ構造です。

これは IPv6 アドレスにも当てはまりますか? 余分な96ビットに対応するために、より深く/より高くしようとしていますか？トライはまだパトリシアですか、それとも別の基数のトライですか?

こんにちは、私はCでトライを実装していました...しかし、insert_trie関数でエラーが発生します。

ルートノードが更新されない理由がわかりませんでした。これを手伝ってください。

insert_trie関数のnodepointer=nodepointer->listという行が原因でセグメンテーション違反が発生します...なぜ????

PS：これは宿題ではありませんが、私はそれを実装しようとしています。間違いを見つけることができませんでした。

最近、nedtriesについて聞いて、それらを実装してみることにしましたが、検索操作の複雑さについて何か気になります。なぜこんなに速いのか我慢できない。

私が理解したことから、彼らの検索操作の予想される複雑さは、ビット単位のキーのサイズがmのO（m / 2）であるはずです。これを従来の二分木の検索操作の複雑さと比較すると、次のようになります。log2（n）> = m / 2

キーを32ビット長にしましょう：log2（n）> = 16 <=> n> = 65536

したがって、nettriesは、65536アイテムから始まるバイナリツリーよりも高速である必要があります。ただし、著者は、それらは常に二分木よりも高速であると主張しているため、それらの複雑さに関する私の仮定が間違っているか、検索の各ステップで実行される計算がnedtrieで非常に高速です。

それで、それはどうですか？

私たちは電話帳 (連絡先) アプリケーションを作成しています。ネットでググったところ、TRIE である電話帳アプリケーションに使用できる便利なデータ構造が見つかりました。

Trie データ構造を使用して電話帳アプリケーションを実装できるように、リンクをガイドまたは提案してください。

私はJavaのデータ構造とアルゴリズムの初心者です。これを私を助けるための私の要求と考えてください。

TRIEデータ構造を使用して実装することが本当に可能かどうかについて、私は先に進むことができませんか?

私は現在、読み込み時に約 30000 語のテキスト ファイルを読み込み、ゲームプレイ中にすばやく検索できるようにそれらをプレフィックス ツリーに読み込む iOS 用の単語ゲームを作成しています。これはうまく機能しますが、読み込みとツリーの構築プロセスにより、アプリの起動時間がかなり長くなります。現時点では iPhone 4 でテストしていますが、3GS の以前のモデルではかなり遅くなると思います。

アプリを開くときではなく、コンパイル時にこのツリーを作成する方法はありますか? または、あまり理想的ではありませんが、実行時に実行する代わりに、別のプログラムでデータをプリベークし、そのファイルをプロジェクトに追加することは可能でしょうか? どうすればそれを行うことができますか？

文献には、トライを検索する時間は O(N) であり、N はパターンの長さであるという多くの情報があります。

ただし、ツリーの構築にも時間がかかります。私にとって、合計 Y 文字の単語が X 個あるとします。

したがって、O(Y) は時間です (各文字を挿入する必要があるため)。この評価は正しいですか（通常、私は正しくありません）

I. Just implemented a kind of bitwise trie (based on nedtries), but my code does lot Of memory allocation (for each node). Contrary to my implemetation, nedtries are claimed to be fast , among othet things, Because of their small number of memory allocation (if any). The author claim his implementation to be "in-place", but what does it really means in this context ? And how does nedtries achieve such a small number of dynamic memory allocation ?

Ps: I know that the sources are available, but the code is pretty hard to follow and I cannot figure how it works

試行はノードごとにデータ全体を保存するのではなく、親ノードのサフィックスのみを保存することをリモートで覚えています。

ツリーはデータ全体を保存しますが、プレフィックスに基づいてのみ整理します。

そのため、試行は小さくなり、たとえば辞書を非常にうまく圧縮できます。

違いは本当にそれだけですか？

実際のアプリケーションから、範囲クエリでは試行が高速であることを覚えています。範囲クエリを高速化するための特別な solr/lucene trie フィールドもあります。しかし、それはどうしてですか？

トライとツリーの実際の違いと長所と短所は何ですか?

非常に一般的なプレフィックス ツリーを作成することで、新しい Scala コレクション フレームワークを学びたかったのです。キーと値がパラメーターである必要があるだけでなく、各ノードで使用されるマップのタイプもパラメーターである必要があります。だから私はこれを試しました：

しかし、これはコンパイルされません:

これは私を混乱させます。ドキュメントから、MapLike には「This」を返す空の値があることがわかります。したがって、children は M[K,PrefixMap[M,K,V]] 型であるため、children.empty もその型である必要があります。

何がうまくいかないのですか、それを修正できますか?