我记得几年前听说过以下算法，但在网上找不到任何参考。它仅使用 m 个计数器来识别 n 个元素的数据流中的前 k 个元素（或重量级元素）。这对于在使用最少内存的情况下查找热门搜索词、网络滥用者等特别有用。
算法：对于每个元素，
- 如果该元素还没有计数器且计数器 m，则为该元素创建一个计数器并初始化为 1。
- 否则，如果该元素确实有一个计数器，则增加它。
- 否则，如果元素没有计数器且计数器 > m，则递减现有计数器 c。如果c达到0，则将其对应的元素替换为当前元素。 （c 是现有计数器列表的索引，其中 c 对于到达此步骤的每个元素以循环方式增加。）
我发现了许多其他类似的算法（在这篇关于的维基百科文章中列出了其中许多，尽管没有描述）流算法 http://en.wikipedia.org/wiki/Streaming_algorithm#Heavy_hitters），但不是这个。
我特别喜欢它，因为它的实现和描述一样简单。
但我想更多地了解它的概率特征——如果我只对前 100 个项目感兴趣，那么使用 1,000 个计数器而不是 100 个计数器会有什么效果？
您正在谈论著名的 Misra-Gries 算法，而节省空间算法是 Misra-Gries 算法的更快版本。详情请查看本讲义流算法达特茅斯 http://www.cs.dartmouth.edu/~ac/Teach/CS49-Fall11/Notes/lecnotes.pdf第 1.2 节。
我想指出的一件事是，如果只使用 k 个计数器，该算法不会给出 top-k 元素，而是给出频率 > m / k 的所有元素，其中 m 是数据流的总长度。
详细分析可以参见我所附的讲义。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
