lev*_*and 5 language-agnostic algorithm indexing search
这实际上是我正在研究的一个真正的问题,但为了简单起见,让我们假装我是谷歌.
假设用户搜索"纳米级特百惠".这两个词的页面都不多,只有3k左右.但是有大约200万页的"纳米级"和大约400万页的"特百惠".不过,Google在0.3秒内为我找到了3k.
它是如何做到的？
我所知道的唯一算法是获取"纳米级"的文档,获取"tupperware"的文档,然后进行列表合并.但那是O(N + M),或O(5,000,000)似乎有点慢.特别是如果我在桌面而不是超快集群上运行它.
谷歌正在做什么呢？他们的速度主要是因为他们在庞大的分布式集群上运行这种昂贵的计算？
还是有一个我不知道的更好的算法？维基百科和谷歌没有为我提供任何东西.
编辑:
由于人们似乎专注于我的问题的谷歌方面,我想我会在实际条款中重申它.
我有几个非常大(数百万项)的索引作为键/值对实现.键是简单的单词,值是文档集.一个常见的用例是在不同索引上的几次搜索中获得结果的交集:痛点是获取文档集的交集.
我可以重新实现我想要的索引 - 此时它主要是一个学术项目.
按照您描述的方式，您已经有了一个倒排索引，其中每个术语都有一个发布列表（文档列表）。我不知道有什么比合并加入每个术语的发布列表更好的解决方案了，据我所知，这就是像 Lucene 这样的全文索引解决方案所做的。不过，您可以在这里进行一些明显的优化：