27

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

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

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

但是返回匹配两个单词的文档的查询呢？最直接的实现如下：

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

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

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

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

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

4

4 回答 4

7

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

于 2011-05-17T15:44:16.067 回答
5

即使没有排名，我想知道谷歌如何快速计算两组的交集。

显然，计算某些单词 A、B、C 的交集的最坏情况是它们的索引非常大而交集非常小。一个典型的案例是在不同语言中搜索一些非常常见的（DB 术语中的“流行”）单词。

让我们试试中文的“conte”和“位置”、“location”和日文的“位置”な（“extreme”）。

谷歌搜索位置返回大约1,000000000 个结果（028 秒）“谷歌搜索“concre ”返回“大约 2,020,000,00 个结果（0.46 秒）” 谷歌搜索“な”大约 7,590,000 个结果（0.25 秒）

极有可能所有三个术语都出现在同一个文档中，但让我们：Google 搜索它们的具体位置 ro 将返回“大约 174，00 个结果（0.13 秒）”

添加俄语单词“игра”（游戏） 搜索игра：大约 212,000,000 个结果（0.37 秒）

搜索所有这些：“игра 具体位置”返回约 12,600 个结果（0.33 秒）

当然返回的搜索结果是胡说八道，它们不包含所有搜索词。

但是查看组合查询的查询时间，我想知道是否在单词索引上计算了一些交集。即使一切都在 RAM 中并且被大量分片，计算具有 1,500,000,000 和 2,020,000,000 个条目的两个集合的交集也是 O(n) 并且几乎不能在 <0.5 秒内完成，因为数据位于不同的机器上并且它们必须进行通信。

必须有一些连接计算，但至少对于流行词来说，这肯定不是在整个词索引上完成的。加上结果模糊的事实，谷歌似乎使用了某种优化“返回一些排名靠前的结果，并在 0.5 秒后停止”。

这是如何实现的，我不知道。有任何想法吗？

于 2013-10-28T12:12:12.440 回答
4

大多数系统以某种方式实现TF-IDF。TF-IDF 是函数词频和逆文档频率的乘积。

IDF 函数将文档频率与集合中的文档总数联系起来。这个函数的普遍直觉是，它应该为出现在少数文档中的术语赋予更高的值，而为出现在所有文档中的术语赋予较低的值，使其无关紧要。

您提到了谷歌，但谷歌使用 PageRank（链接输入/输出）以及词频和接近度来优化搜索。Google 分发数据并使用 Map/Reduce 来并行化操作——计算 PageRank+TF-IDF。

在信息检索：实现搜索引擎第 2 章中对此背后的理论进行了很好的解释。进一步研究的另一个想法是查看Solr如何实现这一点。

于 2011-05-17T15:00:51.780 回答
3

Google 不需要实际查找所有结果，只需要查找最上面的结果。索引可以先按等级排序，然后才能按id排序。由于相同的 ID 始终具有相同的等级，因此不会影响设置交叉时间。

所以谷歌开始交集，直到它找到 10 个结果，然后做一个统计估计告诉你它找到了多少结果。

最坏的情况几乎是不可能的。如果所有单词都是“共同的”，那么交集将很快给出前 10 个结果。如果有一个稀有词，那么交集很快，因为复杂度是 O(N long M)，其中 N 是最小的组。

您需要记住，google 将其索引保存在内存中并使用并行计算。例如，U 可以将问题分成两个搜索，每个搜索只搜索一半的网络，然后对结果进行分析并取最佳值。谷歌拥有数百万台计算机

于 2016-09-25T09:48:04.910 回答