5

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

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

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

4

4 回答 4

7

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

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

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

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

笔记

第一遍中使用的哈希表理论上可能会因输入的某些统计分布（例如，每个单词正好 16 次）或极其有限的 RAM 而溢出。由您来计算或尝试这是否真的会发生在您身上。

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

至于布隆过滤器本身的数量级内存需求；这些人的工作量低于 100 MB，并且应用程序更具挑战性（“完整”n-gram 统计，而不是阈值 1-gram 统计）。

于 2012-09-21T09:05:28.037 回答
3

使用 mergesort 按字母顺序对 TB 文件进行排序。在初始阶段，使用所有可用的物理 RAM 使用快速排序来对长时间运行的单词进行预排序。

这样做时，只用一个这样的单词和一个计数来表示一个连续的相同单词序列。（也就是说，您在合并期间添加计数。）

然后重新使用文件，再次使用带有快速排序预排序的合并排序，但这次是按计数而不是按字母顺序。

这比我的其他答案更慢但更容易实现。

于 2012-09-21T09:10:53.293 回答
2

我能想到的最好的：

  1. 将数据拆分为可以存储在内存中的部分。
  2. 对于每个部分获得N最频繁的单词，您将获得N * partsNumber单词。
  3. 再次阅读所有数据，计算你之前得到的单词。

它不会总是给你正确的答案，但它会在固定的内存和线性时间内工作。

于 2012-09-21T07:20:30.323 回答
0

为什么你认为建造 Trie 结构不是最好的决定？用计数器标记所有子节点，就是这样！最大内存复杂度是 O(26 *longest_word_length)，时间复杂度应该是 O(n)，还不错吧？

于 2020-01-26T10:07:47.743 回答