algorithm - 如何构造反向btree？

Question

我正在关注这个网页https://nlp.stanford.edu/IR-book/html/htmledition/wildcard-queries-1.html来学习通配符查询。

但是，无法理解字典上的反向 B 树会是什么样子。

例如，如果我有这样的 Btree：

**

如何基于这个btree构造一个反向Btree？

**

Answer 1

Reverse B-Tree 就是在 Reversed 字符串上构建的常规 B-Tree 数据结构。

前缀查询很慢，处理前导通配符查询的方法之一是构建一个反向树（所有字符串都反转），也反转查询，然后像普通的尾随通配符查询一样搜索它，因为它们要快得多必须枚举受限域。

（考虑字符串 Lemon）例如'Le*'，您遍历 L，然后遍历 e，然后枚举所有可能性。如果您存储了一个反向树（其中 Lemon 变为 nomeL），则'*mon'可以将诸如前缀查询之类的查询更改（反转）为'nom*'后缀查询，并且可以以更好的运行时间复杂度来回答。

从更实际的角度来看，像 Solr 这样的搜索引擎使用类似的技术来提供领先的通配符查询。性能的提高是以更高的空间复杂度（空间/时间权衡）为代价的。有关更多信息，您可以查看 Solr ReversedWildcardFilterFactory。