拉宾-卡普算法

在计算机科学中，拉宾-卡普算法（英语：Rabin–Karp algorithm）或卡普-拉宾算法（Karp–Rabin algorithm），是一种由理查德·卡普与迈克尔·拉宾于1987年提出的、使用散列函数以在文本中搜寻单个模式串的字符串搜索算法单次匹配。该算法先使用旋转哈希以快速筛出无法与给定串匹配的文本位置，此后对剩余位置能否成功匹配进行检验。此算法可推广到用于在文本搜寻单个模式串的所有匹配或在文本中搜寻多个模式串的匹配。

若要在一段文本中找出单个模式串的一个匹配，此算法具有线性时间的平均复杂度，其运行时间与待匹配文本和模式串的长度成线性关系。虽然平均情况下，此算法表现优异，但最坏情况下，其复杂度为文本长与模式串长的乘积。当在文本中搜寻多个匹配时，其具有线性时间的平均复杂度（与文本串长、模式串长、模式串所有匹配总长三者的和成线性关系）。相对地，另一种用于找出模式串所有匹配的AC自动机算法的最坏情况复杂度与文本串长、模式串长、模式串所有匹配总数（而非总长）成正比。

此算法的一个实际应用为内容相似度检验（英语：content similarity detection）（如论文查重）。在给定原材料与待查重论文的情况下，此算法可以迅速在论文中搜寻原材料中的句子，同时忽略诸如大小写与标点等细节。由于原材料中的字符串过多，故单字符串搜索算法在此处不适用。

简介

下文中设所有模式串长为m，所有文本串长为n。

要在给定文本中搜索模式串，最简单的朴素算法的做法是将模式串与文本中所有位置进行比对。每次比对所需时间为 ，所有可能的位置数为n，故该算法的最坏复杂度为 。一种典型的优化为：当匹配到文本串的某一位置时，若文本串与模式串在任一位置失配，则直接移动到下一个位置继续尝试匹配。这种优化省去了在已经确定当前位置文本串失配时剩余的无用匹配尝试，但在特定情况下它无法确保任何加速。相对地，

一些字符串匹配算法会利用失配时的信息来降低最坏情况复杂度：每次失配时，文本的当前位置会使得两串中至少存在一处不同，这使得上述算法可以跳过已经确定无法成功匹配的位置。这类算法中KMP算法与Boyer-Moore字符串搜索算法较为常见。本条目所述的算法的加速方式则不同：此算法使用散列函数以快速对每个位置能否匹配作大致的检测，此后只对通过了检测的位置进行匹配尝试。

字符串搜索中所用散列函数（或哈希函数）会对每一个字符串进行处理与计算，生成的数值称为散列值（或哈希值）：例如，在以某种方式定义了散列函数hash()后，我们可能有hash("rabin")=2020，hash("karp")=2019（仅供示意）。如果两个字符串相等，那么它们的散列值相等。对于一些良好的散列函数而言，通常情况下这句话反之依然成立：不同的字符串在大多数情况下拥有不同的散列值。此算法会在文本串的每一个位置计算从该位置开始的、与模式串等长的子串的散列值；如果该值与模式串的散列值相等，则算法会在该位置进行模式串的遍历比较。

为使此算法正常并且良好地工作，散列函数应从不易产生伪阳性错误的函数中随机挑选以防止非匹配位置的字符串散列值与模式串相同，从而增加并没有对匹配产生贡献的冗余运算量。另外，所采用的散列函数应当为旋转哈希（特点为新位置的散列值可以通过已有散列值快速计算）以防止重新计算的额外工作。

算法实现

算法实现如下。 

function RabinKarp(string s[1..n], string pattern[1..m])
    hpattern := hash(pattern[1..m]);
    for i from 1 to n-m+1
        hs := hash(s[i..i+m-1])
        if hs = hpattern
            if s[i..i+m-1] = pattern[1..m]
                return i
    return not found

第2/4/6行中每行执行一次时间复杂度均为 ，但第2行只被执行一次，第6行仅在散列值相等时被执行（次数也因此较少）。在被执行了n次的第5行中，由于散列值的比较仅需常数时间，其对复杂度的影响为 。算法时间复杂度的瓶颈在于第四行。

用朴素算法计算散列值时，由于每一个字符都需计算，共需要 的复杂度。由于在每一次循环时均需要计算及比较散列值，采用此方法时算法总复杂度退化为 （与朴素算法无异）。若要提速，每次进行散列值计算时，其复杂度不应超过常数时间。由于每次计算散列值时，已有上一个位置的散列值为基础，倘若能用以在常数时间内计算新位置的散列值，则总时间将急遽减少。因此，我们引入旋转哈希。

