指定一个键与发现一个键
上一节回答的是一个事后查询问题:给定事先选好的键 ,估计它出现了多少次。Count-Min 草图能够完成这一任务,却不能告诉我们应该查询哪些键:它的计数器混合了多个键,也不记录键的身份。估计值为正,甚至不能说明该键曾经出现过。
本节讨论另一项任务,称为候选键发现。我们在事先不知道哪些键重要的情况下扫描一次有限数据流,希望最后得到一个简短的键列表,保证其中包含所有出现次数超过固定比例的键。下面的方法是确定性的:它既不使用哈希,也没有失败概率。它通常称为 Misra–Gries 频繁项摘要。
下文的结论会各自列出假设并给出完整证明。
模型与假设
数据流是由键组成的有限序列 ,其中 。键可以来自任意全集,算法只需要能够精确判断两个键是否相等。每次更新都插入一次出现;这里没有权重、删除或负更新。对长度为 的前缀,,记
固定整数 。摘要是一张表 ,最多存放 个(键,正整数计数器)对;此外,整数 记录全部递减事件的次数。记 为处理 个数据项后键 的计数器,约定不在表中的键满足 。所有运算都是精确整数运算。由于数据流有限,每个计数器都不超过 。
FREQUENT-CANDIDATES(stream, k) // k >= 1
T <- 空字典 // 键 -> 正整数
D <- 0; N <- 0
按顺序处理流中的每个键 y:
N <- N + 1
如果 y 在 T 中:
T[y] <- T[y] + 1
否则如果 |T| < k:
T[y] <- 1 // 插入并赋值为 1
否则: // |T| = k 且 y 不在 T 中
对 T 中每个键 z:
T[z] <- T[z] - 1
删除每个满足 T[z] = 0 的 z
D <- D + 1 // 不插入 y
返回 (T, D, N)
对于空数据流,循环体不会运行,输出是空表、 和 ;以下所有结论在此情形同样成立。
三个分支直接给出两个不变量。第一,,因为只有在 时才会插入。第二,表中每个计数器都至少为 :增加和插入产生正数,而递减分支会删除所有减到零的计数器。第二条在主要证明中很重要:发生全部递减时,表中恰有 个计数器,且每个都至少为一。
计数恒等式与误差界
直观地看,一次全部递减从 个不同的已存键各去掉一次出现,同时也舍弃到来的键的一次出现;后者与已存键全部不同。因此,每次事件恰好舍弃属于 个不同键的 次出现。其余未被舍弃的次数仍记录在计数器中。
定理 15.1.1
( 计数器摘要的不变量)
对于每个前缀长度 ,其中 :
- ;
- 对每个键 ,包括不在表中的键,。
证明
(对三个分支归纳)
令 ,对 归纳。当 时,表为空,没有键出现过,故 ,所有 均为零,两条结论成立。
假设两条结论对长度 的前缀成立,令 。各频数中只有 改变,增加一。
情况一: 在表中。 增加一, 不变。计数器之和增加 ,与 的增加一致。 和 都增加一,所以 不变;其他 也不变。
情况二: 不在表中且 。 从 变为 , 不变。计数器之和仍增加 ,而 不变。
情况三: 不在表中且 。 已存的 个计数器都至少为一,所以各减一使 恰好减少 。删除现在为零的计数器不会改变总和,因为按照约定,被删除键的计数器变为 。 没有被插入,故 保持 。因此
对于误差, 增加而 不变,故 增加一。表中 个键的计数器各减少一,而频数不变,所以它们的 也各增加一。其他键不受影响。
在每种情况下,每个 要么不变,要么恰好增加一;只有在 也增加一的步骤中, 才可能增加。由于 ,于是 。
证明透视
两条结论为何是同一套计数账目
对所有键的 求和得到 ,因此结论 1 是逐键损失的总和。情况三解释了系数 :已存的 个键与到来的键两两不同,所以一次事件给 个不同的键各增加一单位损失。由于这些键不同,任何单个键在一次事件中最多损失一次,这正是 的原因。若到来的键与已存键相同,则会执行情况一;这也是伪代码中分支顺序重要的原因。
推论。 结论 1 中各量均非负,所以 。由于 为整数,
结论 2 还说明每个计数器是下界,一般并非精确计数:。对不在表中的键,估计值 至多低估 。因此,这张表也能回答对任意指定键的事后查询,其确定性加性误差至多为 。
常见错误
(把计数器当作频率)
存储的计数器只是下界:。在下面的追踪中, 而 。把 报告为次数,或按 对键排序并当作精确排名,都忽略了每个键可能损失的至多 次出现。精确次数需要第二遍扫描。
所有严格重频键都会保留
记 。若 ,称 为重频键。重频键至多有 个:若有 个,它们的频数之和便已超过 。
定理 15.1.2
(严格重频键的保留)
处理完整个数据流后,每个满足 的键都有 ,因此在最终表中。
证明
(计数器减去损失仍为正)
由误差界及 的上界,
计数器是整数,因此 ,即 被存储。
不等式必须是严格的。最终表称为候选集,它包含全部重频键,但也可能包含假阳性。证明并不排除流末尾的低频键占用空位。
常见错误
(把候选集当作重频键报告)
保证是单向的:每个重频键都是候选键,但候选键未必是重频键。在最后一次全部递减之后到达的键,无论频率多少都会以计数 插入,正如下面追踪中的 。若没有第二遍扫描,也没有下文的判据,最终表只能报告为重频键的超集。
例题 15.1.3
(,数据流 的运行过程)
| 数据项 | 分支 | 处理后的表 | |
|---|---|---|---|
| 插入 | 0 | ||
| 插入 | 0 | ||
| 全部递减; 减为 0 并删除;不插入 | 空 | 1 | |
| 插入 | 1 | ||
| 增加 | 1 | ||
| 插入 | 1 | ||
| 增加 | 1 |
因此 ,最终表为 。真实计数为 ,且 。
恒等式成立:。损失 、 均不超过 ,总和为 。上界 也成立。
阈值为 。只有 是重频键,因为 ;定理保证它被保留。候选键 是假阳性,因为 。同时注意, 低估了 。
下面的互动图逐项重放 个计数器的摘要,在每个前缀后显示表、全部递减次数 与恒等式 ,最后列出重频键、假阳性与第二遍精确计数的结果。
反例模式
等于阈值并不能保证保留
取 ,数据流为 。前两项填满表,第三项触发全部递减,使两项都被删除,且 不被插入。最终表为空,。
每个键都满足 ,但没有一个被保留。因此,“每个满足 的 都会被保留”是错误的。证明恰好在需要 的地方失效:此处 。在代码中比较阈值时,应使用精确的整数判断 ,而非浮点商。
第二遍扫描精确恢复重频键
假设可以再次读取同一数据流,例如数据已存储或可以重放。为至多 个候选键分配精确计数器,只统计这些键:
EXACT-HEAVY(stream, T, N, k) // stream 必须是生成摘要的流
对 T 中每个键 z: E[z] <- 0
对流中的每个键 y:
如果 y 在 E 中: E[y] <- E[y] + 1
返回 { z in E : (k+1) * E[z] > N }
定理 15.1.4
(两遍扫描精确恢复)
如果第二遍读取生成 的同一序列,则输出恰好是 。
证明
(在超集上精确计数)
第二遍中,每个候选键 的 都是精确计数。候选键被输出当且仅当它是重频键,所以输出是 。由保留定理,,故 。
计数不受顺序影响,所以第二遍只需要相同的键多重集合,而不必采用相同排列。但如果内容改变,候选列表就失去了原有保证:新数据中的重频键可能从未成为候选键。对于空数据流,两遍均不做任何操作,输出 ,结果正确。
这个摘要无法在一遍扫描中判定什么
第一遍确实能给出部分确定结论。若 ,则 一定是重频键,因为 ;若 ,则 一定不是重频键。在上例中,这两种判据恰好判定了两个候选键。一般而言并非如此,下面的比较说明了这一点。
例题 15.1.5
(追踪中两个候选键的判定)
在 、 的追踪中,最终状态为 ,。对 ,,由 得 : 一定是重频键。对 ,,由 得 : 一定不是重频键。不在表中的键,例如 ,有 及 ,所以也被判定为低频。两种判据都只读取摘要;若某候选键有 ,判据就无法下结论,因为 。
反例模式
相同的最终状态,不同的答案
令 。数据流 的最终表为 ,且 、。数据流 产生完全相同的最终状态。
在第一个流中,,所以 是重频键;在第二个流中,,所以 不是重频键。任何只读取 的规则,都不能在这两个流上同时正确分类 。
这表明此摘要不支持一遍扫描后的精确分类;它并不是针对所有算法的一般下界。
定理对输入的每种排列都成立,但最终表可能依赖顺序。
例题 15.1.6
(同一多重集合的另一种顺序)
取 ,把第一个追踪的多重集合重排为 。 和 填满表; 触发全部递减,删去两者,本身不插入,使 。其后四个 被插入并递增,最终为 ,。恒等式为 ,损失为 、,此时 的计数器是精确的。这个表与 不同,但两种结果都满足所有保证,而这次没有假阳性。
短数据流。 若 ,包括 ,则不会发生全部递减。第 步要发生递减,必须在之前的 个数据项之后已有 个不同的已存键;由于每个已存键至少出现过一次,这不可能。因此 ,由误差界可知每个计数器都精确。阈值满足 ,所以重频键恰好是所有出现过的键,表也恰好包含这些键。当 时,没有键被存储,也没有重频键。
内存与更新成本
摘要最多存储 个键–计数器对,另加 和 ,即 个计数器。但其位成本不能笼统地称为 个字。每个计数器需要 位。每个存储的键也需要自己的表示:对有限全集需 位,而长字符串可能需要多得多的空间。字典本身还有额外开销。在固定字长硬件上,精确运算模型假设计数器不会溢出;若已知 的上界,就可以检查这一点。
若使用精确相等比较对表做简单线性扫描,每次到达的最坏成本为 ,包括可能发生的全部递减,因此 次到达总共耗费 。另一方面,恒等式给出整个过程中计数器递减次数 。这个总量上界不包括查找,也不意味着单次全部递减只需常数时间。删除零计数器是表内部的维护操作,不是删除输入中的出现;此类删除次数不超过插入次数,因而至多为 。若声称字典操作更快,必须说明数据结构与成本模型。
正文的论证不依赖合并这些表;本节也不声称支持带权或负更新,或能在一遍扫描中精确分类。
练习
练习 15.1.7
(以 对 运行算法。写出最终表及 ,指出被删除的键,并验证两个不变量及保留定理。)
核心
解答(4)
- 1
处理前五项
读完四项后,表为 。 到达时表已满,递减后得 。 和 都降到零而被删除, 不插入,。
- 2
完成整个数据流
其后插入 ,再插入 。最终表为 ,,。
- 3
验证两个不变量
关键一步
恒等式成立:。真实次数为 。损失为 ,均不超过 ,总和为 。
- 4
验证保留定理
阈值为 。重频键是 和 ,两者都被保留。候选键 是假阳性。
练习 15.1.8
(取 ,数据流为 ,求最终状态。结果是否与保留定理矛盾?)
基础
解答(2)
- 1
追踪数据流
每个 都插入空表,随后的 发现表已满,触发递减并删去 。最终表为空,, 的上界恰好达到。
- 2
与定理比较
两个频率都等于 。两个键都不是严格重频,所以空表并不与定理矛盾。
练习 15.1.9
(使用第一个追踪的候选键 ()。若第二遍改为读取 ,。输出是什么?哪里出错?)
核心
解答(2)
- 1
在新数据上运行第二遍
计数为 ,都不超过 ,所以输出为空。
- 2
与两个重频集合比较
新数据有 ,其重频集合为 ;原数据流的重频集合则为 。输出对两个数据流都不正确。
依据: 两遍定理要求同一数据流,或至少相同的键多重集合。
练习 15.1.10
(取 、,键为 64 位。界定 ,写出重频测试,并估计表、 及 所需比特数(不计字典开销)。再界定单次更新最坏的递减工作量及总递减工作量。)
核心
解答(3)
- 1
界定 并写出测试
。键是重频的当且仅当 。
- 2
计算比特数
计数器至多为 ,每个需 20 比特。表需 比特。存储 需 20 比特, 需 14 比特,合计 比特。
- 3
界定递减工作量
一次全部递减改动 99 个计数器。整个数据流至多执行 次计数器递减。
本节涵盖仅插入数据流中的确定性候选键发现、其不变量和两遍扫描精确恢复。合并、带权流与带符号流,以及空间下界均不在本节范围内。