频率问题
数据流包含对固定全集 中键值 的更新 ,权重 是非负整数。令 为键值 的权重总和, 为总权重;处理的更新数有限。为每个不同键值保留精确计数器可能代价高昂;Count–Min 草图以精确性换取紧凑表格。它可回答指定键值的频率,但本身不会列出所有出现过的键值。
定义 1.2.1
(Count–Min 草图及其估计)
取正整数 (宽度)和 (深度),并对各行 独立选取随机哈希函数 。每一行只假设以下碰撞界:
初始时每个计数器 均为零。每次更新 ,就在每行的 加上 。键值频率的估计为
数据流及任何查询键值均与所选哈希独立地预先固定。我们不要求同一行中不同碰撞彼此独立。还必须存储哈希函数的描述及种子,其大小取决于所选函数族与全集。碰撞条件是要为该函数族核实的假设,并非任意哈希函数都具备的性质。
命题 1.2.2
(估计永不低估)
若每个更新权重均非负,则对每个键值 及哈希函数的每个实现,都有 。
证明
(每个被查询的计数器都包含完整计数)
固定一行 。每次更新 都把 加到 ,所以这个计数器收到 的全部,另加满足 的键值 的权重。这些额外权重非负,故对每个 都有 ,对 取最小值也至少为 。
论证只用到碰撞权重的符号,别无其他,所以更新的非负假设不能删去。
反例模式
负更新可使估计低于真值
断言:对任何整数更新数据流,Count–Min 估计都是上界。取 、,并让哈希在两行都把键值 和 送到同一个桶。处理 及 。 的两个被查询计数器都是 ,所以 ,但 。证明恰好在假设碰撞权重非负的地方失效。修正后的陈述就是上面的命题:更新非负时估计是单侧的;有负更新时,既不声称这个不等式,也不声称下面的误差界。
固定键值的误差界
定理 1.2.3
(Count–Min 误差界)
设更新非负,在抽取哈希前固定数据流及键值 ,并设 。若 ,则
特别地,对 ,取 、 可使成功概率至少为 。
证明
(每行用 Markov,各行之间用独立性)
由上一命题,下方不等式恒成立。当 时,所有计数器和频率均为零,结论确定地成立,不必除以 ;以下设 。第 行超出真实计数的部分是
由期望的线性性与碰撞假设,
此求和不需要各项独立。Markov 不等式给出
因为完整的各行哈希函数相互独立,而数据流已固定,各行误差 相互独立。最小估计超过 ,只可能在每一行的误差都超过 时发生,其概率至多为 。最后, 给出 。
证明透视
各个假设在误差界中的位置
证明分两步。第一步在单一行内:超出量的期望只需要两两碰撞概率与线性性,所以同一行内的哈希值可以任意相关。接着 Markov 不等式需要 ,这又是更新非负的假设。这个单行界很弱,只有 。第二步是放大:取最小值把“有一行良好”变成成功,所以失败需要全部 行同时失败;整行哈希的独立性只在这里用到。在抽取哈希前固定数据流与键值,才使各 只是独立哈希的函数;看过表格后才选的键值会破坏这一步。
这是对固定数据流及键值、以哈希选择为随机性的概率陈述;它不保证看到表格后自适应选出的每个键值。若预先指定有限集合 ,其中有 个键值,联合界给出同时成功的概率至少为 ;取 可使总失败概率至多为 。联合界不要求不同键值的失败事件相互独立。
常见错误
(误差相对于总权重是加性的,而非相对于该键值)
界写作 ,其中 是整个数据流的权重。它并非说 。对于 远小于 的罕见键值,估计可以是真实计数的许多倍,而仍然符合定理。
小表格与合并
例题 1.2.4
(从固定表格读出估计)
设 、、,并取 、。第 1 行让 、 哈希至桶 0, 至桶 1;第 2 行让 、 哈希至桶 1, 至桶 2。非零计数器为
查得的两行计数是 ,故 ; 查得 ,估计为 ; 查得 ,估计为 。每个估计都不小于真实计数,正如命题所保证;取最小值则去掉了较干净那一行以外的碰撞。此例展示特定函数的碰撞;单个选定表格不是概率界的实验证明。
例题 1.2.5
(为固定查询集合确定草图大小)
设查询是预先指定的 个键值,,总失败概率 。宽度与 无关:。深度须满足 ,所以 。此时 ,因此以至少 的概率,全部 个估计都落在 。表格有 个计数器。若只有一个键值, 已足够;多出的五行是联合界的代价。
只有当两个不重叠更新批次的草图具有相同维度及各行哈希函数时,才能把相应计数器相加来合并。所得结果等同以同一组哈希顺序处理两批更新。若批次重叠,共有更新会重复计数。若合并后的数据流与共用哈希选择独立,上述界可用于该数据流。
例题 1.2.6
(以共用哈希合并两批更新)
沿用第一个例子的哈希。第 1 批是 ,第 2 批是 。草图 1 有 、、;草图 2 有 、、。逐项相加得
串接后的数据流有 、、,直接处理得 、、、,正是同一个表格。因此 ,与整个数据流的单一草图完全相同。
常见错误
(把以不同种子建立的草图相加)
只有描述同一组桶的计数器才可相加。取 、,草图 1 用 并接收 ,草图 2 用 并接收 。相加后计数器为 ;用 查询 读到 ,但 。即使更新非负,单侧保证也失效,因为合并所得的表格不是任何数据流在单一哈希选择下的草图。
表格使用 个计数器,每次更新改动 个计数器;此外还要计算及存储哈希描述。若字长模型中算术及哈希均为常数时间,则使用 个计数器,每次更新及查询需 次操作。精确非负计数器可达 ;当 ,每个最多需要 个比特。固定字长溢出会破坏精确算术,也可能破坏上述保证。计数器数目小并不自动给出完整的比特级内存界。
习题
快速检查
(在第一个例题中,为什么即使所有更新非负, 仍大于 ?)
看看每一行中哪些键值与 共用桶。
解答 · 答案
两个被查询计数是 和 :第 1 行中 与 碰撞并加上 ,第 2 行中 碰撞并加上 。每一行都有正的碰撞贡献,所以连最小值 也大于 。非负性只保证 ,并不保证相等。
快速检查
(若 、,按取上整的方法求整数 、,并写出它们对一个固定键值的概率保证。)
解答 · 答案
,。对在抽取哈希前固定的数据流及键值,独立选取各行哈希后,估计落在 与 之间的概率至少为 。
快速检查
(用户查询草图、看过表格后,挑出估计看来最大的键值。固定键值定理能否界定这个估计的误差?)
解答 · 答案
不能。定理要求键值与哈希独立地预先固定。看过表格后才选的键值,可能正因其桶中碰撞很大而被选中。只有预先指定的 个键值集合才受保证,方法是取 的联合界。