11

我一直在尝试用 Java 实现 Rabin-Karp 算法。我很难在恒定时间内计算滚动哈希值。我在http://algs4.cs.princeton.edu/53substring/RabinKarp.java.html找到了一个实现。我仍然无法理解这两条线是如何工作的。

txtHash = (txtHash + Q - RM*txt.charAt(i-M) % Q) % Q;
txtHash = (txtHash*R + txt.charAt(i)) % Q;

我看了几篇关于模数运算的文章，但没有一篇文章能够穿透我厚厚的头骨。请给出一些指示以理解这一点。

4

2 回答 2

28

首先，您需要了解哈希是如何计算的。

让我们举一个以 10 为底的字符串的简单案例。您如何保证字符串的哈希码是唯一的？Base 10 是我们用来表示数字的，而且我们没有冲突！！

“523” = 5*10^2 + 2*10^1 + 3*10^0 = 523

使用上面的哈希函数，您可以保证为每个字符串获得不同的哈希值。

给定“523”的哈希值，如果你想计算“238”的哈希值，即突出最左边的数字5并从右边引入一个新的数字8，你必须执行以下操作：

1）从哈希中去除5的影响：hash = hash - 5*10^2 (523-500 = 23)

2）通过移位1来调整剩余字符的哈希，哈希=哈希* 10

3) 添加新字符的哈希值：hash = hash + 8 (230 + 8 = 238，正如我们预期的那样，它是“238”的以 10 为底的哈希值)

现在让我们将其扩展到所有 ascii 字符。这将我们带到基地 256 世界。因此，相同字符串“523”的哈希现在是

= 5*256^2 + 2*256^1 + 3*256^0 = 327680 + 512 + 3 = 328195。

您可以想象随着字符串长度的增加，您将相对较快地超过大多数编程语言中整数/长整数的范围。

我们如何解决这个问题？通常解决这个问题的方法是使用一个大素数的模数。这种方法的缺点是我们现在也会得到误报，如果将算法的运行时间从二次变为线性，这是一个很小的代价！

您引用的复杂方程只不过是上面用模数数学完成的步骤 1-3。上面使用的两个模量属性是 ->

a) (a*b) % p = ((a % p) * (b % p)) % p

b) a % p = (a + p) % p

让我们回到上面提到的步骤 1-3 ->

1) (使用属性 a 扩展) hash = hash - ((5 % p)*(10^2 %p) %p)

与您引用的内容相比

txtHash = (txtHash + Q - RM*txt.charAt(iM) % Q) % Q;

以下是两者的关系！

  • RM = 10^3 %
  • txt.charAt(iM) % Q = 5 % p
  • 您看到的附加 + Q 只是为了确保哈希不是负数。参见上面的属性 b。

2 & 3) hash = hash*10 + 8, vs txtHash = (txtHash*R + txt.charAt(i)) % Q; 是一样的，但是对最终的哈希结果取模！

更仔细地查看属性 a 和 b，应该可以帮助您弄清楚！

于 2013-05-06T01:26:04.307 回答
6

这是哈希的“滚动”方面。它消除了最旧字符（txt.charAt(i-M)）的贡献，并合并了最新字符（txt.charAt(i)）的贡献。

哈希函数定义为：

            M-1
hash[i] = ( SUM { input[i-j] * R^j } ) % Q
            j=0

（我^用来表示“权力”的地方。）

但这可以写成一个有效的递归实现：

hash[i] = (txtHash*R - input[i-M]*(R^M) + input[i]) % Q

您的参考代码正在执行此操作，但它使用各种技术来确保始终正确（且有效地）计算结果。

因此，举例来说，+ Q第一个表达式中% Q的 它还将计算分成多个阶段，大概是为了防止数值溢出。

于 2011-05-24T13:07:07.557 回答