Misra–Gries 摘要

候选表满时的全体减一，可以解释为把当前新元素与 $k-1$ 个不同候选凑成一组互异出现并共同消去。真正频率超过总消去轮数的键不可能被全部抹掉，因此必然留下；摘要计数记录的是未被配对消去的余量，而非精确频率。

可跟踪例子 ​

网络流依次出现 A、B、A、C，取 $k=3$。前三项后候选为 A:2、B:1；读 C 时无空槽，三种不同元素各消去一次，留下 A:1。B、C 被移除不代表真实频率为零，只表示它们尚未被证明超过 $m/3$。

输出与边界 ​

候选可能是假阳性，且计数是下界；若需精确报告超过阈值者，可对候选做第二遍真实计数。一般 turnstile 流含负更新，消去解释不再成立。参数是 $k-1$ 个计数器对应阈值 $m/k$；把计数器数直接写成 $k$ 会造成 off-by-one。朴素每轮全减 $O(k)$，需用摊还或共享偏移优化实现成本。

“全部计数器同时减一”可看作删除一组互异元素，整个流中发生次数受总长度限制；摊还分析公理库摊还分析Amortized analysis对操作序列的总成本作上界，而非逐次最坏成本。据此说明朴素更新或批量实现的总减计数工作。

合并与加权更新 ​

两个分片摘要不能简单逐键相加后保留前 $k-1$ 名；可把候选及其摘要计数视作加权流，再运行同样的批量消去，把总误差预算相加。合并后仍需以全局流长解释 $m/k$。

正整数权重更新可一次增加计数并批量执行共同减量，而不逐个展开；证明要把每次消去的总权重计入 $D$。负权更新则没有“消去 $k$ 个不同出现”的证据，必须换 turnstile 算法。

计数误差从消去组得到 ​

设一共执行 $D$ 次“所有候选减一”。每次恰可配成 $k$ 个互异流元素，所以 $kD\le m$，即 $D\le m/k$。任意元素 $x$ 只有在未被计入候选或随一次全减时才损失一票，因此最终计数 ${\hat{f}}_x$ 满足

这给出确定性一侧误差；频率严格大于 $m/k$ 的元素不可能被完全消去，必在候选表中。

流 a,b,a,c,a,b、$k=3$ 时，前两项占满候选；读到第三种 c 会把 a,b,c 各消去一次，而后续 a,b 再建立计数。摘要最后可能低估实际次数，但不会制造不存在的重频元素。

候选身份和精确频率是两个问题。若要输出所有超过阈值的元素，可在可重读数据上第二遍精确计数；单遍且不能保存原流时，只能给候选与误差界，不能把摘要计数当真实频率。