拉賓-卡普演算法

在電腦科學中，拉賓-卡普演算法（英語：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）.