Count-Min Sketch (CMS)

引言：“频繁项”问题

想象你正在管理一个全球网络。你想知道：“IP 1.2.3.4 在过去一小时内发送了多少次请求？” 在每秒数十亿个数据包的流中，为每一个 IP 都存一个计数器会消耗数 TB 的内存。

Count-Min Sketch 是一种估算流中事件 频率 的概率型结构。它就像布隆过滤器，但它存的不是比特位 (0/1)，而是 计数器。它可能会稍微高估频率，但 绝对不会低估 频率。

算法要解决什么问题？

• 输入： 元素流。
• 输出： 任意给定元素的估算出现频率（计数）。
• 承诺： 在海量数据集下，使用固定、低廉的内存来跟踪频率。

核心思想 (直觉版)

想象一个 多层计数器网格。

1. 网格： 创建 $D$ 行、$W$ 列的计数器。
2. 添加元素： 对于每一行，使用不同的哈希函数找到一个列，并增加该计数器的值 (count[row][col]++)。
3. 查询元素： 同样使用这 $D$ 个哈希函数。你会得到 $D$ 个不同的计数值（每行一个）。
4. 答案： 这 $D$ 个计数值中的 最小值 就是你的估算结果。

为什么取最小值？因为由于哈希冲突，某些计数器可能被多个元素共享（导致高估）。同一个元素在所有 $D$ 行都发生严重冲突的概率极低。

为什么要用它？

• ✅ 寻找“重炮手” (Heavy Hitters)： 无需存储所有数据，即可在流中找到最频繁出现的项（前 1%）。

• ✅ DDoS 防护： 快速识别发送异常高流量的 IP 地址。

• ❌ 高估风险： 它可能会说一个元素出现了 1005 次，而实际只有 1000 次。但它绝不会说 999 次。

• ❌ 去重计数： 如果你想知道“有多少个唯一元素”，请用 HyperLogLog。CM Sketch 是用来问“这个元素出现了多少次”。

典型业务场景

• ✅ 实时分析： 实时跟踪 Twitter 上的热门話題。
• ✅ 內容交付 (CDN)： 确定哪些視頻是當下的“爆款”，以便將其推送到邊緣緩存。
• ✅ 数据库优化： 查询优化器使用 Sketch 来估算列中重复值的分布，从而计算 Join 操作的成本。

性能与复杂度总结

• 时间： $O(D)$，$D$ 是哈希函数的数量（通常很小，如 5-10）。
• 空间： $O(D \cdot W)$ —— 根据你要求的误差容忍度确定的固定内存。

小结：一句话记住它

“Count-Min Sketch 是‘频率估算器’。通过在多个哈希计数器中取最小值，它过滤了噪声，并为你提供了一个可靠的事件频率上限。”