知识卡片

普通读书笔记卡 · 3705.d

哈希均匀假设决定期望误命中

理解等级:高级

若把模q指纹近似视为均匀随机映射,一个无效位移与模式同余的概率约1/q,约n个窗口期望产生O(n/q)次误命中。

该期望界依赖哈希分布假设与有效位移数,不是对任意输入的确定保证。

这张卡片看不懂?

已有反馈 · 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