如何在Rabin-Karp算法中选择模值？

Question

3

我有一个问题，关于选择在Rabin-Karp算法中用于搜索字符串的q和d 的问题。这个算法使用 q 作为模数和 d 作为哈希函数。

如果我选择2的幂次方作为 q ，并且d = q-1或d = q+1

这些选择会如何影响伪命中？在d=q+1和d=q-1的情况下，哪些模式一定会出现伪命中？请解释。

- prilia

你能更具体地说明 q 和 d 代表什么吗？它们与哈希函数有关吗？ - mjv

我编辑了问题，谢谢。 - prilia

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Aki Suihkonen · Accepted Answer

X mod (2^n +1) 可以描述为交替的和/差，例如：

当 X= 0x11223344，n=8，X mod 257 == 0x44 - 0x33 + 0x22 - 0x11 mod 257。这里的问题是任何重复的字母都会相互抵消 -- 不太实用 -- 当然 n 不一定要是 8。

X mod (2^n -1) 将是所有 n 比特模式的总和，例如：

当 X= 0x11223344，n=8，X mod 255 ==( 0x44 + 0x33 +0x22 +0x11 ) mod 255

这里的问题是切换字节会相互抵消：Hash('ab') = Hash('ba')。