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

考虑下面的搜索结果：搜索引擎如何进行“AND”操作？

Google for 'David' - 591百万安打0.28秒
Google for 'John' - 785百万安打0.18秒

确定。页面被编入索引，它只需要查找索引表中的计数和前几个项目，因此速度是可以理解的。

现在考虑下面的搜索与操作：

Google for 'David John'（ '大卫' 和 '约翰'） - 173个百万命中在0.25秒

这让我打勾;）搜索引擎如何能够如此快地获得巨大数据集上的AND运算结果？我看到以下两种方式来执行任务，两者都很糟糕：

您进行'大卫'的搜索。拿着巨大的临时表，并在其上搜索“约翰”。但是，临时表不是由'John'索引的，因此需要进行强力搜索。不管你有什么样的硬件，它在0.25秒内都不会计算。
通过所有可能的词索引像'大卫约翰'组合。然后我们面临一个关键数量的组合式爆炸，并且甚至没有Google的存储容量来处理。

你可以和在一起as many search phrases as you want，你仍然可以在0.5秒内得到答案！怎么样？

来源

2010-02-26 user256890

Markus写的关于Google在多台机器上并行处理查询的问题是正确的。

此外，还有information retrieval算法，使这项工作更容易一些。经典的做法是构建一个inverted index，其中包含过帐列表 - 按顺序包含该术语的所有文档的每个术语的列表。

当查询包含两个词语时，在概念上，您将为这两个词语（'david'和'john'）中的每一个词汇发布列表，并沿着它们前进，查找包含这两个词条的文档。如果两个列表都以相同的方式排序，则可以在O（N）中完成。当然，N仍然很大，这就是为什么这将在数百台机器上并行完成。

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

来源

2010-02-26 10:34:53 Avi

我在一台16位机器上做了类似于今年的工作。该数据集的上限约为110,000条记录（这是一个墓地，因此有限的墓地限制），所以我设置了一系列包含128K位的位图。

搜索“david”导致我在其中一个位图上设置相关位以表示记录中包含单词“david”。在第二个位图中，'john'也一样。

然后你需要做的就是一个二进制的'和'两个位图，并且结果位图告诉你哪些记录号码中包含'david'和'john'。对结果位图进行快速扫描可以让您找回符合两个术语的记录列表。

这种技术不适用于谷歌，所以考虑这个价值0.02美元。

来源

2010-02-26 09:51:12 Andrew

我认为你是从错误的角度接近问题。

Google在单台机器上没有表格/索引。相反，他们将数据集大量分布在服务器上。报告显示that as many as 1000 physical machines are involved in every single query！利用这种数量的计算能力，它“简单地”（高度讽刺地使用）确保每台机器在一秒钟内完成其工作。

关于Google技术和基础架构的阅读非常鼓舞人心且教育程度非常高。我建议您阅读BigTable,MapReduce和Google File System。

谷歌有一个archive of their publications有很多关于其技术的多汁信息。 This thread on metafilter也提供了一些洞察到运行搜索引擎所需的大量硬件。

来源

2010-02-26 10:10:26

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

它开始倒排索引，如阿维描述。这只是一个表格列表，对于每个文档中的每个单词，文档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

这将返回具有分数都“大卫”和“约翰”（即，这两个词的出现）的所有文件的ID，通过有序一些相关性的近似值，无论需要查找多少条或多少条目，都需要大致相同的时间才能执行，因为IN的性能不受目标集大小的很大影响，并且它使用简单的count来确定是否所有条款都匹配或不匹配。请注意，这种过于简单的方法只是将'David'分数和'John'分数相加，以确定总体相关性;它不需要命令/接近/等等。的名字考虑在内。再一次，我确信谷歌确实将这些因素纳入他们的分数中，但我的客户并不需要它。

来源

2010-02-26 11:34:32

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

回答

相关问题