Rabin-Karp算法 | lovelyfrog's blog

数据结构

发布日期: 2020-03-02

文章字数: 1.5k

本文先简单分析了字符串匹配中暴力搜索效率低的原因，然后引出了两类改进的算法，然后重点关注第二类Rabin-Karp算法，分析了它的算法实现，以及它在多模式串匹配上的高效率。

字符串匹配在计算机科学中是一个非常重要的问题。给定一个长度为m的pattern串，我们想要在一个长度为n的input串中查询是否存在子串与pattern匹配。

最先想到的是暴力搜索，但是这样效率太低了，最坏情况下它的计算时间是$O(mn)$

为什么暴力搜索的效率低呢？

因为它没有用到之前误匹配的信息，一步一步的往前移动当然很慢了。所以我们希望能够最大限度的利用误匹配的信息，使得下一次移动时可以跳过一些肯定不会发生匹配的位置。这样的代表算法有 Knuth-Morris-Pratt(KMP)算法 和 Boyer-Moore string-search算法。
在每次移动的时候，都要重新逐位比较对应的位置上的字符是否相等，这样每次的最坏的计算时间都是$O(m)$. 能不能把它降到$O(1)$ 呢？我们可以把这整个长为m的子串看成一个整体，计算它的hash值，通过前一个子串的hash值我们可以在$O(1)$的时间下推出当前子串的hash值。如果当前子串的hash值和pattern的hash值相等，这个时候我们还要逐位比较一下看是否完全匹配，如果非完全匹配，则需要继续往后移动（因为hash值的范围可能小于不同子串的个数的，所以一定会存在hash冲突）。这就是Rabin-Karp算法的思想，最坏情况下它的计算时间是$O(n+m)$。

下面我们详细介绍一下Rabin-Karp算法。

1.Rabin-Karp算法

先看一下它的伪代码：

function RabinKarp(string s[1...n], string pattern[1...m])
    hpattern := hash(pattern[1...m])                //A: O(m)
    for i from 1 to n-m+1                            //B: O(n)
        hs := hash(s[i...i+m-1])                    //C: O(m) or O(1)?
        if hs = hpattern                                            
            if s[i...i+m-1] = pattern[1...m]        //D: O(m)
                return i
    return not found

可以看到，A,C,D行的计算时间都是$O(m)$, 而B行是$O(n)$，D行只在少数子串和pattern串hash值相等的时候才会执行，而C行在循环中每次都要执行，所以我们的计算时间取决于它，我们要把它降到$O(1)$。

我们可以用Rolling hash，看一个最简单的 rolling hash 式子：

s[i+1...i+m] = s[i...i+m-1] - s[i] + s[i+m]

它可以让C行的计算时间为$O(1)$，但是这样会使得D行执行的次数更多，所以它不是一个好的rolling hash function.

所以就产生两个问题，即如何计算hash，如何从前一项的hash推到后一项的hash

1.1 计算hash

Rabin finger 是一个比较流行且高效的hash函数，给定一个base B（通常是字符串所有能取到的字符的个数，这样可以确保对每个字符串的hash值唯一），对于s[1...m] 可以这样计算它的hash值
$$hash(s[1…m]) = \sum_{i=1}^m s[i]*B^{m-i}$$

如果m很大的话，这里的hash值可能会很大，甚至超过最大能处理的整数导致溢出，所以我们这里取一个质数的模数P（为什么要取质数？），所以我们的hash值可以这样计算：
$$ hash(s[1…m]) = (\sum_{i=1}^m s[i]*B^{m-i}) \ mod P $$

但是这样括号中的数仍然可能会溢出，这里我们需要用到取模的性质来简化运算：
$$(x + y) \ mod \ P = x \ mod \ P + y \ mod \ P$$ $$(xy) \ mod \ P = ((x \ mod \ P) *(y \ mod \ P)) \ mod \ P $$

对于上面的hash函数我们还可以从内向外的运算：
$$ hash(s[1…m]) = \{(…((s[i] * B+s[i-1]) * B+s[i-2]…) * B + s[1] \} mod \ P $$

令$Z = \{(…((s[i] * B+s[i-1]) * B+s[i-2]…) * B + s[1] \} $ , $X = (…((s[i]*B+s[i-1])*B+s[i-2]…)$ 则
$$ hash(s[1…m]) = Z \ mod \ P $$ $$= (X * B+s[1]) \ mod \ P $$ $$= \{(X * B)\ mod\ P + s[1]\} \ mod \ P $$ $$ = \{(X \ mod \ P) * B)\ mod\ P + s[1]\} \ mod \ P $$

对于$X$取模$P$我们可以进一步往里面迭代的计算取模，可以得到最终的hash函数的伪代码:

function hash(s[1...m])
    shash := 0
    for i from 1 to m
      shash = ((shash * B % P) + s[i]) % P

1.2 Roll string hash

接下来需要考虑的是如何从 $hash(s[i…m+i-1])$ 到 $hash(s[i+1…m+i])$, 令$s[i…m+i-1]$ 取模前的值为$Z_i$, $s[i+1…m+i]$取模前的值为$Z_{i+1}$，则:
$$ hash(s[i…m+i-1]) = Z_i \ mod \ P $$ $$hash(s[i+1…m+i]) = Z_{i+1} \ mod \ P $$
而
$$
Z_{i+1} = (Z_i - s[i]*B^{m-1})*B + s[m+i]
$$
所以
$$ hash(s[i+1…m+i]) = \{(Z_i - s[i]*B^{m-1})*B + s[m+i] \} \ mod \ P $$ $$ = \{(hash(s[i..m+i-1]) - hash(s[i]*B^{m-1}) + P) * B + s[m+i]\} \ mod \ P $$
至此，两个问题就都解决了。

2.Java 实现

以cs61B sp19的clab8的Problem2为框架，代码参见

RollingString.java

RabinKarpAlgorithm.java

3.多模式串匹配

思考一下Rabin-Karp算法还有哪些不足的地方，它依然是一位一位向后移来比较的，没有利用错误匹配信息，这也决定了它效率没有KMP高。但是它在多模式串(模式串长度一样)匹配上是高效率的。

考虑在一个文本串上，查询给定模式串集合（包含k个模式串，每个模式串的长度都是m）是否在该文本串上出现。直接看伪代码:

function RabinKarpSet(string s[1...n], set of string subs, m)
    set hsubs := emptySet
    for sub in subs
        insert hash(sub[1..m]) into subs
  hs := hash(s[1...m])
    for i from 1 to n-m+1
        if hs in hsubs and s[i...i+m-1] in subs
            return i
        hs := hash(s[i+1...i+m])
    return not found