跳至主要內容

Rabin-Karp算法

linwu大约 2 分钟

Rabin-Karp算法

在计算机科学中,Rabin-Karp算法(或Karp-Rabin算法)是一种使用散列(哈希)的字符串搜索算法,由Richard M. Karp和Michael O. Rabin(1987年)创建。

算法

Rabin-Karp算法通过使用哈希函数加速模式与文本中的子字符串的相等性测试。哈希函数是将每个字符串转换为其哈希值的数值的函数;例如,我们可以有hash('hello') = 5。该算法利用了这样一个事实:如果两个字符串相等,则它们的哈希值也相等。因此,字符串匹配(几乎)可以简化为计算搜索模式的哈希值,然后在具有该哈希值的输入字符串的子字符串中寻找匹配。

然而,这种方法存在两个问题。首先,由于存在大量不同的字符串和较少的哈希值,一些不同的字符串将具有相同的哈希值。如果哈希值匹配,模式和子字符串可能不匹配;因此,必须通过比较它们来确认搜索模式和子字符串的潜在匹配;对于较长的子字符串,这种比较可能需要很长时间。幸运的是,对于合理的字符串,良好的哈希函数通常不会产生太多冲突,因此期望的搜索时间将是可接受的。

使用的哈希函数

Rabin-Karp算法的性能关键在于高效计算文本的连续子字符串的哈希值。Rabin指纹是一种流行且有效的滚动哈希函数。

本示例中描述的多项式哈希函数不是Rabin指纹,但它同样有效。它将每个子字符串视为一些基数的数字,基数通常是一个大素数。

复杂度

对于长度为n的文本和p个总长度为m的模式,其平均和最佳情况下的运行时间为O(n + m),空间复杂度为O(p),但最坏情况下的运行时间为O(n * m)

应用

该算法的一个实际应用是检测抄袭。给定源材料,该算法可以快速搜索论文中来自源材料的句子,忽略大小写和标点等细节。由于所寻找的字符串非常丰富,单字符串搜索算法是不实际的。

参考资料

关注公众号

和小伙伴们一起学习

加入技术交流群

扫描二维码 备注加群