了解滚动哈希如何与 Rabin Karp 算法中的模数一起工作

Question

我无法理解滚动哈希算法在通过除以素数将哈希值减少为模值后如何工作。

考虑数字

123456

中的 5 位数字的序列。

第一个块是

12345

。我存储该值，在下一个窗口中，6 进来，1 出去。

所以新的哈希值将是

(12345-1*10^4)*10 + 6 = 23456

。这是相当直观的。

很明显，这些数字很大，所以我们需要一个模函数来保持它们很小。假设我为此目的将

101

作为素数。

因此

12345

将减少为

23

。那么，我将如何从中导出下一个窗口的滚动哈希，

23456

？

Answer 1

您的计算方式与计算

23456

的方式相同，但始终以

101

为模。

(((23 - (10^4 mod 101))*10) mod 101 + 6) mod 101 = 24.

这是您想要的值，因为

23456 mod 101 = 24

。

Answer 2

@dejvuth 的回答是正确的 - 我会在做 rabin-karp 时特别添加这一点，有时你可能会得到 -ve 模量值 - 在这种情况下，最好采用该模量值的 +ve 等价物 - 所以检查之前是否见过相同的模数更容易。

例如： 用这个图案

"abcdabc"

- 和哈希函数：

hash(i) = (49*S[i]+7*S[i+1]+1*S[i+2])%1123

结果：

"abc" -> 1046
"bcd" -> 1103
"cda" -> 33
"dab" -> 62
"abc" -> -77

第二次出现

"abc"

结果是

-77

，它是

1046

的模等价物，因为

(-77 + 1123 = 1046)

PS：我目前没有足够的“声誉”来添加此评论..

Answer 3

我花了很长时间思考@dejvuth给出的答案，我的数学直觉太差了:(

我把理由放在下面，以防万一有人遇到和我一样的困惑，如果有什么问题也请指教：

首先注意模数的分配律：

(a + b) mod n = [(a mod n) + (b mod n)] mod n

a * b mod n = [(a mod n) * (b mod n)] mod n

下面我们定义一个哈希函数，其中'c'是我们当前处理的字符，q是一个小质数，而m是小于字长的最大质数：

h = 0
for c in window:
    h = ( h * q + ord(c) ) % m

现在，为了简单起见且不失一般性，让我们使用窗口大小 2 进行分析，注意我将 ord(c1) 简单地表示为 c1，等等：

h = ( ( ( 0 * q + c0 ) % m ) * q + c1 ) % m )
  = ( c0 * q^1 % m + c1 * q^0 ) % m
  = ( c0 * q^1 % m + c1 * q^0 % m ) % m, because a % b % b = a % b
  = ( c0 * q^1 + c1 * q^0 ) % m, because [(a mod n) * (b mod n)] mod n = a * b mod n

现在很明显，即使使用模，级数仍然可以写成

的形式

h = ( Σ ci * q ^ ( n - i + 1 ) ) % m，其中 n 是窗口大小。

最后，让我们看看当超出窗口大小并且需要去掉窗口中的第一个字符时会发生什么，我们仍然使用窗口大小2来演示，请特别注意取模是在哪一部分应用，以便得到结果：

h = ( h - ( c0 * q^1 ) % m ) % m
  = ( ( c0 * q^1 + c1 * q^0 ) % m - ( c0 * q^1 ) % m ) % m
  = ( ( c0 * q^1 + c1 * q^0 ) - ( c0 * q^1 ) ) % m
  = ( c1 * q^0 ) % m

砰，现在我们得到了我们想要的，哈希值与 c1 相同，是当前窗口中的第一个字符，只需让滚动继续下去，直到我们耗尽字符串。