KMP 单元利用前缀信息确定性地匹配模式。另一种方法比较等长字符串的短数值摘要。窗口移动时可以有效更新这些指纹,但指纹相等只能提供可能相等的候选。
字符串的多项式
令 为素数,把有限字母表的每个符号单射编码为 的元素。选择随机种子之前,先固定长度 的模式 及长度 的文本 。独立于这些字符串,从整个域均匀选择 。
定义 6.3.1
(多项式指纹)
对已编码的长度 字符串 及底数 ,指纹定义为
常数次幂 ,包括 的情况。
相同字符串必有相同哈希值。对不同字符串 ,单射编码保证差多项式非零,且次数至多 。
定理 6.3.2
(两个字符串的碰撞界)
设 是固定的已编码长度 字符串, 在 上均匀。则
证明
(碰撞就是非零多项式的根)
令 。由于编码是单射且 ,某个系数 非零,所以 非零且次数至多 。碰撞恰好意味着 。
域上非零 次多项式至多有 个不同根:每个根提供一个线性因子,而所有不同根因子的乘积整除该多项式。因此在 个机会均等的 值中,至多 个会造成碰撞,这就是所述的界。当 ,非零差多项式是常数,碰撞概率为零。若次数上界至少为 ,此概率界可能没有信息;证明仍然有效。
证明透视
根的数目给出碰撞界
核心想法是把概率陈述转化为根的计数。先固定 ,再抽取 ,这使 成为固定的多项式,而碰撞只是 在 个机会均等的值中的一个根。
每个假设都恰好用一次。编码是单射,使 非零,因此只有有限多个根。域的性质给出根的上界:在环 上,二次多项式 有四个根 ,所以没有域时这个计数不成立。 均匀且与字符串独立,使根的计数成为概率。若编码不是单射,不同符号也可能使 为零,那么每个 都会碰撞。
下一个陈述同时涵盖文本中的所有窗口。
定理 6.3.3
(全部窗口的碰撞界)
对 的固定 个窗口,任何不等于 的窗口与 指纹相同的概率至多为 。
证明
(共用种子下的并集界)
由上一个定理,每个不等于 的窗口与 碰撞的概率至多为 。至多 个事件中至少有一个发生的概率,不超过各事件概率之和,这就是所述的界。所有窗口共用同一种子,碰撞事件可能相依;并集界不要求独立。
若在看到 后才选择字符串,那是不同的对手模型,不受此固定输入保证涵盖。
移动窗口
令当前窗口从位置 开始,并以 表示文本位置 的编码符号。使用从零开始的下标及 ,令 。
定理 6.3.4
(滚动更新)
以 如上,
此恒等式不需要模除法,对每个 (包括 )及 都成立。
证明
(去掉最高次项、移位、再附加)
按定义,。减去 即去掉 一项,余下 。乘以 并代入 ,得 。 缺少的那一项,即 ,是 ,这一项被加上。当 时求和为空,公式成为 。
例题 6.3.5
(小域中的一次滚动更新)
取 ,,,,,即 。第一个哈希值为 。此时 ,
直接计算得 ,所以更新与定义相符。
例题 6.3.6
(边界情形:底数为零)
当 且 ,除最后一项外各项都消失,所以 就是最后一个符号。对 ,两个窗口的哈希值分别为 和 。滚动公式仍然有效:,。这样的底数使任何最后一个符号相同的两个窗口碰撞,是一次坏的抽取。它出现的概率为 ,与碰撞界一致。
小域中的一次碰撞
例题 6.3.7
(两个不同窗口有相同哈希值)
取 ,把 编码为 ,令模式 、文本 。窗口为 和 。对底数 ,
两者恰在 ,即 时碰撞。此时哈希值均为 ,但 ;第二个窗口则真的匹配。若 在 均匀,这对不同字符串的碰撞概率是 ,与一次多项式的界吻合。
反例模式
哈希匹配不能证明字符串匹配
在 时,若返回所有哈希匹配的窗口,便会错把 bac 的第一个窗口报成 ac 的出现位置。逐符号直接核对每个候选可移除假阳性。在所述精确域算术下,这使输出精确;单靠哈希则有单侧错误:真正匹配的窗口绝不会有不同哈希值。
工作量与保证
计算模式、第一个窗口的哈希值及 需 次域运算;其后每个窗口只需额外 次。若能以常数时间取得移出及移入的编码符号,扫描需 次域运算。流式实现可用环形缓冲区保留最近 个符号。域运算的位成本取决于 及算术实现。
不核对时,应把哈希匹配报作候选,并使用上述固定输入概率界。若逐符号核对每次哈希匹配,正确性是确定性的,但至多 次核对各可耗 ,包括真正匹配;最坏工作量变为 。这不能取代 KMP 的确定性线性时间保证。精确的随机域抽样与算术是假设,并非对特定机器实现的声称。
常见错误
常见错误
(用错误的幂移除移出的符号)
移出的符号带有 ,而不是 ,因为窗口有 个符号,其第一个符号的指数是 。在 、、、 的例子中,若用 ,得 ,而 的正确指纹是 。
常见错误
(预先固定底数)
界 是对独立于字符串而抽取的随机 而言的。若底数是公开的常数,便可以构造出与模式碰撞的文本。取 及固定底数 ,如前所算,模式 与窗口 必定碰撞,不论文本多长。要在输入选定之后才抽取底数,保证才得以恢复。
习题
快速检查
(例子中取 ,求 与 模 的哈希值。)
利用 和 。
解答 · 答案
,。两个哈希值不同,所以在 时这一对不碰撞。
快速检查
(单射编码下,两个不同单符号字符串的碰撞概率是多少?)
当 时,指纹是什么?
解答 · 答案
零。当 ,指纹就是符号本身,,单射使不同符号无论 为何都不相同。这与界 一致。
快速检查
(若 且 ,哪个符号决定哈希值?)
当 时,哪个幂不为零?
解答 · 答案
最后一个符号,因为只有 保留下来,所以 。滚动公式仍适用,如底数为零的例子所示。
快速检查
(所有窗口共用种子,为何仍可用并集界?)
并集界对这些事件假设了什么?
解答 · 答案
并集界对任意事件都成立,不要求事件之间独立。共用种子使碰撞事件相依,但至少有一个发生的概率仍不超过各事件概率之和。