我有一个问题,关于选择在Rabin-Karp算法中用于搜索字符串的q和d 的问题。这个算法使用 q 作为模数和 d 作为哈希函数。
如果我选择2的幂次方作为 q ,并且d = q-1或d = q+1
这些选择会如何影响伪命中?在d=q+1和d=q-1的情况下,哪些模式一定会出现伪命中?请解释。
如果我选择2的幂次方作为 q ,并且d = q-1或d = q+1
这些选择会如何影响伪命中?在d=q+1和d=q-1的情况下,哪些模式一定会出现伪命中?请解释。
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')。
q
和d
代表什么吗?它们与哈希函数有关吗? - mjv