適応型基数木での文字列の検索

Question

「Adaptive Radix Tree： ARTful主記憶データベースの索引付け」のリサーチ・ペーパーを見てきましたが、どのように文字列を一致させることができるかに関する質問がありました。ノードのキー例えば：もし私が単語を持っていたなら、私のテーブルのタプルの1つの主キー（識別子）だったIota。そして、アルファからゼータなどのAから始まる値から検索しなければなりませんでした。簡単にするため、Alpha、Beta、Delta、Gamma、Kappa、Iota、Phi、Psi、Rho、Zetaの10個の値のみを考慮してください。あなたはどうやってそれをやりますか？

研究論文への参照：それは紙のように見える私にhttps://db.in.tum.de/~leis/papers/ART.pdf

Answer 1

はわずか4、16または256のエントリを含む、より小さな例int型のバイナリ検索を必要とする（別の内部ノードタイプと通常のTrie構造を記述します）。著者はまた、何らかの形で単一の子ノードのチェーンをコンパクトにしているように見えます。

PhiとPsiを除いてルートノード（記事ではタイプ16のもの）にすべての別個のエントリがあるので、あなたのサンプルキーで構造をよく記述することはできません。 "P"エントリは "h"と "s"のエントリを持つ4ノードにつながります。残りのすべてのエントリは、最適化された単一ノードチェーンになります。

今日のヒープメモリサイズに比べて実際には多くの異なる単語が存在しないことに注意してください。本当に本当のケースがあるまで「エキゾチック」なデータ構造を検討しています。これからの利益。