倒排索引搜索算法

Question

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

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

我正在寻找一种算法来找到 100 个稀有词对。稀有词对是一对同时出现(不一定连续)的词恰好 1 个文档。

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

Answer 1

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

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