問題タブ [patricia-trie]

現在、基数ツリー/パトリシア トライを実装しています (名前は何でも構いません)。非常に能力の低いハードウェアで辞書のプレフィックス検索に使用したいと考えています。多かれ少なかれオートコンプリートのように機能するはずです。つまり、入力されたプレフィックスが一致する単語のリストを表示します。

私の実装はこの記事に基づいていますが、そのコードにはプレフィックス検索が含まれていませんが、著者は次のように述べています。

[...] 共通のプレフィックス「AB」を持つキーを持つすべてのノードを列挙したいとします。そのルートから開始して、バック エッジに遭遇するたびに停止する深さ優先検索を実行できます。

しかし、それがどのように機能するのかわかりません。たとえば、次の単語から基数ツリーを構築するとします。

病気
想像上の
想像力
想像する
模倣
すぐ
に すぐ に
巨大

接頭辞「i」と「in」に対してまったく同じ「ベストマッチ」を取得するため、そのベストマッチからツリーをトラバースするだけで、一致するすべての単語を収集するのは難しいようです。

さらに、Java には基数ツリーの実装があり、 RadixTreeImpl.javaにプレフィックス検索が実装されています。そのコードは、すべてのノード (特定のノードから始まる) を明示的にチェックして、プレフィックスの一致を確認します。実際にはバイトを比較します。

基数ツリーでのプレフィックス検索の実装に関する詳細な説明を誰かに教えてもらえますか? Java 実装で使用されるアルゴリズムは、それを行う唯一の方法ですか?

私はパトリシアがIPプレフィックスルックアップを試みて実装しています。完全なキー一致のためにコードを機能させることができましたが、次のような他のキーのプレフィックスであるキーがある場合、プレフィックス検索で問題に直面しています。

上記の場合のプレフィックス検索のアルゴリズムを誰かが手伝ってくれますか？これらを別々の長さ（つまり、/ 24と16）のキーと見なす必要がありますか？

私は現在、DNA 配列データ検索システム用に Index Fabric を実装しようとしています。

インデックス ファブリック アルゴリズム

通常のパトリシア トライは実装できましたが、レイヤーの追加方法がわかりませんでした。私もグーグルを試しましたが、パトリシアトライにレイヤーを追加することに関する十分な情報を見つけることができませんでした。上記の論文では、彼らは私には魔法のように見える階層化されたトライをまっすぐに持ってきました（冗談です、最後の部分）。Index Fabric アーキテクチャを実装した経験のある方はいらっしゃいますか?

前もってありがとう
ヌワン

私は、メソッド、、を使用して、および迅速な検索（プレフィックス検索を含む）のために単語の大きな辞書を格納する手段として、addWord()PatriciaTrieを実装しようとしています。私は概念を読みましたが、それらは実装を明確にしていません。Trie、特にノードを実装する方法を（JavaまたはPythonコードで）知りたい（または再帰的に実装する必要がある）。26個の子ノードの配列をnull/Noneに設定して実装した人を見ました。より良い戦略（文字をビットとして扱うなど）はありますか？それをどのように実装しますか？isWord()isPrefix()

それらが何であり、どのように機能するかを理解できるように、トライの Python 実装を探し回っていると、ジャスティン・ピールのパトリシア・トライに出くわし、非常に有益であることがわかりました。そこから学ぶ。

しかし、私が理解していないと思うことがあります：

Justin のクラス patricia() を使用すると、次のようになります。

次のような辞書としてトライします。

addWord() と isWord() は期待どおりに機能しますが、 isPrefix() は次のような動作を示し、私を困惑させます:

予想通り、良い。その後

も良いですが、次に：

さらに：

ここで何か理解できませんか？

I am looking into writing an Android app that has a database of approximately 2000 longitudes and latitudes which are effectively hard coded.

I assume that once my app is installed, I can put this information into the SQLite database, but how should I distribute this information when the app is downloaded?

One option I thought of was some kind of Patricia Trie to minimise the size of the data (the points will be in a number of clusters, rather than evenly distributed), but I'm not sure whether such a collection would work when there are two associated numbers to store, along with perhaps some other information such as place name.

Does anyone have any thoughts, input or suggestions?

Rich

最近、私は 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機能を実装できるかどうか知っていますか?

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

私は、約 500,000 のドキュメントへの逆インデックスのセットとして約 10,000 語を使用しています。どちらも正規化されているため、インデックスは整数 (単語 ID) から一連の整数 (単語を含むドキュメントの ID) へのマッピングになります。

私のプロトタイプでは、当然のデータ型として Python のセットを使用しています。

ドキュメントを検索すると、N 個の検索語とそれに対応する N 個のセットのリストが見つかります。これらの N セットの交差点にあるドキュメントのセットを返したいと思います。

Python の「交差」メソッドは、ペアワイズ リダクションとして実装されています。ライブラリがiの後に次のエントリを取得する高速な方法を提供している限り、ソートされたセットの並列検索を使用すると、より適切に実行できると思います。

私はしばらくの間、そのようなものを探していました。何年も前に私はPyJudyを書きましたが、もはやそれを維持することはなく、再び快適に使えるようになるまでにどれだけの作業が必要になるかを知っています。私はむしろ他の誰かの十分にテストされたコードを使用したいと思います。また、高速なシリアライゼーション/デシリアライゼーションをサポートするコードが欲しいです。

Pythonバインディングでは何も見つからないか、少なくとも何も見つかりません。私が望むことを行うavltreeがありますが、ペアごとのセットのマージでさえ、必要以上に時間がかかるため、すべての操作を C/C++ で実行したいと考えています。

Python の C/C++ 拡張機能として書かれた基数/パトリシア/クリビット ツリー ライブラリを知っていますか?

それができない場合、ラップする必要がある最も適切なライブラリは何ですか? Judy Arrayサイトは 6 年間更新されておらず、1.0.5 が 2007 年 5 月にリリースされました。

（編集：APIから探しているものを明確にするために、次のようなものが必要です：

指定されたエントリの後に発生する次のエントリを返すために GET_NEXT() を実装するものを探しています。これは、Judy1Nおよび他の Judy 配列の同様のエントリに対応します。

このアルゴリズムは、データに動的に適応し、ヒットの少ないセットを優先的に優先する必要があります。私が扱うデータのタイプでは、これによりパフォーマンスが 5 ～ 10% 向上しました。) )

Patricia Trieを部分的に実装しましたが、Trieからノードを削除するために使用される削除/削除機能がないため、まだ完了していません。C++での実装に付属する構造について説明しているこの記事を見つけました。削除があります。 / delete関数ですが、実装の背後にある考え方がわかりません。

Trieからノードを削除し、Trieを適切な状態のままにするにはどうすればよいですか？