请识别此算法：数据流中的概率前k个元素

Question

我记得几年前听说过以下算法，但在网上找不到任何相关的参考资料。它可以仅使用m个计数器，在n个元素的数据流中识别前k个元素（或热门项目）。这对于在使用最小内存的情况下查找顶级搜索词、网络滥用者等非常有用。

算法步骤如下：

• 对于每个元素：
  1. 如果该元素尚未具有计数器，且计数器数量 m，则为该元素创建一个计数器并将其初始化为1。
  2. 否则，如果该元素已具有计数器，则递增该计数器。
  3. 否则，如果该元素没有计数器且计数器数量 > m，则递减现有计数器c。如果c达到0，则用当前元素替换其相应的元素。（c是现有计数器列表中的索引，其中c每当达到此步骤的每个元素时以轮换方式增加。）

我找到了许多其他类似的算法（其中许多列在维基百科文章流算法中，虽然没有描述），但没有找到这个算法。我特别喜欢它，因为它的实现和描述一样简单。

但我想了解更多有关其概率特性的信息-如果我只对前100个项目感兴趣，使用1000个计数器而不是100个计数器会产生什么影响？

- Hunter

---

不是很确定，但看起来像是A. Metwally等人的节省空间。 - Michael Foukarakis

抱歉，@erickson，这不是我的投票。 - Michael Foukarakis

Answer 1

您提到的是著名的Misra-Gries算法，而Space-Saving算法是Misra-Gries算法的一种更快速的版本。请查看此流式算法Dartmouth第1.2节的讲义了解详情。

需要指出的一点是，如果您只使用k个计数器，则该算法不会给出前k个元素，而是会给出所有频率＞m/k的元素，其中m是数据流的总长度。

详细分析可以在我附上的讲义中找到。

- xmerge

Answer 2

您可能正在寻找“频繁”算法。它使用k - 1个计数器来查找所有超过总数的1/k的元素，并于1982年由Misra和Gries发表。它是Boyer和Moore（或Fischer-Salzberg）的“多数”算法的概括，其中k为2。这些及相关算法在一篇有用的文章中介绍，{{link1：“Britney Spears问题。”}}

我在StackOverflow的其他地方提供了算法的详细解释, 我不会在这里重复。重要的是，在一次遍历后，计数器值并不精确表示一个项目的频率；它们可以低估一个取决于流长度并且反比于计数器数量(n / k)的余量。如果您想获得精确的计数而不是频率估计，则所有这些算法（包括Metwally的“SpaceSaving”）都需要第二次遍历。

- erickson

---

我记得当那篇文章发表时曾经读过。但是在第三步的算法中有所不同。文章中的算法会递减所有计数器，而我描述的算法只会递减单个计数器。我模糊地记得这是一个重要因素。它使其更有效率，但我不知道它如何影响准确性。 - Hunter

Answer 3

看起来像是 CPU 缓存替换算法 最近最少使用 (LFU)。

该算法：

1. 对于每个元素，
• 如果元素还没有计数器且计数器 < m，则为元素创建计数器并初始化为 1。 a. 如果缓存未满，则添加行。
• 否则，如果元素已经有计数器，则将其增加。 a. 增加缓存行计数器
• 否则，如果元素没有计数器且计数器 > m，则减少现有计数器。如果 c 达到 0，则用当前元素替换其相应的元素。（c 是现有计数器列表的索引， 当达到此步骤的每个元素时，c 以循环方式递增。）
• a. 转到下一个候选缓存行
• b. 减少当前候选计数器
• c. 如果它还没有达到零，请返回 a。
• d. 驱逐缓存行并用新行替换它。

- Surt