知识卡片
哈希均匀假设决定期望误命中
若把模q指纹近似视为均匀随机映射,一个无效位移与模式同余的概率约1/q,约n个窗口期望产生O(n/q)次误命中。
该期望界依赖哈希分布假设与有效位移数,不是对任意输入的确定保证。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第32章 字符串匹配 · 查看原书依据
We can base a heuristic analysis on the assumption that reducing values modulo q acts like a random mapping from ∑* to ℤq. The expected number of spurious hits is then O(n/q), because we can estimate the chance that an arbitrary ts will be equivalent to p, modulo q, as 1/q. Since there are O(n) positions at which the test of line 8 fails (actually, at most n − m + 1 positions) and checking each hit takes O(m) time in line 9, the expected matching time taken by the
参考来源
- 位置:《算法导论(第4版)》第32章《字符串匹配》(OEBPS/chapter032.xhtml,文本字符[15000,20000))。
- 结论依据:原文第32.2–32.3节对应算法、定义或复杂度说明;公式与示意图已核对。
- 原始内容:We can base a heuristic analysis on the assumption that reducing values modulo q acts like a random mapping from ∑* to ℤ q . The expected number of spurious hits is then O ( n / q ), because we can estimate the chance that an arbitrary t s will be equivalent to p , modulo q , as 1/ q . Since there are O ( n ) positions at which the test of line 8 fails (actually, at most n − m + 1 positions) and checking each hit takes O ( m ) time in line 9, the expected matching time taken by the