需要帮助理解Rabin-Karp实现的常数时间的Rolling Hash计算

Question

我一直在尝试用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;  

我查看了几篇关于模运算的文章,但没有文章可以穿透我厚厚的头骨.请给出一些指示来理解这一点.

Answer 1

首先,您需要了解如何计算哈希值.

让我们看一个基本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来调整剩余字符的散列,hash = hash*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)%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%p
• txt.charAt(iM)%Q = 5%p
• 您看到的额外+ Q只是为了确保散列不是负数.见上面的财产b.

2&3)hash = hash*10 + 8,vs txtHash =(txtHash*R + txt.charAt(i))%Q; 是相同的,但采取最终哈希结果的模型!

更仔细地查看属性a&b,应该帮助您弄明白!

Answer 2

这是哈希的"滚动"方面.它消除了最古老的字符(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则没有所需的效果).它也将计算分为几个阶段,大概是为了防止数值溢出.