旋转哈希是一种专为此操作设计的散列算法。一种便捷但并不优秀的旋转哈希函数采用的计算方法为直接减去串首字符的值并加上串尾字符的值，类似一个滑动窗口操作： 

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

此类函数可以在常数时间内计算模式串移动时的散列值，但如果散列算法并不好，将造成过多的哈希碰撞，从而使第5行与采用其他更优秀的散列函数（如下文）时相比被过多执行。一个良好的散列算法不应产生过多相同的散列值，因其会使比较次数增加（仅在极端情况时，若所有字符串的散列值均相同，其最坏情况复杂度与不加优化时相同，为 。

采用的散列函数

主条目：拉宾指纹

对于拉宾-卡普算法，一种常用的可靠、高效的散列算法为拉宾指纹。在此处叙述的算法并非拉宾指纹，但依然有良好的表现。本算法视字符串中的每一个子串为某进制下的一个数字，通常进制数与字符集大小相同。

例：若子串为"hi"，字符集大小/进制为256，用于取模的质数为101，那么散列值将会以如下方式计算（此处采用字符的ASCII值）：

[(104 × 256 ) % 101 + 105] % 101 = 65

此处'%'表取模或同余之意。例如，10除以3等于3余1，则10%3=1

与一般的进制不同的是，所用进制可以比某一位上的数字大，详见散列函数。使用此类散列函数的最大优势在于可以仅需常数次操作或计算来得到新位置的散列值。例如，当文本串为"abracadabra"、模式串长为3、首个可能的匹配的串为"abr"、进制数为256、用于取模的质数为101时，其散列值以如下方式计算： 

// a的ASCII值为97，b为98，r为114
hash("abr") =  [ ( [ ( [ (97 × 256) % 101 + 98 ] % 101 ) × 256 ] % 101 ) + 114 ] % 101 = 4

若要从上一个串的散列值4计算下一个串"bra"的散列值，只需减去首字母a的散列值（需乘上对应偏移量，即该位置字母在当前串中所乘进制数的幂，本例为97 × 2562），将整个串偏移一位（即乘上进制数）再加上新的末位字母对应散列值（本例为97 × 2560）即可: 

hash("bra") = [ ( 4 - 97 × [(256%101)×256] % 101 ) × 256 + 97 ] % 101 = 30

为防止计算时溢出，此处取结果与2562%101相同的((256%101)*256)%101。实际计算时，一般会先用循环处理出所需的进制数幂以节省时间

此散列值与直接计算时结果相同： 

hash'("bra") =  [ ( [ ( [ (98 × 256) % 101 + 114 ] % 101 ) × 256 ] % 101) + 97 ] % 101 = 30

但当模式串较长时，其能极大地节约时间。

理论上仍有其他能实现便捷计算的散列算法，如取所有字符的ASCII乘积为散列值等。此种散列算法的限制在于数据类型的上限与取模的必要性，参考散列函数。而另一些散列算法，要么耗时较长，要么较容易产生散列冲突（英语：Hash_collision）而因此减慢了算法执行的速度。因此，本节所记散列算法通常被拉宾-卡普算法采用。

多模式搜索

拉宾-卡普算法在单模式搜索方面不如Knuth–Morris–Pratt算法、Boyer-Moore字符串搜索算法和其他较快的单模式字符串搜索算法，因为它的最坏情况行为很慢。然而，它是多模式搜索的首选算法。

为了在文本中找到任何一个大量的，比如说k个固定长度的模式，拉宾-卡普算法的一个简单变体使用布隆过滤器或集合数据结构来检查给定字符串的哈希值是否属于我们要寻找的模式的哈希值集合： 

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

我们假设所有子串都具有固定长度m 。 一种朴素的搜索k个模式的方法是，重复每次花费O(n+m)时间的单模式搜索，总时间为O((n+m)k)。 与之对比，假设哈希表检查工作在O(1)预期时间内，那么上述算法可以在O(n+km)个预期时间内找到所有k个模式。一个确定性的O(n+km)解就是Aho-Corasick算法。

参考资料

  • Karp, Richard M.; Rabin, Michael O. Efficient randomized pattern-matching algorithms. IBM Journal of Research and Development. March 1987, 31 (2): 249–260. doi:10.1147/rd.312.0249. 
  • Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford. The Rabin–Karp algorithm. Introduction to Algorithms 2nd. Cambridge, Massachusetts: MIT Press. 2001-09-01: 911–916 [1990]. ISBN 978-0-262-03293-3. 
  • Candan, K. Selçuk; Sapino, Maria Luisa. Data Management for Multimedia Retrieval. Cambridge University Press. 2010: 205–206. ISBN 978-0-521-88739-7.  (for the Bloom filter extension)

外部链接