algorithm - 日志梳理算法

Question

我们得到了这些由 16 字节代码组成的 ~50GB 数据文件，我想找到任何出现频率为 1/2% 或更多的代码。有什么方法可以在单次传递数据时做到这一点？

编辑:有大量代码 - 可能每个代码都不同。

结语:我选择 Darius Bacon 作为最佳答案，因为我认为最好的算法是修改他所链接的多数元素。大多数算法应该是可修改的，只使用少量的内存——比如我认为 201 代码可以获得 1/2%。基本上，您只需在流中计算最多 201 个不同的代码。一旦找到 201 个不同的代码，就将每个代码丢掉一个(从计数器中减去 1，忘记任何变为 0 的代码)。最后，您最多丢弃了 N/201 次，因此任何出现次数超过此次数的代码一定仍然存在。

但这是一个两次通过的算法，而不是一次。你需要第二次通过来计算候选人的人数。实际上很容易看出这个问题的任何解决方案都必须使用至少 2 遍(您加载的第一批元素可能都不同，其中一个代码最终可能恰好是 1/2%)

感谢您的帮助!

Answer 1

Metwally et al., Efficient Computation of Frequent and Top-k Elements in Data Streams (2005) .我在雅虎工作时阅读的其他一些相关论文现在找不到了；但这看起来是一个好的开始。

编辑:啊，看到这个Brian Hayes article .它勾勒出 Demaine 等人的精确算法，并附有引用资料。它以很少的内存一次性完成，产生一组项目，包括您正在寻找的常见项目(如果存在)。获得准确的计数需要(现在易于处理的)第二遍。