搜索引擎如何进行“AND”运算？手术？

发布于 2024-08-22 21:34:51 字数 1253 浏览 8 评论 0原文

请考虑以下搜索结果：

Google for 'David' - 0.28 秒内5.91 亿次点击
Google for 'John' - 0.18 秒内7.85 亿次点击

好的。页面被索引，只需要查找索引表中的计数和前几项，所以速度是可以理解的。

现在考虑以下使用 AND 运算的搜索：

Google 搜索“David John”（“David”AND“John”） - 0.25 秒内点击量达到 1.73 亿次 strong>

这让我很兴奋;) 搜索引擎到底是如何能够这么快地得到海量数据集的 AND 运算结果的呢？我看到以下两种执行任务的方法，两种方法都很糟糕：

你进行“大卫”的搜索。获取巨大的临时表并在其上搜索“John”。但是，临时表未按“John”索引，因此需要进行强力搜索。无论您拥有什么硬件，都不会在 0.25 秒内完成计算。
按所有可能的单词建立索引像“大卫·约翰”这样的组合。然后我们面临着按键数量的组合爆炸连谷歌都没有存储空间有能力处理这个问题。

您可以 AND 一起任意数量的搜索短语，您仍然可以在 0.5 秒内获得答案！如何？

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

海螺姑娘 2024-08-29 21:34:52

马库斯写的关于谷歌在许多机器上并行处理查询的内容是正确的。

此外，还有信息检索算法可以使这项工作变得更容易一些。经典的方法是构建一个由帖子列表组成的倒排索引 - 按顺序包含该术语的所有文档中每个术语的列表。

当搜索包含两个术语的查询时，从概念上讲，您将获取两个术语（“david”和“john”）中每个术语的发布列表，并沿着它们行走，查找两个列表中的文档。如果两个列表的排序方式相同，则可以在 O(N) 内完成。当然，N 仍然很大，这就是为什么这将在数百台机器上并行完成。

此外，可能还有其他技巧。例如，如果排名最高的文档在列表中的位置较高，那么算法可能会决定无需遍历整个列表即可找到 10 个最佳结果。然后它会猜测结果的剩余数量（基于两个列表的大小）。

回复收藏 0 原文

黒涩兲箜 2024-08-29 21:34:52

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

Google 在单台机器上没有表/索引。相反，他们在服务器上大量划分数据集。报告表明涉及多达 1000 台物理机在每个查询中！

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

阅读有关 Google 技术和基础设施的内容非常鼓舞人心且具有很高的教育意义。我建议阅读 BigTable、MapReduce 和 Google 文件系统。

Google 有一个其出版物档案，其中包含大量有关其技术的有趣信息。 metafilter 上的这个帖子还提供了对大量硬件的一些见解需要运行搜索引擎。

回复收藏 0 原文

缘字诀 2024-08-29 21:34:52

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

它以倒排索引开始，如 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”分数相加来确定整体相关性；它不考虑顺序/接近度/等等。的名称考虑在内。再次，我确信谷歌确实将其纳入他们的分数中，但我的客户不需要它。

I don't know how google does it, but I can tell you how I did it when a client needed something similar:

It starts with an inverted index, as described by Avi. That's just a table listing, for every word in every document, the document id, the word, and a score for the word's relevance in that document. (Another approach is to index each appearance of the word individually along with its position, but that wasn't required in this case.)

From there, it's even simpler than Avi's description - there's no need to do a separate search for each term. Standard database summary operations can easily do that in a single pass:

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

This will return the IDs of all documents which have scores for both 'David' and 'John' (i.e., both words appear), ordered by some approximation of relevance and will take about the same time to execute regardless of how many or how few terms you're looking for, since IN performance is not affected much by the size of the target set and it's using a simple count to determine whether all terms were matched or not.

Note that this simplistic method just adds the 'David' score and the 'John' score together to determine overall relevance; it doesn't take the order/proximity/etc. of the names into account. Once again, I'm sure that google does factor that into their scores, but my client didn't need it.

回复收藏 0 原文