什么是算法来搜索索引的多个值？

这实际上是我正在处理的一个真正的问题，但为了简单起见，我们假装我是Google。什么是算法来搜索索引的多个值？

假设用户搜索“nanoscale tupperware”。没有很多页面，只有大约3k。但是，有200万页“纳米级”和400万“特百惠”。尽管如此，谷歌在0.3秒内为我找到了3k。

它是如何做到的？

我知道的唯一算法是获取“nanoscale”的文档，获取“tupperware”的文档，然后执行列表合并。但那是O（N + M），或者O（5,000,000），看起来有点慢。特别是如果我在桌面上运行它而不是超高速集群。

那么Google究竟在做什么，他们的速度主要是因为他们在他们的大规模分布式集群上运行这种昂贵的计算？

或者有没有更好的算法，我不知道？维基百科和谷歌没有为我提供任何东西。

编辑：

由于人们似乎把重点放在我的问题的谷歌方面，我想我会在实际的条款再说一遍。

我有几个非常大的（数百万项）索引实现为键/值对。键是简单的词，值是文档集。一个常见的用例是在不同索引上对多个搜索结果进行交集：难点在于获取文档集的交集。

我可以重新实现我的索引，但是我想要的 - 这主要是一个学术项目。

来源

2010-02-22 levand

可能有很多巧妙的缓存涉及...... – 2010-02-22 19:05:16

我确信有，以及一百万其他聪明的优化。但我真的怀疑他们正在缓存搜索结果*，所以我仍然好奇 - 他们使用什么算法来实际获取结果列表？ – levand 2010-02-22 19:10:05

谷歌有索引。很多指数。可能是抓住预先生成的单词'nanoscale'的索引，然后为列出的每个页面查看预先生成的该页面中所有单词的排序列表，以查看是否发生“tupperware”。这部分将大规模分发。它会缓存结果，以便下次搜索相同的术语时，它只会抓取预先生成的“纳米级特百惠”索引。可以想象，谷歌已经预先生成了按频率排列的前10,000个英语单词中的任何两个的每个可能组合的索引：它仅“是”1亿个页面列表。 – 2010-02-22 19:10:49

你描述它的方式，你已经有了一个inverted index，每个术语（文档列表）都有一个发布列表。我并不知道比合并每个术语的发布列表合并更好的解决方案，并且据我所知，这就是像Lucene一样的全文索引解决方案。有一对夫妇明显的优化，你可以在这里做，虽然：

如果你能在内存中存储数据集中，甚至是跨多台机器分布，可以非常快速地merge join结果集的确，相比于被什么了磁盘搜索需要。
'天真'合并连接算法在每次不匹配时将一个指针向前移动一个位置，但是如果您的发布列表本身已编入索引，则可以通过获取单个当前值的最大值并寻找在所有其他发布列表中的第一个值大于或等于该密钥 - 可能会忽略数百万个不相关的结果。这被称为zig-zag merge join。

来源

2010-02-24 15:10:44

你所描述的内容叫n-grams。

Google使用称为PageRank的算法来搜索和排序使用MapReduce实现的结果。

以上所有这些话题都在Stackoverflow上详细讨论过。查看它们应该相当容易。

这可能不会帮你一大堆，因为你可能没有一个庞大的分布式系统来运行MapReduce，但是因为你没有真正给我们提供关于你想要什么的任何细节index，很难提出适合你的问题的东西。

来源

2010-02-22 19:10:40

这只是一堆技术喋喋不休。这个问题与n-grams完全无关，并且与标记化的关联很奇怪。 – Fuser97381 2015-09-07 00:51:40

什么是算法来搜索索引的多个值？

回答

相关问题