拉賓-卡普演算法

在電腦科學中，拉賓-卡普演算法（Rabin–Karp algorithm）或卡普-拉賓演算法（Karp–Rabin algorithm），是一種由理察·卡普與麥可·拉賓於1987年提出的、使用散列函數以在文本中搜尋單個模式串的字串搜索算法單次匹配。該演算法先使用旋轉哈希以快速篩出無法與給定串匹配的文本位置，此後對剩餘位置能否成功匹配進行檢驗。此演算法可推廣到用於在文本搜尋單個模式串的所有匹配或在文本中搜尋多個模式串的匹配。

若要在一段文本中找出單個模式串的一個匹配，此演算法具有線性時間的平均複雜度，其運行時間與待匹配文本和模式串的長度成線性關係。雖然平均情況下，此演算法表現優異，但最壞情況下，其複雜度為文本長與模式串長的乘積。當在文本中搜尋多個匹配時，其具有線性時間的平均複雜度（與文本串長、模式串長、模式串所有匹配總長三者的和成線性關係）。相對地，另一種用於找出模式串所有匹配的AC自動機演算法的最壞情況複雜度與文本串長、模式串長、模式串所有匹配總數（而非總長）成正比。

此演算法的一個實際應用為內容相似度檢驗（如論文查重）。在給定原材料與待查重論文的情況下，此演算法可以迅速在論文中搜尋原材料中的句子，同時忽略諸如大小寫與標點等細節。由於原材料中的字串過多，故單字串搜索算法在此處不適用。

## 簡介

下文中設所有模式串長為m，所有文本串長為n。

要在給定文本中搜索模式串，最簡單的樸素演算法的做法是將模式串與文本中所有位置進行比對。每次比對所需時間為$\mathcal{O}(m)$，所有可能的位置數為n，故該演算法的最壞複雜度為$\mathcal{O}(mn)$。一種典型的優化為：當匹配到文本串的某一位置時，若文本串與模式串在任一位置失配，則直接移動到下一個位置繼續嘗試匹配。這種優化省去了在已經確定當前位置文本串失配時剩餘的無用匹配嘗試，但在特定情況下它無法確保任何加速。相對地。

一些字串匹配算法會利用失配時的資訊來降低最壞情況複雜度：每次失配時，文本的當前位置會使得兩串中至少存在一處不同，這使得上述演算法可以跳過已經確定無法成功匹配的位置。這類演算法中KMP演算法與Boyer-Moore字串搜索算法較為常見。本條目所述的演算法的加速方式則不同：此演算法使用散列函數以快速對每個位置能否匹配作大致的檢測，此後只對通過了檢測的位置進行匹配嘗試。

字串搜索中所用散列函數（或哈希函數）會對每一個字串進行處理與計算，生成的數值稱為散列值（或哈希值）：例如，在以某種方式定義了散列函數hash後，我們可能有hash("rabin")=2020，hash("karp")=2019（僅供示意）。如果兩個字串相等，那麼它們的散列值相等。對於一些良好的散列函數而言，通常情況下這句話反之依然成立：不同的字串在大多數情況下擁有不同的散列值。此算法會在文本串的每一個位置計算從該位置開始的、與模式串等長的子串的散列值；如果該值與模式串的散列值相等，則算法會在該位置進行模式串的遍歷比較。

為使此算法正常並且良好地工作，散列函數應從不易產生偽陽性錯誤的函數中隨機挑選以防止非匹配位置的字串散列值與模式串相同，從而增加並沒有對匹配產生貢獻的冗餘運算量。另外，所採用的散列函數應當為旋轉哈希（特點為新位置的散列值可以通過已有散列值快速計算）以防止重新計算的額外工作。

## 演算法實現

演算法實現如下。

```php
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行中每行執行一次時間複雜度均為$\mathcal{O}(m)$，但第2行只被執行一次，第6行僅在散列值相等時被執行（次數也因此較少）。在被執行了n次的第5行中，由於散列值的比較僅需常數時間，其對複雜度的影響為$\mathcal{O}(n)$。演算法時間複雜度的瓶頸在於第四行。

用樸素演算法計算散列值時，由於每一個字符都需計算，共需要$\mathcal{O}(m)$的複雜度。由於在每一次循環時均需要計算及比較散列值，採用此方法時演算法總複雜度退化為$\mathcal{O}(mn)$（與樸素演算法無異）。若要提速，每次進行散列值計算時，其複雜度不應超過常數時間。由於每次計算散列值時，已有上一個位置的散列值為基礎，倘若能用以在常數時間內計算新位置的散列值，則總時間將急遽減少。因此，我們引入旋轉哈希。

旋轉哈希是一種專為此操作設計的散列演算法。一種便捷但並不優秀的旋轉哈希函數採用的計算方法為直接減去串首字符的值並加上串尾字符的值，類似一個滑動窗口操作：

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

此類函數可以在常數時間內計算模式串移動時的散列值，但如果散列演算法並不好，將造成過多的哈希碰撞，從而使第5行與採用其他更優秀的散列函數（如下文）時相比被過多執行。一個良好的散列演算法不應產生過多相同的散列值，因其會使比較次數增加（僅在極端情況時，若所有字串的散列值均相同，其最壞情況複雜度與不加優化時相同，為$\mathcal{O}(mn)$。

## 採用的散列函數

對於拉賓-卡普演算法，一種常用的可靠、高效的散列演算法為拉賓指紋。在此處敘述的演算法並非拉賓指紋，但依然有良好的表現。本演算法視字串中的每一個子串為某進位下的一個數字，通常進位數與字符集大小相同。

例：若子串為"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 &times; 256) % 101 + 98 ] % 101 ) &times; 256 ] % 101 ) + 114 ] % 101 = 4
```

若要從上一個串的散列值4計算下一個串"bra"的散列值，只需減去首字母a的散列值（需乘上對應偏移量，即該位置字母在當前串中所乘進位數的冪，本例為97 × 2562），將整個串偏移一位（即乘上進位數）再加上新的末位字母對應散列值（本例為97 × 2560）即可:

```
hash("bra") = [ ( 4 - 97 &times; [(256%101)&times;256] % 101 ) &times; 256 + 97 ] % 101 = 30
```

為防止計算時溢出，此處取結果與2562%101相同的((256%101)*256)%101。實際計算時，一般會先用循環處理出所需的進位數冪以節省時間

此散列值與直接計算時結果相同：

```
hash'("bra") =  [ ( [ ( [ (98 &times; 256) % 101 + 114 ] % 101 ) &times; 256 ] % 101) + 97 ] % 101 = 30
```

但當模式串較長時，其能極大地節約時間。

理論上仍有其他能實現便捷計算的散列演算法，如取所有字符的ASCII乘積為散列值等。此種散列演算法的限制在於數據類型的上限與取模的必要性，參考散列函數。而另一些散列演算法，要麼耗時較長，要麼較容易產生散列衝突而因此減慢了演算法執行的速度。因此，本節所記散列演算法通常被拉賓-卡普演算法採用。

## 多模式搜索

拉賓-卡普演算法在單模式搜索方面不如Knuth–Morris–Pratt演算法、Boyer-Moore字串搜索算法和其他較快的單模式字串搜索算法，因為它的最壞情況行為很慢。然而，它是多模式搜索的首選演算法。

為了在文本中找到任何一個大量的，比如說k個固定長度的模式，拉賓-卡普演算法的一個簡單變體使用布隆過濾器或集合數據結構來檢查給定字串的哈希值是否屬於我們要尋找的模式的哈希值集合：

```php
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演算法。

## 參考資料

- (for the Bloom filter extension)