algorithm – TB级数据中最频繁的单词

检查最初为空的Bloom过滤器的1 TB字样;如果一个单词已经存在并且所有存储桶都设置为最大值15(这可能部分或完全是误报),则将其传递通过.如果不是,请添加它.

通过的词被计算;对于大多数单词而言,这是每次,但前15次你看到它们.一小部分人将开始更快地计算,每个单词最多可能出现15次不准确的结果.这是Bloom过滤器的限制.

当第一次通过结束时,如果需要,您可以通过第二次通过来纠正不准确性.取消分配Bloom过滤器,还释放所有不在第十个最常用单词后面15次内的计数.再次浏览输入,这次准确计算单词(使用单独的哈希表),但忽略第一遍中未保留为近似获胜者的单词.

笔记

在第一遍中使用的哈希表理论上可以溢出输入的某些统计分布(例如,每个字恰好16次)或具有非常有限的RAM.您可以自行计算或尝试这是否可以实际发生在您身上.

还要注意,铲斗宽度(以上描述中的4位)只是结构的参数.一个不计数的Bloom过滤器(桶宽度为1)可以很好地过滤掉大多数独特的单词,但不会过滤掉其他很少出现的单词.较宽的桶大小将更容易在单词之间进行串扰(因为将有更少的桶),并且它还将在第一次通过后降低保证的准确度水平(在4位的情况下发生15次).但是这些缺点在某种程度上在数量上是微不足道的,而我正在想象更具侵略性的过滤效果对于将哈希表保持在亚GB大小与非重复的自然语言数据完全至关重要.

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