如何从计数素描中获得最高K元素？

Question

我正在阅读概率数据结构count-min-sketch是如何用于在数据流中查找顶部k元素的。但我似乎不能把我的头绕在我们维持一堆得到最终答案的那一步上。

问题是： 我们有一个项目流[B, C, A, B, C, A, C, A, A, ...]。我们被要求找出最常出现的项目。

我的理解是，这可以用微批次来完成，在这个过程中，我们在开始做一些真正的工作之前积累了N个项目。

hashmap+heap方法很容易让我理解。我们遍历微批次并通过计数元素建立一个频率图(例如{B:34, D: 65, C: 9, A:84, ...})。然后，我们通过遍历频率映射来维护大小为k的最小堆，并根据需要使用每个[item]:[freq]添加到堆中并从堆中逐出。直截了当，一点也不花哨。

现在使用CMS+heap，而不是hashmap，我们有这个概率的有损2D数组，我们通过遍历微批处理来构建它。问题是:考虑到这个CMS?，我们如何维护大小为k的最小堆？

CMS只包含一串数字，而不是原始项。除非我还保留了一组来自微批处理的独特元素，否则我无法知道在最后需要针对哪些项构建堆。但如果我这么做了，难道这不就辜负了使用CMS来节省内存空间的目的吗？

在遍历列表时，我还考虑了实时构建堆。随着每一个项目的到来，我们可以快速更新CMS，并得到该项目的累积频率在这一点。但是，这个频率是累积的，这对我没有多大帮助。例如，使用上面的示例流，我们将得到[B:1, C:1, A:1, B:2, C:2, A:2, C:3, A:3, A:4, ...]。如果我们使用相同的逻辑来更新最小堆，我们就会得到不正确的答案(带有副本)。

我肯定漏掉了什么东西。请帮我理解一下。

Answer 1

保持大小为k的哈希映射，键为id，值为Item(id，count)，将大小为k的极小堆与项作为事件，更新count-min 2d数组，获取min，在hashmap中更新项，在堆中冒泡/冒泡以重新计算项的顺序。如果堆大小> k，则轮询最小项并从hashmap中删除id。

Answer 2

下面的解释来自于这个Youtube视频的评论

我们需要储存钥匙，但只有K(或更多)。不是全部。当每个键都出现时，我们执行以下操作：

• 把它加到伯爵小品里。
• 从伯爵小品中提取钥匙数。
• 检查当前键是否在堆中。如果它出现在堆中，我们在那里更新它的计数值。如果堆中没有堆，则检查堆是否已满。如果未满，则将此键添加到堆中。如果堆已满，则检查最小堆元素并将其值与当前键计数值进行比较。此时，我们可以删除最小元素并添加当前键(如果当前键计数>最小元素值)。