存储来自 count-min-sketch 的前 k 个结果

Question

我需要在流中存储前 k 个最频繁的元素。为了估计频率，我使用 count-min-sketch 算法。我的流由键（作为字符串）组成。所以基本上每次我在我的流中遇到一个新键时，我都会通过查看 count-min-sketch 数据结构来计算到目前为止当前键的频率。但是我无法存储前 k 个最常用的键。

我的第一个想法是将它们存储在一个固定大小为 k 的最小堆中。我将 [频率，键] 存储在这个最小堆中，并使用比较器比较频率。因此，每次我获得一个键的频率时，我都会尝试查看堆大小是否超过 k，如果是，那么我将当前键的频率与最小堆中的最高（最小）频率进行比较，如果我当前的键是频率较大然后我弹出顶部，并将我的密钥插入堆中。

但是我意识到最小堆不是一个集合，这意味着它允许重复。假设我有一个非常热的键，并且我一直在流中计算它，所以每次我将这个 [频率，键] 插入堆中时，最终我的堆将充满相同的键，只是频率不同。

所以我想知道有没有一种好方法可以在 count-min-sketch 中存储前 k 个不同的更频繁的元素。

Answer 1

您还可以维护所有三个数据结构 1. Count-min 草图以存储您在流中遇到的所有内容 2. 大小为 k 的最小堆 3. 大小为 k 的哈希图如果是热门项目 - 您增加计数并从 count-min 草图中获取新频率，假设此项目已存在于 min-heap 中，则您从哈希映射中获取该项目并增加频率当您遇到一个频率刚刚增加并进入著名的最小堆的不同项目时，您可以同时从最小堆和哈希映射中驱逐根，因此基本上最小堆可以帮助您维护前 k 个频繁项目和哈希-map 随机访问那些频繁项目。请注意，min-heap 和 hash-map 都可以映射到相同的内存地址，因此更新频率只能对存储在 hash-map 中的项目进行

Answer 2

维护[key,<frequency,position>]堆中已经存在的对的哈希图是有意义的。position指的是堆内键的索引（假设是基于数组的堆）。当键到达时，您检查 2 个条件：- 键在哈希图中- 它的频率已经改变如果两者都为真，你会O(1)及时在堆中找到键，因为你已经将它的位置存储在哈希图中，然后修改键的频率，并根据频率是增加还是减少，你从那个位置（O(logn)）。更改位置后，您可以使用新的频率和位置值更新该键的哈希图条目。如果第一个为假，则遵循通常的逻辑，即将键与根进行比较，如果堆已满且键的频率大于根的频率，则将根从堆中弹出并将其从哈希图中删除，同时插入进入堆和哈希映射的键。如果键在哈希图中但它的频率没有改变，你什么都不做。