algorithm - 逆btreeを構築するには?

Question

ワイルドカード クエリを学習するために、この Web ページhttps://nlp.stanford.edu/IR-book/html/htmledition/wildcard-queries-1.htmlをフォローしていました。

しかし、辞書の逆 B ツリーがどのように見えるかを理解できません。

たとえば、次のような Btree があるとします。

**

このbtreeに基づいて逆Btreeを構築する方法は?

**

Answer 1

逆 B ツリーは、逆文字列で構築された通常の B ツリー データ構造です。

先頭のワイルドカード クエリを処理する方法の 1 つは、(すべての文字列を逆にして) 逆ツリーを構築し、クエリも逆にして、通常の末尾のワイルドカード クエリのように検索することです。制限付きドメインを列挙する必要があります。

(文字列レモンを考えてみましょう) たとえば'Le*'、L をトラバースし、次に e をトラバースしてから、すべての可能性を列挙します。逆ツリー (Lemon が nomeL になる場所) を保存した場合'*mon'、プレフィックス クエリであるようなクエリを変更 (逆) し'nom*'てサフィックス クエリにすることができ、実行時間の複雑さを向上させることができます。

より実用的な観点から見ると、Solr のような検索エンジンは同様の手法を使用して主要なワイルドカード クエリを処理します。スペースの複雑さが増すという犠牲を払ってパフォーマンスが向上します (スペースと時間のトレードオフ)。詳細については、Solr ReversedWildcardFilterFactory を確認してください。