Rabin-Karp 演算法簡介

Created: November-22, 2018

Rabin-Karp 演算法是由 Richard M. Karp和 Michael O. Rabin建立的字串搜尋演算法，它使用雜湊來查詢文字中的一組模式字串中的任何一個。

字串的子字串是另一個出現的字串。例如， ver 是 stackoverflow 的子字串。不要與子序列混淆，因為 cover 是同一個字串的子序列。換句話說，字串中連續字母的任何子集都是給定字串的子字串。

在 Rabin-Karp 演算法中，我們將生成我們正在尋找的模式的雜湊，並檢查我們的文字的滾動雜湊是否與模式匹配。如果它不匹配，我們可以保證的是，模式不存在的文字。但是，如果匹配，則模式可以出現在文字中。我們來看一個例子：

假設我們有一個文字： yeminsajid ，我們想知道文字中是否存在模式 nsa 。要計算雜湊和滾動雜湊，我們需要使用素數。這可以是任何素數。讓我們在這個例子中使用 prime = 11 。我們將使用以下公式確定雜湊值：

(1st letter) X (prime) + (2nd letter) X (prime)¹ + (3rd letter) X (prime)² X + ......

我們將表示：

a -> 1    g -> 7    m -> 13   s -> 19   y -> 25
b -> 2    h -> 8    n -> 14   t -> 20   z -> 26
c -> 3    i -> 9    o -> 15   u -> 21
d -> 4    j -> 10   p -> 16   v -> 22
e -> 5    k -> 11   q -> 17   w -> 23
f -> 6    l -> 12   r -> 18   x -> 24

nsa 的雜湊值為：

 14 X 11⁰ + 19 X 11¹ + 1 X 11² = 344

現在我們找到文字的滾動雜湊值。如果滾動雜湊與模式的雜湊值匹配，我們將檢查字串是否匹配。因為我們的模式有 3 個字母，我們將採取 1 日 3 封 YEM 從我們的文字，並計算雜湊值。我們得到：

25 X 11⁰ + 5 X 11¹ + 13 X 11² = 1653

此值與我們的模式的雜湊值不匹配。所以字串在這裡不存在。現在我們需要考慮下一步。計算下一個字串 emi 的雜湊值。我們可以使用我們的公式計算出來。但這將是相當微不足道的，並且會花費更多。相反，我們使用另一種技術。

我們從當前雜湊值中減去 Previous String 的第一個字母的值。在這種情況下， y 。我們得到了，1653 - 25 = 1628。
我們將差異除以我們的素數，這個例子是 11 。我們得到了，1628 / 11 = 148。
我們加上新的字母 X（素數）ᵐ-1 ，其中 m 是模式的長度，商是 i = 9 。我們得到了，148 + 9 X 11² = 1237。

新的雜湊值不等於我們的模式雜湊值。繼續前進，為 ñ 我們得到：

Previous String: emi
First Letter of Previous String: e(5)
New Letter: n(14)
New String: "min"
1237 - 5 = 1232
1232 / 11 = 112
112 + 14 X 11² = 1806

它不匹配。在那之後，對於 s ，我們得到：

Previous String: min
First Letter of Previous String: m(13)
New Letter: s(19)
New String: "ins"
1806 - 13 = 1793
1793 / 11 = 163
163 + 19 X 11² = 2462

它不匹配。接下來，對於 a ，我們得到：

Previous String: ins
First Letter of Previous String: i(9)
New Letter: a(1)
New String: "nsa"
2462 - 9 = 2453
2453 / 11 = 223
223 + 1 X 11² = 344

這是一個匹配！現在我們將模式與當前字串進行比較。由於兩個字串都匹配，因此子字串存在於此字串中。然後我們返回子字串的起始位置。

虛擬碼將是：

雜湊計算：

Procedure Calculate-Hash(String, Prime, x):
hash := 0                                  // Here x denotes the length to be considered
for m from 1 to x                          // to find the hash value
    hash := hash + (Value of String[m])ᵐ⁻¹
end for
Return hash

雜湊重新計算：

Procedure Recalculate-Hash(String, Curr, Prime, Hash):
Hash := Hash - Value of String[Curr]  //here Curr denotes First Letter of Previous String
Hash := Hash / Prime
m := String.length
New := Curr + m - 1
Hash := Hash + (Value of String[New])ᵐ⁻¹
Return Hash

字串匹配：

Procedure String-Match(Text, Pattern, m):
for i from m to Pattern-length + m - 1
    if Text[i] is not equal to Pattern[i]
        Return false
    end if
end for
Return true

拉賓，卡普：

Procedure Rabin-Karp(Text, Pattern, Prime):
m := Pattern.Length
HashValue := Calculate-Hash(Pattern, Prime, m)
CurrValue := Calculate-Hash(Pattern, Prime, m)
for i from 1 to Text.length - m
    if HashValue == CurrValue and String-Match(Text, Pattern, i) is true
        Return i
    end if
    CurrValue := Recalculate-Hash(String, i+1, Prime, CurrValue)
end for
Return -1

如果演算法找不到任何匹配，則只返回 -1 。

該演算法用於檢測抄襲。在給定源材料的情況下，該演算法可以快速在紙張中搜尋來自源材料的句子例項，忽略諸如大小寫和標點符號之類的細節。由於所搜尋的字串豐富，單字串搜尋演算法在這裡是不切實際的。同樣， Knuth-Morris-Pratt 演算法或 Boyer-Moore 字串搜尋演算法是比 Rabin-Karp 更快的單模式字串搜尋演算法。但是，它是多模式搜尋的首選演算法。如果我們想在文字中找到任何大數，比如 k，固定長度模式，我們可以建立一個簡單的 Rabin-Karp 演算法變體。

對於組合長度為 m 的長度為 n 和 p 的模式的文字，其平均和最佳情況執行時間在空間 O(p) 中為 O（n + m ），但其最壞情況時間為 O(nm) 。 **** **** **** ****