我遇到了一个问题，我们必须找到一TB文件或字符串中最频繁的10个单词。
我能想到的一个解决方案是使用哈希表(单词，计数)和最大堆。但是，如果单词是唯一的，那么匹配所有单词可能会产生问题。我想到了另一个使用MapReduce的解决方案，通过在不同的节点上分割块。另一个解决方案是为所有单词建立一个Trie，并在扫描文件或字符串时更新每个单词的计数。
以上哪一项是更好的解决方案？我认为第一个解决方案相当天真。
将可用内存分成两半。使用一个作为4位计数Bloom过滤器，另一半作为具有计数的固定大小哈希表。计数Bloom过滤器的作用是以高记忆效率过滤掉很少出现的单词。
对照最初空的Bloom过滤器检查您的1TB单词；如果一个单词已经在其中，并且所有的bucket都设置为最大值15(这可能是部分或全部的假阳性)，则将其通过。如果不是，请添加它。
通过的单词会被计算在内；对于大多数单词来说，这是除了前15次之外的每一次。一小部分人会更快地开始被统计，这可能会给你的结果带来每个单词最多15次的不准确。这是Bloom过滤器的限制。
当第一次通过后，如果需要，您可以通过第二次通过来纠正错误。取消分配Bloom过滤器，也取消分配不在第十个最频繁单词后面15次出现以内的所有计数。再次检查输入，这一次准确地计算单词(使用单独的哈希表)，但忽略第一次通过时未作为大致赢家保留的单词。
票据
理论上，在第一遍中使用的哈希表可能会溢出输入的某些统计分布(例如，每个单词正好16次)或极其有限的RAM。这取决于你是否能真实地发生在你身上。
还要注意，桶宽度(在上面的描述中为4比特)只是结构的参数。一个不计数的Bloom过滤器(桶宽度为1)可以很好地过滤掉大多数唯一的单词，但不会过滤掉其他很少出现的单词。更宽的桶大小将更容易在字之间发生串扰(因为桶将更少)，并且它还将降低第一次通过后的保证精度水平(在4比特的情况下出现15次)。但在某种程度上，这些缺点在数量上是微不足道的，而我认为更具攻击性的过滤效果对于用非重复的自然语言数据保持亚GB大小的哈希表来说是至关重要的。
至于Bloom滤波器本身的数量级存储器需求；这些人的工作空间远低于100MB，而且应用程序更具挑战性("完整"的n-gram统计数据，而不是阈值1-gram统计数据)。
使用mergesort按字母顺序对TB文件进行排序。在最初的过程中，使用所有可用的物理RAM对长时间运行的单词进行快速排序。
执行此操作时，仅用一个这样的单词和一个计数来表示相同单词的连续序列。(也就是说，您在合并期间添加计数。)
然后使用文件，再次使用mergesort和快速排序预排序，但这次是按计数而不是按字母顺序。
这比我的另一个答案更慢，但实现起来更简单。
我能想到的最好的：
- 将数据拆分为可以存储在内存中的部分
- 对于每个部分，获得
N最频繁的单词，您将获得N * partsNumber单词 - 重新阅读所有数据，计算你以前得到的单词
它不会总是给你正确的答案，但它会在固定的内存和线性时间内工作。
为什么你认为Trie结构的建筑不是最好的决定？用计数器标记所有子节点，就这样！最大内存复杂度将是O(26*longest_word_length)，时间复杂度应该是O(n)，这还不错，是吗？