algorithm - 在全文搜索中使用索引进行多词查询(例如网络搜索)

Question

我知道全文搜索的一个基本方面是使用 inverted indexes .因此，使用倒排索引，单词查询变得很容易回答。假设索引的结构如下:

some-word -> [doc385, doc211, doc39977, ...](按排名降序排列)

要回答对该词的查询，解决方案只是在索引中找到正确的条目(这需要 O(log n) 时间)并从中指定的列表中呈现一些给定数量的文档(例如前 10 个)索引。

但是如果查询返回匹配的文档，比如说，两个词呢？最直接的实现如下:

1. 将 A 设置为具有单词 1 的文档集(通过搜索索引)。
2. 将 B 设置为具有单词 2 (ditto) 的文档集。
3. 计算 A 和 B 的交集。

现在，第三步可能需要 O(n log n) 的时间来执行。对于可能使查询回答缓慢的非常大的 A 和 B。但是像谷歌这样的搜索引擎总是在几毫秒内返回他们的答案。所以这不是完整的答案。

一个明显的优化是，由于像 Google 这样的搜索引擎无论如何都不会返回所有匹配的文档，因此我们不必计算整个交集。我们可以从最小的集合(例如 B)开始，找到足够多的条目也属于另一个集合(例如 A)。

但是我们不能还有下面最坏的情况吗？如果我们将 A 设置为匹配一个常用词的文档集，将 B 设置为匹配另一个常用词的文档集，仍然可能存在 A ∩ B 非常小的情况(即组合很少见)。这意味着搜索引擎必须线性地遍历 B 的所有元素 x 成员，检查它们是否也是 A 的元素，以找到满足两个条件的少数元素。

线性并不快。而且您可以搜索两个以上的词，因此仅采用并行性肯定不是完整的解决方案。那么，这些案例是如何优化的呢？大型全文搜索引擎是否使用某种复合索引？布隆过滤器？有什么想法吗？

Answer 1

正如你所说的some-word -> [doc385, doc211, doc39977, ...](按排名降序排列)，我认为搜索引擎可能不会这样做，文档列表应该按文档ID排序，每个文档都有一个根据单词的排名。
当查询到来时，它包含几个关键字。对于每个单词，您都可以找到一个文档列表。对于所有的关键字，您都可以进行合并操作，并计算文档与查询的相关性。最后将排名靠前的相关文档返回给用户。
查询过程可以分布式以获得更好的性能。