倒排索引搜索算法

Question

考虑一下人们在谷歌中搜索了100亿个单词.对应于每个单词,您都有所有文档ID的排序列表.该列表如下所示:

[Word 1]->[doc_i1,doc_j1,.....]
[Word 2]->[doc_i2,doc_j2,.....]
...
...
...
[Word N]->[doc_in,doc_jn,.....]

我正在寻找一种算法来找到100个罕见的单词对.罕见的单词对是在一个文档中一起出现的一对单词(不一定是连续的).

如果可能的话,我正在寻找比O(n ^ 2)更好的东西.

Answer 1

1. 您可以根据单词出现的文档数量对单词进行排序。这里的想法是，很少出现的单词也很少成对出现。如果您发现某个单词恰好出现在一个文档中，只需从该文档中选择任何其他单词即可完成。
2. 然后开始反转索引，从最稀有的单词开始。这意味着您创建一个映射，其中每个文档都指向其中的单词集。首先，您仅使用最稀有的单词创建倒排索引。将与该最稀有单词相关的所有文档插入倒排索引后，您将获得一个映射，其中每个文档都指向一个单词。
3. 然后添加下一个单词及其所有文档，仍然遵循 (1.) 中创建的顺序。在某些时候，您会发现与某个单词关联的文档已经存在于您的倒排地图中。在这里，您可以检查与该文档关联的所有单词是否形成这样的罕见单词对。

该东西的性能在很大程度上取决于你需要走多远才能找到 100 个这样的对，我们的想法是，你只处理了总数据集的一小部分就完成了。为了利用仅处理一小部分数据的事实，您应该在 (1.) 中使用一种排序算法，该算法允许您在整个集合排序之前找到最小的元素，例如快速排序。然后排序可以像 O(N*log(N1) ) 一样完成，其中 N1 是在找到 100 对之前实际需要添加到倒排索引的单词数。其他操作（即向倒排索引添加一个单词以及检查单词对是否出现在多个文档中）的复杂性也与每个单词的文档数量呈线性关系，因此这些操作应该一开始就快，然后慢下来稍后，因为稍后每个单词都会有更多文档。