拉賓-卡普演算法

在計算機科學中，拉賓-卡普演算法或卡普-拉賓演算法，是一種由理查德·卡普與邁克爾·拉賓於1987年提出的、使用雜湊函式以在文字中搜尋單個模式串的字串搜尋演算法單次匹配。該演算法先使用旋轉雜湊以快速篩出無法與給定串匹配的文字位置，此後對剩餘位置能否成功匹配進行檢驗。此演算法可推廣到用於在文字搜尋單個模式串的所有匹配或在文字中搜尋多個模式串的匹配。若要在一段文字中找出單個模式串的一個匹配，此演算法具有線性時間的平均複雜度，其執行時間與待匹配文字和模式串的長度成線性關係。雖然平均情況下，此演算法表現優異，但最壞情況下，其複雜度為文字長與模式串長的乘積。當在文字中搜尋多個匹配時，其具有線性時間的平均複雜度成正比。此演算法的一個實際應用為。在給定原材料與待查重論文的情況下，此演算法可以迅速在論文中搜尋原材料中的句子，同時忽略諸如大小寫與標點等細節。由於原材料中的字串過多，故單字串搜尋演算法在此處不適用。簡介.下文中設所有模式串長為m，所有文字串長為n。要在給定文字中搜索模式串，最簡單的樸素演算法的做法是將模式串與文字中所有位置進行比對。每次比對所需時間為formula_1，所有可能的位置數為n，故該演算法的最壞複雜度為formula_2。一種典型的最佳化為：當匹配到文字串的某一位置時，若文字串與模式串在任一位置失配，則直接移動到下一個位置繼續嘗試匹配。這種最佳化省去了在已經確定當前位置文字串失配時剩餘的無用匹配嘗試，但在特定情況下它無法確保任何加速。相對地，一些字串匹配演算法會利用失配時的資訊來降低最壞情況複雜度：每次失配時，文字的當前位置會使得兩串中至少存在一處不同，這使得上述演算法可以跳過已經確定無法成功匹配的位置。這類演算法中KMP演算法與Boyer-Moore字串搜尋演算法較為常見。本條目所述的演算法的加速方式則不同：此演算法使用雜湊函式以快速對每個位置能否匹配作大致的檢測，此後只對通過了檢測的位置進行匹配嘗試。字串搜尋中所用雜湊函式。如果兩個字串相等，那麼它們的雜湊值相等。對於一些良好的雜湊函式而言，通常情況下這句話反之依然成立：不同的字串在大多數情況下擁有不同的雜湊值。此演算法會在文字串的每一個位置計算從該位置開始的、與模式串等長的子串的雜湊值；如果該值與模式串的雜湊值相等，則演算法會在該位置進行模式串的遍歷比較。為使此演算法正常並且良好地工作，雜湊函式應從不易產生偽陽性錯誤的函式中隨機挑選以防止非匹配位置的字串雜湊值與模式串相同，從而增加並沒有對匹配產生貢獻的冗餘運算量。另外，所採用的雜湊函式應當為旋轉雜湊以防止重新計算的額外工作。演算法實現.演算法實現如下。function RabinKarp(string s[1..n], string pattern[1..m])hpattern := hash(pattern[1..m]);for i from 1 to n-m+1hs := hash(s[i..i+m-1])if hs = hpatternif s[i..i+m-1] = pattern[1..m]return ireturn not found第2/4/6行中每行執行一次時間複雜度均為formula_1，但第2行只被執行一次，第6行僅在雜湊值相等時被執行。在被執行了n次的第5行中，由於雜湊值的比較僅需常數時間，其對複雜度的影響為formula_4。演算法時間複雜度的瓶頸在於第四行。用樸素演算法計算雜湊值時，由於每一個字元都需計算，共需要formula_1的複雜度。由於在每一次迴圈時均需要計算及比較雜湊值，採用此方法時演算法總複雜度退化為formula_2。若要提速，每次進行雜湊值計算時，其複雜度不應超過常數時間。由於每次計算雜湊值時，已有上一個位置的雜湊值為基礎，倘若能用以在常數時間內計算新位置的雜湊值，則總時間將急遽減少。因此，我們引入旋轉雜湊。旋轉雜湊是一種專為此操作設計的雜湊演算法。一種便捷但並不優秀的旋轉雜湊函式採用的計算方法為直接減去串首字元的值並加上串尾字元的值，類似一個滑動視窗操作：此類函式可以在常數時間內計算模式串移動時的雜湊值，但如果雜湊演算法並不好，將造成過多的雜湊碰撞，從而使第5行與採用其他更優秀的雜湊函式時相比被過多執行。一個良好的雜湊演算法不應產生過多相同的雜湊值，因其會使比較次數增加（僅在極端情況時，若所有字串的雜湊值均相同，其最壞情況複雜度與不加最佳化時相同，為formula_2。採用的雜湊函式.對於拉賓-卡普演算法，一種常用的可靠、高效的雜湊演算法為拉賓指紋。在此處敘述的演算法並非拉賓指紋，但依然有良好的表現。本演算法視字串中的每一個子串為某進位制下的一個數字，通常進位制數與字符集大小相同。例：若子串為"hi"，字符集大小/進製為256，用於取模的質數為101，那麼雜湊值將會以如下方式計算：[(104 × 256 ) % 101 + 105] % 101 = 65此處'%'表取模或同餘之意。例如，10除以3等於3餘1，則10%3=1與一般的進位制不同的是，所用進位制可以比某一位上的數字大，詳見雜湊函式。使用此類雜湊函式的最大優勢在於可以僅需常數次操作或計算來得到新位置的雜湊值。例如，當文字串為"abracadabra"、模式串長為3、首個可能的匹配的串為"abr"、進位制數為256、用於取模的質數為101時，其雜湊值以如下方式計算：// a的ASCII值為97，b為98，r為114hash("abr") = [ ( [ ( [ (97 × 256) % 101 + 98 ] % 101 ) × 256 ] % 101 ) + 114 ] % 101 = 4若要從上一個串的雜湊值4計算下一個串"bra"的雜湊值，只需減去首字母a的雜湊值即可: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乘積為雜湊值等。此種雜湊演算法的限制在於資料型別的上限與取模的必要性，參考雜湊函式。而另一些雜湊演算法，要麼耗時較長，要麼較容易產生而因此減慢了演算法執行的速度。因此，本節所記雜湊演算法通常被拉賓-卡普演算法採用。多模式搜尋.拉賓-卡普演算法在單模式搜尋方面不如Knuth–Morris–Pratt演算法、Boyer-Moore字串搜尋演算法和其他較快的單模式字串搜尋演算法，因為它的最壞情況行為很慢。然而，它是多模式搜尋的首選演算法。為了在文字中找到任何一個大量的，比如說"k"個固定長度的模式，拉賓-卡普演算法的一個簡單變體使用布隆過濾器或集合資料結構來檢查給定字串的雜湊值是否屬於我們要尋找的模式的雜湊值集合：function RabinKarpSet(string s[1..n], set of string subs, m):set hsubs := emptySetforeach sub in subsinsert hash(sub[1..m]) into hsubshs := hash(s[1..m])for i from 1 to n-m+1if hs ∈ hsubs and s[i..i+m-1] ∈ subsreturn ihs := 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演算法。