問題タブ [radix-tree]

3つの操作をサポートする非常に単純なTrieをJavaで実装しようとしています。insertメソッド、hasメソッド（つまり、トライ内の特定の単語）、および文字列形式でトライを返すtoStringメソッドが必要です。挿入は適切に機能していると思いますが、hasとtoStringは難しいことがわかっています。これが私がこれまでに持っているものです。

トライクラス。

そしてノードクラス

したがって、基本的に、Trieを作成する場合、TrieNodeは26の子を持つルートとして作成されます。挿入が試行されると、そのルートノードで挿入が呼び出され、正しい位置に新しいノードが再帰的に作成され、単語が完了するまで続行されます。メソッドは正しく機能していると思います。

何らかの理由で括弧の外にreturnステートメントが必要なため、私のhas関数は非常に壊れています。else句に含めることができないか、コンパイラが文句を言います。それ以外は、少し調整すればうまくいくと思いますが、一生理解できません。

toStringは私が取り組もうとした獣ですが、何も投げないので、問題が解決するまでそのままにしておきます。動作するようになれば、それをtoString関数に再フォーマットする方法を見つけることができるかもしれません。

int val = word.charAt（0）-64;の目的 入力する各文字列はすべて大文字でなければならないため（後でこれを確実にするために文字列フォーマット関数を作成します）、最初の文字のint値-64が配列内の位置になります。つまり、配列インデックス0はAであるため、A = 64、A-64 =0です。B=65、B-64=1などです。

バイナリ文字の文字列であるキーに使用できる基数ツリーの実装を探しています。実際には UUID なので、null バイトをサポートする必要があります。

商用製品で使用されるため、適切なライセンスを持つものです。

以下に使用するデータ構造を決定しようとしています。

いくつかのデータを含む一意のオブジェクトへのポインターを含むキーが 1,000 万個あるとします。

キーは UUID の 16 バイトのバイナリ配列と見なされます。UUID は、高品質の乱数ジェネレーターを使用して生成されます。

以下を検討していますが、それぞれの速度とメモリ消費の長所と短所を知りたいです。いくつかの公正な見積もり、64 ビット プラットフォームでの最良/最悪/平均のケースが適切です。

事実上無制限のアイテムを挿入できるようにする必要があります。

バイナリ ツリー ハッシュ テーブル 基数ツリー (ビット ベースまたは 2 ビット マルチウェイ)

これらに必要な操作は、挿入、削除、検索です

基数ツリーのアイデアは気に入っていますが、実装が最も難しいことが判明しており、商用製品に組み込むことができる適切な実装が見つかりませんでした。

IPアドレス（すべてIPv4）をすばやく検索して保存する必要があるC ++でプログラムを書いています。すべての IP アドレスには、関連付けられたデータがあります。トライに既に存在する場合は、トライの IP アドレスのデータを新しいアドレス データとマージするつもりです。存在しない場合は、新しいエントリとしてトライに追加するつもりです。IPアドレスの削除は不要です。

これを実装するには、パトリシア トライを設計する必要があります。しかし、これ以上のデザインを視覚化することはできません。私には非常に素朴に思えますが、頭に浮かんだ唯一のアイデアは、IP アドレスをバイナリ形式に変更してからトライを使用することでした。ただし、これを正確に実装する方法についてはわかりません。

この件でお役に立てましたら、本当にありがとうございます。ここで同様の質問を見つけたことに注意してください。CPAN Web サイトのコードが私にとって十分に明確ではなかったため、質問またはより具体的には回答は私の理解を超えていました。

また、私のデータは次の形式です

10.10.100.1: 「トム」、「ジャック」、「スミス」

192.168.12.12: "ジョーンズ","リズ"

12.124.2.1: "ジミー","ジョージ"

10.10.100.1: 「マイク」、「ハリー」、「ジェニファー」

トライと基数トライのデータ構造は同じですか？

それらが同じでない場合、基数トライ（別名パトリシアトライ）の意味は何ですか？

IPv4 アドレスがパトリシア/基数ツリーに挿入される方法を理解するのに役立つドキュメントはありますか? マスク長の計算と、マスク長が完全なアドレスまたはアドレス内の 1 オクテットの場合について混乱しています。

説明をいただければ幸いです。

私は常に基数ツリーのスペース使用法に関心を持っていましたが、これに関する有益な議論は見つかりませんでした。

ここで、linux radix-tree.c と同じ基数ツリーの実装があるとしましょう。これは整数を取り、6 ビットごとに使用してツリー内の次の位置にインデックスを付けます。基数ツリーのスペース使用量が二分探索ツリーよりもはるかに多い場合は簡単に思いつきます。私が間違っている場合は修正してください：

ユースケース: (0,1,1,1,1)、(1,1,1,1,1)、(2,1,1,1,1)、... (63,1,1,1) 、1)。

ここでは便宜上、(a,b,c,d,e) を使用して 30 ビット整数キーを表し、各要素は 6 ビット値を表します。a は MSB、e は LSB です。

基数ツリー:

この使用例では、基数ツリーの高さは 5 で、各キーはルートの異なるサブツリーにあるため、4 つの個別のノードを使用します。したがって、((5-1) * 64 + 1) = 257 ノードになります。

各ノードには 2^6 = 64 個のポインターが含まれているため、257 * 64 * 4Byte = 65KB を使用します。

二分探索木

キーの数だけが重要です。この場合、64 個のキーがあります。

各 BST ノードがノードごとに 3 つのポインターを使用すると仮定すると、64 * 3 * 4 バイト = 768 バイトを使用することになります。

比較

基数ツリーは非常にスペース効率が悪いようです。同じ数のノードが与えられた場合、二分探索木よりも ~100 倍の空間を使用します! なぜLinuxカーネルでも使われるのか理解できません。

何か不足していますか？ありがとう。

http://en.wikipedia.org/wiki/Compact_prefix_treeや http://en.wikipedia.org/wiki/Trieなどのトライと基数ツリーを調べる と、ノードの子。

したがって、たとえば、このトライ (ページの右上にある唯一の図) では、ルートの子は、左から右に「A」、「i」、「t」の順序で並べることができます。

試行/基数ツリーは検索用であり、頻繁な更新用ではありません。そのため、この種の順序付けは、特にまれなツリーの更新ではあまりコストがかからず、アルゴリズム的に簡単/簡単で、値の検索/取得中の速度にいくらか追加されます。

私は何が欠けていますか？

これに関する/反対の議論を探しています。