草图算法 = 用极小空间 + 可控误差，快速近似处理超大规模数据
“草图算法（Sketching Algorithms）”是一类在大数据和流式数据处理中非常重要的技术，核心思想是：用一个非常小的“摘要数据结构（sketch）”来近似表示一个巨大的数据集，从而实现高效的计算。
草图算法（Sketching Algorithms）是一类用于处理海量数据或数据流的高效技术，其核心思想是通过构建一个紧凑的“摘要数据结构（sketch）”，在不存储完整数据的情况下，对数据进行近似分析。与传统需要完整数据存储和精确计算的方法不同，草图算法主动接受一定范围内的误差，以换取极大的空间和时间效率提升。这类方法通常建立在概率论与随机化技术之上，通过哈希函数和统计估计来提取数据的关键信息，使得即使面对持续不断的数据流，也能实时更新结果并快速响应查询。
草图算法之所以重要，在于它改变了处理大规模数据的思维方式。在数据规模爆炸式增长的背景下，试图“完整存储再精确计算”往往不可行，而“用小而快的近似结构直接回答问题”则成为更现实的选择。正因为如此，这类算法被广泛应用于流式计算系统、分布式数据处理框架以及实时分析场景中，例如网络流量监控、广告点击统计和推荐系统等领域。可以说，草图算法并不是对精确计算的简单替代，而是一种在资源受限条件下，以概率方式重构计算能力的范式转变。
草图算法通常基于一些关键的概率论和随机化思想：
用于估计集合中“不同元素的数量”
用于估计某个元素出现了多少次
判断某个元素“是否可能存在”
常见应用：
找出最频繁出现的元素
| 特性 | 传统方法 | 草图算法 |
|---|---|---|
| 精确性 | 精确 | 近似 |
| 空间 | 很大 | 很小 |
| 速度 | 较慢 | 很快 |
| 是否适合流式数据 | ❌ | ✅ |
HyperLogLog (HLL) 解决的是基数估计问题：在一个大数据集中，统计不重复元素的个数（即集合的势/cardinality）。
比如统计一个网站今天有多少不重复的 UV，朴素方案是用 HashSet，但当数据量达到亿级时内存开销极大。
直觉理解：
把每个元素哈希成一串二进制，观察这串二进制从最高位起，连续 0 的个数（前导零数量）。
关键推论： 如果在所有元素中，观察到的最大前导零数为 k，那么可以估计集合基数大约为 2ᵏ。
元素哈希值: 00110101... → 前导零数 = 2
00011010... → 前导零数 = 3 ← 最大
01010101... → 前导零数 = 1
最大前导零 k = 3 → 估计基数 ≈ 2³ = 8
单一估计误差很大，HLL 的关键优化是：
① 分桶（Stochastic Averaging）
用哈希值的前 b 位决定放入哪个桶（共 m = 2ᵇ 个桶），其余位用于计算前导零。每个桶独立记录自己遇到的最大前导零数 Mᵢ。
哈希值 64 位: [ 前b位 → 桶索引 ][ 剩余位 → 计算前导零 ]
|___________| |________________________|
桶选择 计数部分
② 调和平均（Harmonic Mean）
最终估计公式：
E = α_m × m² × (Σ 2^(-Mᵢ))⁻¹
m = 桶的数量Mᵢ = 第 i 个桶的最大前导零数α_m = 修正常数（消除系统性偏差）调和平均比算术平均对离群值更鲁棒，大幅降低误差。
| 桶数 m | 内存占用 | 标准误差 |
|---|---|---|
| 512 | ~0.3 KB | 4.1% |
| 1024 | ~0.6 KB | 2.9% |
| 4096 | ~2.5 KB | 1.6% |
| 16384 | ~10 KB | 0.8% |
Redis 的实现固定使用 16384 个桶，每个桶 6 bits，总共仅需 12 KB 内存，误差率约 0.81%，却能统计 2⁶⁴ 量级的基数。
对比一下朴素 HashSet 存 1 亿个 UUID：约需 1.6 GB。
适合：
不适合：
Count-Min Sketch（CMS）解决的是另一个经典问题：频率估计——在海量数据流中，快速估算某个元素出现了多少次。
和 HyperLogLog 的关系：
| HyperLogLog | Count-Min Sketch | |
|---|---|---|
| 问题 | "有多少种不同元素？" | "某个元素出现了多少次？" |
| 答案 | 整体基数 | 单个元素频率 |
CMS 是一个 d 行 × w 列的二维计数器矩阵，配合 d 个独立哈希函数。
每插入一个元素 x，对 d 个哈希函数分别计算列索引，然后对应格子 +1：
对 i = 1..d：
j = hᵢ(x) mod w
matrix[i][j] += 1
时间复杂度 O(d)，空间 O(d × w)。
查询元素 x 的频率时，读取 d 个格子的值，取最小值作为估计：
freq(x) = min over i of matrix[i][hᵢ(x)]
为什么取最小值？
每个格子存的是"哈希到同一列的所有元素的总计数"。由于哈希碰撞，某些格子会被其他元素"污染"而偏大，但不会偏小（只增不减）。所以 d 行中，被污染最少的那行就是最准确的，取最小即可。
这也解释了 CMS 的误差特性：只会高估，不会低估。
设总插入次数为 N，矩阵宽度为 w，行数为 d。
单行的期望误差：某行中，元素 x 的格子被其他元素污染的期望值为 N/w（其他元素均匀分散到 w 列）。
多行取最小：d 行独立，每行误差超过 ε·N 的概率为 1/e（当 w = e/ε 时）。d 行同时超标的概率为 \((1/e)^d\)。
因此，设 w = ⌈e/ε⌉，d = ⌈ln(1/δ)⌉，可以保证：
\[\text{P}[\hat{f}(x) - f(x) > \varepsilon \cdot N] < \delta \]
| 参数 | 含义 | 典型值 |
|---|---|---|
| ε | 允许的相对误差 | 0.01（1%） |
| δ | 超过误差的概率 | 0.001 |
| w = e/ε | 列数 | ≈ 272 |
| d = ln(1/δ) | 行数 | ≈ 7 |
| 内存 | w × d × 4 bytes | ≈ 7.6 KB |
在实际系统里，两者经常组合：
HyperLogLog → 今天来了多少不同用户？（基数）
Count-Min Sketch → 某个用户今天请求了多少次？（频率）
Redis 本身内置了 PFADD/PFCOUNT（HLL），而 CMS 在 Redis 4.0 以上的 RedisBloom 模块中作为 CMS.INCRBY / CMS.QUERY 提供。
热点 TopK 检测：结合 min-heap，实时维护访问频率最高的 K 个 URL / 商品 / IP，内存只需 KB 级别。
网络流量监控：统计每个 IP 的包频率，快速识别 DDoS 攻击中的高频来源。
推荐系统去噪：用户行为流中，过滤掉低频（可能是爬虫）的操作，只保留频率超过阈值的真实行为。
数据库查询优化：PostgreSQL 的统计模块用类似思路估算列值频率，辅助查询计划器选择最优索引。
CMS 有两个先天限制值得注意。第一，它不支持删除——计数格子只加不减，一旦减就可能引入负误差。要支持删除，需要改用 Count-Mean-Min Sketch 或 Conservative Update 变体。第二，高频元素误差更大——因为热点元素本身就占了 N 中的大部分，ε·N 对它反而不那么宽松，需要适当加宽 w。
Heavy Hitters / Top-K 的目标是：
找出数据中出现最频繁的元素（最“重”的那些）
比如：
核心难点是： 数据量巨大 + 可能是数据流（不能全部存下来排序）
假设有数据流：
A, B, A, C, A, B, D, A, B, B
统计结果其实是：
A = 4
B = 4
C = 1
D = 1
Top-2 = A 和 B
但问题是： 在真实场景中，你不能存所有元素再统计
Heavy Hitters 不是“估计总量”，而是：优先保留“可能很重要的元素”，忽略小的本质是：用有限空间维护一个“候选排行榜”
假设我们只想找 Top-2（K=2）：
我们最多只保留 K 个候选
我们维护一个小表（最多 2 个元素）：
{}
A:1
A:1, B:1
A:2, B:1
表满了（已有2个），且 C 不在里面
➡️ 所有计数 -1：
A:1, B:0 → 删除B
变成：
A:1
最终可能得到：
A:?, B:?
它们就是“重元素候选”
关键直觉：
高频元素不容易被“抵消掉”
所以最后留下的：
很可能就是 Heavy Hitters
可以简单对比一下（博客很好用）：
| 方法 | 做什么 | 特点 |
|---|---|---|
| Misra-Gries | 找 Top-K 候选 | 精简、确定性 |
| Count-Min Sketch | 估计频率 | 有误差，但更灵活 |
实际工程里常结合使用
Heavy Hitters 算法的本质，是在有限内存中“不断淘汰弱者”，让真正高频的元素自然浮现出来。
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。