挤掉最小者 · 继承计数 · 门槛 N/k

Space-Saving：k 个槽位捞出 heavy hitters

Count-Min Sketch 回答的是「给定这个 key，它出现了几次」。运维场景里更常见的问题反过来：「出现最多的那十个 key 是谁」。这个问题的输入里没有 key，Count-Min 无从下手——它只有查询接口，没有枚举接口。

Space-Saving 直接对着这个问题设计：固定 $k$ 个槽位，每个槽记一个 key 与它的计数，只保留「看着最热」的那 $k$ 个。

1 · 槽位替换与计数继承

规则只有三条。来了一个 key：

它已在槽里，计数加一。
槽还没满，占一个空槽，计数记一，error 记零。
槽满了，找出计数最小的那个槽，把它换成新 key。新条目的计数是被挤掉者的计数加一，同时把被继承的那个数记成新条目的 error。

第三条是全部的巧思。新 key 不从 1 开始数，而是继承前住户的计数。这看着荒谬——一个刚出现的 key 凭什么带着几万的计数进场？但它保证了一件事：真正的热 key 就算被挤出去过，回来时也能立刻拿回一个不低于真值的计数，不会因为「刚才被挤掉了」而永远追不上。

定义 1.1（Space-Saving 的区间） 每个槽给出 $[\text{count} - \text{error}, \text{count}]$ 。真实频次 $f$ 必落在此区间内：上界成立是因为继承来的量只增不减，下界成立是因为 error 恰好是「不属于本 key 的那部分」的上限。

图 1-1 · 一条 400 条的 zipf 流上逐条走 Space-Saving。黄框是当前计数最小的槽，即下一次替换的候选。可调槽位数

k

，可单步前进观察谁被挤掉、新条目继承到多少。

2 · 门槛 N/k

槽内最小计数不会超过 $N/k$ ： $k$ 个槽的计数之和不超过已计入的总频次 $N$ ，最小的那个自然不超过平均值。这条不等式给出一个可判定的保证。

定理 2.1 真实频次超过 $N/k$ 的 key，在处理完整条流后一定还在槽内。

证明反证。设 $x$ 处理完整条流后不在槽内，取它最后一次被挤出的时刻 $t$ ， $c_t$ 为被挤出时的计数。被挤出的必是当时的最小者，而 $k$ 个槽的计数之和不超过当时已计入的总频次 $N_t$ ，故 $c_t \le N_t/k \le N/k$ 。

$x$ 的每一次出现都使它的计数至少加一：在槽内时直接加，不在槽内时以「继承前住户的计数再加一」的形式进入。故 $c_t$ 不小于 $x$ 在 $t$ 之前的出现次数。 $t$ 之后 $x$ 若再出现就会重新入槽，而 $t$ 是最后一次被挤出，它此后一直留在槽内，与「不在槽内」矛盾。因此 $t$ 之后 $x$ 不再出现， $f(x) \le c_t \le N/k$ 。∎

于是 $k$ 的取法有了判据：让 $N/k$ 落到目标 top- $k$ 里最末那个的频次以下。

3 · k 的取法

实测 $N = 10^6$ 、词表 10 万、zipf(1.1)。真值的第十名频次是 10892。

$k$	内存	报出的 top-10 对了几个	最大高估	槽内最小计数
10	240 B	1	96160	96162
20	480 B	4	44580	44587
50	1200 B	7	15634	15695
100	2400 B	10	4	7026
200	4800 B	10	0	3120

$k = 10$ 求 top-10 只对了一个，最大高估 96160。这一行是本页最初的错误预期：原本以为「求 top-10 取 $k = 10$ 到 30 就够」，实测要到 $k = 100$ （槽内最小计数 7026，已低于第十名的 10892）才全对。 $k$ 与目标 top- $k$ 之间不是常数倍关系，中间隔着分布的形状。

图 3-1 · top-10 命中数与最大高估随

k

的变化。可切换分布陡峭度，观察同一个

k

在陡与平两种分布下的差别。

分布越平门槛越高。zipf 指数从 1.1 降到 0.8 时，第十名的频次从 10892 掉到 3447，同样的 $k = 200$ 从「全对零高估」退成「对 8 个、最大高估 4378」，要 $k = 500$ 才重新全对。

4 · 与 Count-Min 加小根堆的对照

另一条常见路线是 Count-Min 配一个 $k$ 项的小根堆：每处理一个 key 就查一次 Count-Min，估计值大于堆顶就入堆。两者的分工完全不同。

	Space-Saving	Count-Min + 小根堆
回答范围	只答槽里那 $k$ 个 key	任意 key 的频次，外加 top- $k$
误差	区间 $[\text{count} - \text{error}, \text{count}]$ ，可逐条判定是否已锁定	单边高估，界 $\varepsilon N$
上例内存	4800 B（ $k = 200$ ）	54380 B + 堆
上例 top-10 最大高估	0	71
合并	需专门算法	逐格相加

同一批数据上 Space-Saving 用十分之一的内存把 top-10 报得一个不差，Count-Min 那一侧仍带几十的高估。这不说明前者更好：Count-Min 的矩阵还能回答任意 key 的频次，而 Space-Saving 对槽外的 key 一律没有答案。内存少一个数量级换来的是答题范围小一个数量级。

判据落在两个问题上：需不需要问「某个指定 key 的频次」，以及需不需要跨机合并。两个都是「不需要」时，Space-Saving 是更省的那个。

注 · Space-Saving 与 Misra-Gries 是同一个算法的两种写法，前者记 $(\text{count}, \text{error})$ ，后者记一个统一递减的计数。Agarwal 等人 2012 年证明 Misra-Gries summary 是 mergeable 的：拼两张表、保留最大的 $k$ 项、把第 $k+1$ 大的值从所有项里减掉，误差界仍成立。这条路存在，但它不是逐位相加那种零成本的合并。

5 · 参考文献

Metwally, A., Agrawal, D., & El Abbadi, A. (2005). Efficient computation of frequent and top-k elements in data streams. ICDT 2005, 398–412.
Misra, J., & Gries, D. (1982). Finding repeated elements. Science of Computer Programming, 2(2), 143–152.
Agarwal, P. K., Cormode, G., Huang, Z., Phillips, J. M., Wei, Z., & Yi, K. (2013). Mergeable summaries. ACM Transactions on Database Systems, 38(4), 26.
Cormode, G., & Hadjieleftheriou, M. (2008). Finding frequent items in data streams. Proceedings of the VLDB Endowment, 1(2), 1530–1541.