逆btreeを構築するには？

Question

私はこのウェブページhttps://nlp.stanford.edu/IR-book/html/htmledition/wildcard-queries-1.htmlに続いてワイルドカードクエリを学習していました。

しかし、辞書の逆Bツリーがどのように見えるか理解できません。このBTREEに基づいて逆Bツリーを構築する方法

**

：たとえば

私はこのようなBツリーを持っている場合は？

**

Answer 1

AリバースB-Treeがちょうど逆に、文字列の上に構築され、通常のBツリーデータ構造になります。

先頭のワイルドカードクエリを処理する方法の1つは、（すべての文字列を逆にして）逆ツリーを構築し、クエリも逆順にして、通常の末尾のワイルドカードクエリのように検索することです制限されたドメインを列挙しなければならないため、はるかに高速です。

（Lemonという文字列を考えてください）たとえば、'Le*'の場合、Lをたどり、次にeを選択してすべての可能性を列挙します。逆ツリー（LemonがnomeLになるところ）を保存している場合は、接頭辞問合せである'*mon'のような問合せを接尾辞問合せとなるより良い実行時間の複雑さで答えることができる'nom*'に変更できます。

実用的な観点から見ると、Solrのような検索エンジンは同様の手法を使用して、主要なワイルドカードクエリを提供します。スペースの複雑さ（スペース/時間のトレードオフ）を犠牲にして、パフォーマンスが向上します。詳細は、Solr ReversedWildcardFilterFactoryを参照してください。