algorithm - Rabin-Karpアルゴリズムでモジュラス値を選択するには?

Question

文字列を検索するためのRabin-Karp アルゴリズムのqとd の選択について質問があります。このアルゴリズムは、値qをモジュラスとして使用し、 dをハッシュ関数として使用します。

2 乗の数としてqを選択し、d=q-1 または d=q+1を選択した場合

• これらの選択はスプリアス ヒットにどのように影響しますか?

• d=q+1 の場合と d=q-1 の場合にスプリアスが確実にヒットするパターンは？

Answer 1

X mod (2^n +1) は、交互の和/差として記述できます。

X= 0x11223344, n=8, X mod 257 == 0x44 - 0x33 + 0x22 - 0x11 mod 257. ここでの問題は、繰り返し文字がそれ自体をキャンセルすることです. 8.

X mod (2^n -1) は、n ビット パターンすべての合計になります。

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

ここでの問題は、バイトの切り替えがそれ自体をキャンセルすることです: Hash('ab') = Hash('ba')。