logo标签列表

搜索引擎如何进行“AND”操作？

searchindexinginformation-retrievalboolean-logic
4
考虑以下搜索结果： 好的。页面已被索引，只需要查找计数和索引表中的前几个项目，因此速度是可以理解的。
现在考虑以下AND操作的搜索： 这让我感到很生气 ;)搜索引擎如何如此快速地获取庞大数据集上的AND操作结果？ 我看到以下两种方法来完成任务，但都很糟糕：
  1. 您进行“David”的搜索。取巨大的临时表并对其进行“John”的搜索。 但是，临时表没有按“John”进行索引，因此需要暴力搜索。无论您拥有什么硬件，都无法在0.25秒内计算出来。
  2. 通过所有可能的单词组合进行索引，例如“David John”。然后我们将面对关键字数量的组合爆炸，并且即使Google也无法处理该问题。

您可以AND在一起尽可能多的搜索短语，而您仍然可以在0.5秒内获得答案！怎么做到的？

4个回答
2
马库斯所写的关于谷歌并行处理查询的内容是正确的。
此外，有信息检索算法可以使这项工作变得更容易。经典的方法是构建一个倒排索引，它由倒排列表组成 - 每个术语的所有包含该术语的文档的列表，按顺序排列。
当搜索具有两个术语的查询时，概念上，您将获取每个术语（“david”和“john”）的倒排列表，并沿着它们走，寻找在两个列表中都存在的文档。如果两个列表以相同方式排序，则可以在O（N）时间内完成此操作。当然，N仍然很大，因此将在数百台机器上并行执行此操作。
此外，可能还有其他技巧。例如，如果最高排名的文档排在列表的前面，那么也许算法可以决定找到了10个最佳结果，而不必遍历整个列表。然后，它会根据两个列表的大小“猜测”剩余结果的数量。
1

我不知道谷歌是如何做到的，但当客户需要类似的东西时，我可以告诉你我是如何做到的：

它始于一个倒排索引，就像 Avi 描述的那样。这只是一个表格清单，列出了每个文档中每个单词的文档 ID、单词以及单词在该文档中相关性的分数。（另一种方法是将每个单词的每次出现及其位置单独索引，但在这种情况下并不需要。）

从那里开始，它甚至比 Avi 的描述更简单 - 没有必要为每个术语进行单独搜索。标准数据库摘要操作可以轻松地在单次通过中完成：

SELECT document_id, sum(score) total_score, count(score) matches FROM rev_index
WHERE word IN ('david', 'john') GROUP BY document_id HAVING matches = 2
ORDER BY total_score DESC

这将返回所有具有'David'和'John'得分的文档的ID（即，两个词都出现），按相关性的某种近似顺序排序，并且无论您要查找多少个或少数个术语，执行时间大致相同，因为IN性能不会受目标集大小的影响，并且它使用简单的count来确定是否匹配了所有术语。

请注意，这种简单的方法只是将'David'得分和'John'得分相加以确定整体相关性；它不考虑名称的顺序/接近度等。再次强调，我确信谷歌会将其纳入他们的评分中，但我的客户并不需要。

1

我认为你从错误的角度来解决这个问题。

谷歌没有单一机器上的表格/索引。相反，他们将数据集在服务器上进行大量分区。报告显示每个查询涉及多达1000台物理机器！

有了如此强大的计算能力，“只是”（非常讽刺地使用）确保每台机器在几分之一秒内完成工作的问题。

阅读关于谷歌技术和基础设施的文章非常鼓舞人心，也非常有教育意义。我建议阅读BigTable、MapReduce和Google文件系统。

Google有一个他们的出版物档案，其中包含大量关于他们技术的有趣信息。Metafilter上的这个帖子也提供了一些洞察搜索引擎所需的巨大硬件数量。

0

我多年前在一台16位机器上做过类似的事情。数据集的上限约为110,000条记录（因为它是一个墓地，所以葬礼有限），因此我设置了一系列包含128K位的位图。

搜索“david”导致我在其中一个位图中设置相关位，表示该记录中有单词“david”。在第二个位图中对“john”执行相同操作。

然后，您只需要对两个位图进行二进制“and”运算，得到的位图告诉您哪些记录号同时具有“david”和“john”。快速扫描结果位图可将匹配两个术语的记录列表返回。

这种技术对于谷歌来说行不通，因此请将其视为我的价值0.02美元。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接