最近、私は Patricia の試行を研究しており、STL ソート連想コンテナーとして使用できる非常に優れたC++ 実装を使用しています。パトリシアの試行は、通常のバイナリ ツリーとは異なります。これは、リーフ ノードが内部ノードを指すバック ポインターを持っているためです。それにもかかわらず、リーフ ノード バック ポインターを介して内部ノードのみにアクセスする場合は、順番にトラバーサルを行うことで、パトリシア トライをアルファベット順にトラバースすることができます。
パトリシア トライを使用して STLlower_boundと関数を実装することは可能ですか? upper_bound実際、私が使用している実装はこれらの関数を実装していますが、期待どおりに機能しません。
例えば：
typedef uxn::patl::trie_set<std::string> trie;
trie ts;
ts.insert("LR");
ts.insert("BLQ");
ts.insert("HCDA");
trie::iterator it = ts.lower_bound("GG");
std::cout << *it << std::endl;
HCDAを出力すると予想される場合、これはBLQを出力します。(std::setたとえば、 は確かにここで HCDA を出力します。)
このライブラリを作成した開発者に電子メールを送信しましたが、応答がありませんでした。いずれにせよ、私はパトリシアがどのように機能しようとしているのかをかなりよく理解していると感じています.lower_boundのようなものがどのように可能になるのかさえわかりません. 問題は、lower_bound が 2 つの文字列を辞書的に比較する機能に依存しているように見えることです。「GG」はツリーに存在しないため、どの要素が GG に対して >= であるかを調べる必要があります。しかし、Radix/Patricia は、ノードからノードへの移動に辞書式比較を使用しないように試みています。むしろ、各ノードは、検索キーでビット比較を実行するために使用されるビット インデックスを格納します。ビット比較の結果は、左に移動するか右に移動するかを示します。これにより、ツリー内の特定のプレフィックスを簡単に見つけることができます。しかし、プレフィックスがツリーに存在しない場合、
私が使用している C++ 実装が lower_bound を適切に実装していないように見えるという事実は、それが可能ではないかもしれないという私の疑いを裏付けています。それでも、ツリーをアルファベット順に反復できるという事実は、それを行う方法があるかもしれないと私に思わせます。
誰もこれを経験したことがありますか、またはパトリシアトライでlower_bound機能を実装できるかどうか知っていますか?