algorithm - TB 数据中出现频率最高的单词

Question

我遇到了一个问题，我们必须在 1 TB 的文件或字符串中找到最常用的 10 个单词。

我能想到的一个解决方案是使用哈希表(单词、计数)和最大堆。但是，如果单词是唯一的，则拟合所有单词可能会导致问题。我想到了另一种使用 Map-Reduce 的解决方案，方法是将 block 拆分到不同的节点上。另一种解决方案是为所有单词构建一个 Trie，并在我们扫描文件或字符串时更新每个单词的计数。

以上哪一个是更好的解决方案？我认为第一个解决方案非常幼稚。

Answer 1

将可用内存分成两半。使用一个作为 4 位 counting Bloom filter另一半是带有计数的固定大小的哈希表。计数布隆过滤器的作用是过滤掉很少出现的词，内存效率高。

对照最初为空的布隆过滤器检查您的 1 TB 单词；如果一个词已经存在并且所有桶都设置为最大值 15(这可能部分或全部是误报)，则通过它。如果不是，请添加。

通过的单词被计算在内；对于大多数单词，这是您看到它们的每一次，但前 15 次。一小部分会更快地开始计算，从而给您的结果带来每个单词最多出现 15 次的潜在不准确性。这是布隆过滤器的局限性。

第一遍结束后，如果需要，您可以通过第二遍纠正不准确之处。取消分配布隆过滤器，也取消分配第 10 个最频繁出现的单词后 15 次出现之外的所有计数。再次检查输入，这次准确地计算单词数量(使用单独的哈希表)，但忽略第一次通过时未保留为近似获胜者的单词。

注意事项

在第一遍中使用的哈希表理论上可能会溢出输入的某些统计分布(例如，每个单词恰好 16 次)或极其有限的 RAM。您可以自行计算或尝试这是否会实际发生在您身上。

另请注意，桶宽(上述描述中为 4 位)只是构造的一个参数。一个不计数的布隆过滤器(桶宽度为 1)可以很好地过滤掉大多数独特的单词，但不会过滤掉其他很少出现的单词。更宽的桶大小将更容易出现单词之间的串扰(因为桶会更少)，并且还会降低第一次通过后保证的准确度水平(在 4 位的情况下出现 15 次)。但在某些时候，这些缺点在数量上是微不足道的，而我认为更积极的过滤效果对于将哈希表保持在亚千兆字节大小和非重复的自然语言数据是完全关键的。

至于布隆过滤器本身的数量级内存需求； these people正在以低于 100 MB 的方式工作，并且具有更具挑战性的应用程序(“完整”n-gram 统计信息，而不是阈值 1-gram 统计信息)。