拉賓-卡普算法

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

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

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

簡介

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

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

一些字符串匹配算法會利用失配時的信息來降低最壞情況複雜度：每次失配時，文本的當前位置會使得兩串中至少存在一處不同，這使得上述算法可以跳過已經確定無法成功匹配的位置。這類算法中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行中每行執行一次時間複雜度均為 ${\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 × 256) % 101 + 98 ] % 101 ) × 256 ] % 101 ) + 114 ] % 101 = 4

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

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

_{為防止計算時溢出，此處取結果與256²%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)

外部連結

Rabin–Karp Algorithm/Rolling Hash (PDF). MIT 6.006: Introduction to Algorithms 2011- Lecture Notes. MIT. [2020-04-24]. （原始內容存檔 (PDF)於2013-08-16）.