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。朴素每轮全减会访问至多 $k-1$ 个计数器，单次更新可以花费 $O(k)$ 时间。

更新成本 ​

摊还分析理路摊还分析Amortized analysis对操作序列的总成本作上界，而非逐次最坏成本。将全减的成本计入消去的流元素：总共至多 $m/k$ 轮，每轮访问 $k-1$ 个槽，故全部计数器递减合计 $O(m)$ 次。再加每项的一次候选查找，以及总计 $O(m)$ 次插入、删除，使用每次期望常数成本的哈希字典时，总期望时间为 $O(m+1)$；使用平衡搜索树时可给出 $O((m+1)\log (k+1))$ 上界。这里分别计算消去的确定性总工作和字典实现的成本。

正权批量更新 ​

对正整数权重更新 $(x,w)$，若 $x$ 已在表中，直接加 $w$；若有空槽，直接插入计数 $w$。否则令

将所有 $k-1$ 个候选减 $d$，同时从新键的待处理权重中消去 $d$，并删除零计数。若新键还有剩余权重，则必已腾出空槽，将其插入。这一步消去 $k$ 个不同键各 $d$ 质量，故把 $D$ 增加 $d$ 后，仍有 $C=M-kD$，其中 $M$ 是累计输入质量。每键欠估至多 $D\le M/k$。批处理不用展开成 $w$ 次更新；朴素实现仍可能扫描 $O(k)$ 个候选。

合并时包括再次压缩的误差 ​

设两份摘要使用相同参数 $k$，分别表示互不重叠的流位置或正权更新片段，其总质量为 $M_A,M_B$，消去量为 $D_A,D_B$，残留计数和为 $C_A=M_A-k{D}_A$、$C_B=M_B-k{D}_B$。把两份候选及其计数送入上述加权算法，得到新候选；设这次压缩又消去 $D_{\ast }$，输出计数和为 $C$。那么

对每个键，两个旧摘要的欠估相加至多 $D_A+D_B$，新压缩再增加至多 $D_{\ast }$。因此合并后的总误差预算为

这使 Misra–Gries 成为保持同一全局误差保证的可合并摘要理路可合并摘要mergeable summary · mergeable sketch让分片流的有限状态在不读取原始数据时组合，并保持与集中处理相容的统计保证。。同一个不变量在任意合并树上归纳成立；新压缩的误差已经计入，而非只累加两个旧预算。该实现可能产生不同候选状态，但始终保持相同的全局欠估保证。

例如 $k=3$，第一片为 A、B，第二片为 C。两片都没有发生全减，旧预算均为零；合并三个带权候选时却会消去一组，得到空表，故新预算必须为 $1$。仅相加旧预算会错误声称三个频率都被精确保留。

候选始终来自已见键，但可以低于目标重频阈值。需要精确名单时，可在第二遍中重新统计候选；单遍恢复则按重项页面给出的灰区阈值筛选，并保留确定性的计数误差。