MENU

Rabin–Karp算法

July 15, 2018 • 文章

一:背景

Rabin-Karp算法(也可以叫Karp-Rabin算法),由Richard M. Karp和Michael O. Rabin在1987年发表,它也是用来解决多模式串匹配问题的。

它的实现方式有点与众不同,首先是计算两个字符串的哈希值,然后通过比较这两个哈希值的大小来判断是否出现匹配。

二:算法分析与实现

选择一个合适的哈希函数很重要。假设文本串为t[0, n),模式串为p[0, m),其中$0<m<n$,$Hash(t[i,j])$代表字符串t[i, j]的哈希值。

当$Hash(t[0, m-1])!=Hash(p[0,m-1])$时,我们很自然的会把$Hash(t[1, m])$拿过来继续比较。在这个过程中,若我们重新计算字符串t[1, m]的哈希值,还需要$O(n)$的时间复杂度,不划算。观察到字符串t[0, m-1]t[1, m]中有$m-1$个字符是重合的,因此我们可以选用滚动哈希函数,那么重新计算的时间复杂度就降为$O(1)$。

Rabin-Karp算法选用的滚动哈希函数主要是利用Rabin fingerprint的思想,举个例子,计算字符串t[0, m - 1]的哈希值的公式如下,

$$
Hash(t[0, m-1])=t[0]\ast\,b^{m-1}+t[1]\ast\,b^{m-2}+...+t[m-1]\ast\,b^0\tag{t[0]代表该字符的ASCII码}
$$

其中的$b$是一个常数,在Rabin-Karp算法中,我们一般取值为$256$,因为一个字符的最大值不超过$255$。上面的公式还有一个问题,哈希值如果过大可能会溢出,因此我们还需要对其取模,这个值应该尽可能大,且是质数,这样可以减小哈希碰撞的概率,在这里我们就取$101$。

则计算字符串t[1, m]的哈希值公式如下,

$$
Hash(t[1,m])=(Hash(t[0,m-1])-t[0]\ast\,b^{m-1})\ast\,b+t[m]\ast\,b^0\tag{请仔细对比上式}
$$

完整代码如下,

#include <iostream>
#include <string.h>

using namespace std;

#define BASE 256
#define MODULUS 101

void RabinKarp(char t[], char p[])
{
    int t_len = strlen(t);
    int p_len = strlen(p);

    // 哈希滚动之用
    int h = 1;
    for (int i = 0; i < p_len - 1; i++)
        h = (h * BASE) % MODULUS;

    int t_hash = 0;
    int p_hash = 0;
    for (int i = 0; i < p_len; i++)
    {
        t_hash = (BASE * t_hash + t[i]) % MODULUS;
        p_hash = (BASE * p_hash + p[i]) % MODULUS;
    }

    int i = 0;
    while (i <= t_len - p_len)
    {
         // 考虑到哈希碰撞的可能性,还需要用 memcmp 再比对一下
        if (t_hash == p_hash && memcmp(p, t + i, p_len) == 0)
            cout << p << " is found at index " << i << endl;

        // 哈希滚动
        t_hash = (BASE * (t_hash - t[i] * h) + t[i + p_len]) % MODULUS;

        // 防止出现负数
        if (t_hash < 0)
            t_hash = t_hash + MODULUS;

        i++;
    }
}

int main()
{
    char t[100] = "It is a test, but not just a test";
    char p[10] = "test";
    
    RabinKarp(t, p);
    
    return 0;
}

输出如下,

test is found at index 8
test is found at index 29

三:复杂度分析

首先看空间复杂度,很容易判断,$S(n)=O(1)$。

再来看时间复杂度,取文本串长度为$n$,模式串长度为$m$,预处理需要$O(m)$,在匹配过程中,最佳情况下,未出现哈希碰撞,$T_{best}(n)=O(n-m)$,最坏情况下,每次都出现碰撞,$T_{worst}(n)=O((n-m)*m)$,因为在现实生活中,$n$往往远大于$m$,因此最后的复杂度表格为,

$S(n)$$O(1)$
$T_{best}(n)$$O(n)$
$T_{worst}(n)$$O(nm)$

四:应用分析

Rabin-Karp算法主要用来检测文章抄袭,比如Semantic Scholar的检测系统。

但从上面的复杂度数据来看,Rabin-Karp算法并无多大优势,用于检测文本抄袭可行么?然而从实际使用中反馈的结果表明,检测抄袭的时间复杂度只有$O(n)$,我觉得主要是因为以下两点,

  1. 现实生活中所作的文章,其文本数据并不会出现我们想象中的那么多次的哈希碰撞;
  2. 很大概率上,被提交的一篇文章,原创的篇幅肯定是远远大于抄袭的篇幅的,也就是说并不会出现我们想象中的那么多次的成功匹配;

五:参考文献

Archives QR Code Tip
QR Code for this page
Tipping QR Code
Leave a Comment

已有 1 条评论
  1. 开发者头条 开发者头条

    感谢分享!已推荐到《开发者头条》:https://toutiao.io/posts/8f9nai 欢迎点赞支持!使用开发者头条 App 搜索 230922 即可订阅《经典算法与数据结构》