6

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

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

我正在寻找一种算法来找到 100 个稀有词对。稀有词对是在一个文档中同时出现（不一定连续）的一对词。

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

4

2 回答 2

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

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

于 2014-02-05T17:54:25.827 回答
0

这与“频繁项集挖掘”相反

即查看最近的出版物：稀有模式挖掘：挑战和未来前景

于 2020-12-13T08:22:42.463 回答