算法 – 在全文搜索中使用多字查询的索引(例如网页搜索)

我了解全文搜索的一个基本方面是使用 inverted indexes.所以，使用倒排索引，单字查询变得微不足道。假设索引的结构如下：

一些字 – > [doc385，doc211，doc39977，…](按排名，降序排序)

为了回答该单词的查询，解决方案只是在索引中找到正确的条目(其采用O(log n)时间)，并从索引中指定的列表中提供一些给定数量的文档(例如前10个)。

但是，返回与两个字匹配的文档的查询呢？最直接的实现将是：

>将A设置为具有单词1(通过搜索索引)的文档集合。
>将B设置为具有单词2(同上)的文档集。
>计算A和B的交点

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

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

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

线性不快你可以用两个以上的方式来搜索，所以只是使用并行性肯定不是整个解决方案。那么这些案例如何优化呢？大型全文搜索引擎是否使用某种复合索引？布莱姆过滤器？有任何想法吗？

正如你所说的一样 – > [doc385，doc211，doc39977，…](按排名，降序排序)，我认为搜索引擎可能不这样做，文档列表应该按照doc ID排序，每个文档都按照这个词排列。 当查询到来时，它包含几个关键字。对于每个单词，您可以找到文档列表。对于所有关键字，您可以执行合并操作，并计算文档到查询的相关性。最后返回顶部排名的相关性文档给用户。 并且可以分发查询过程以获得更好的性能。