我遇到了一个问题,我们必须找到一个TB级文件或字符串中最常用的10个单词.
我能想到的一个解决方案是使用哈希表(word,count)和最大堆.但如果单词是唯一的,那么拟合所有单词可能会导致问题.我想到了通过在不同节点上拆分块来使用Map-Reduce的另一种解决方案.另一种解决方案是为所有单词构建Trie,并在扫描文件或字符串时更新每个单词的计数.
以上哪一项是更好的解决方案？我认为第一个解决方案很天真.
将可用内存分成两半.使用一个作为4位计数布隆过滤器,另一半作为具有计数的固定大小哈希表.计数Bloom过滤器的作用是过滤掉具有高内存效率的很少出现的单词.
检查最初为空的Bloom过滤器的1 TB字样; 如果一个单词已经存在并且所有存储桶都设置为最大值15(这可能部分或完全是误报),则将其传递通过.如果不是,请添加它.
通过的词被计算; 对于大多数单词而言,这是每次,但前15次你看到它们.一小部分人将开始更快地计算,每个单词最多可能出现15次不准确的结果.这是Bloom过滤器的限制.
当第一次通过结束时,如果需要,您可以通过第二次通过来纠正不准确性.取消分配Bloom过滤器,还释放所有不在第十个最常用单词后面15次内的计数.再次浏览输入,这次准确计算单词(使用单独的哈希表),但忽略未从第一遍中保留为近似获胜者的单词.
笔记
在第一遍中使用的哈希表理论上可以溢出输入的某些统计分布(例如,每个字恰好16次)或具有极其有限的RAM.您可以自行计算或尝试这是否可以实际发生在您身上.
还要注意,铲斗宽度(在上面的描述中为4位)只是结构的参数.一个不计数的Bloom过滤器(桶宽度为1)可以很好地过滤掉大多数独特的单词,但不会过滤掉其他很少出现的单词.较宽的桶大小将更容易在单词之间进行串扰(因为将有更少的桶),并且它还将在第一次通过后降低保证的准确度水平(在4位的情况下发生15次).但是这些缺点在某种程度上在数量上是微不足道的,而我正在想象更具侵略性的过滤效果对于使用非重复的自然语言数据将哈希表保持在亚兆字节大小是至关重要的.
至于布隆过滤器本身的数量级内存需求; 这些人的工作方式低于100 MB,并且具有更具挑战性的应用程序("完整"n-gram统计数据,而不是阈值1-gram统计数据).
我能想到的最好的：
N最常见的单词，您将获得N * partsNumber单词。它并不总是给你正确的答案，但它会在固定的内存和线性时间内工作。