Rabin-Karp字符串搜索算法中使用的滾動哈希函數是否有任何工作實現？

我正在尋找使用滾動散列函數，所以我可以使用非常大的字符串的n元組哈希值。Rabin-Karp字符串搜索算法中使用的滾動哈希函數是否有任何工作實現？

例如：

「計算器」，分成5克將是：

「堆」，「tacko」，「ackov」，「ckove」，「kover」，「overf」，「verfl」，「erflo」，「rflow」

這是理想的滾動哈希函數，因爲後我計算第一n-gram中的散列，以下物質是相對便宜的計算，因爲我只需刪除第一個散列的第一個字母並添加第二個散列的新的最後一個字母。

我知道一般生成該散列函數爲：

H = c^一個^{的k - 1} + C 一個^{的k - 2} + C 一個^{k - 3} + ... + c _k a 其中a是常數，c1，...，ck是輸入字符。

如果您點擊Rabin-Karp string search algorithm上的此鏈接，它會聲明「a」通常是一個大的素數。

我想我的哈希存儲在32位整數，所以一個素數應該有多大「a」，這樣我纔不會溢出我的整數？

是否存在這個散列函數的現有實現，我已經可以使用它了？

這裏是我創建了一個實現：

public class hash2 
{ 

    public int prime = 101; 

    public int hash(String text) 
    { 
     int hash = 0; 

     for(int i = 0; i < text.length(); i++) 
     { 
      char c = text.charAt(i); 
      hash += c * (int) (Math.pow(prime, text.length() - 1 - i)); 
     } 

     return hash; 
    } 

    public int rollHash(int previousHash, String previousText, String currentText) 
    { 

     char firstChar = previousText.charAt(0); 
     char lastChar = currentText.charAt(currentText.length() - 1); 

     int firstCharHash = firstChar * (int) (Math.pow(prime, previousText.length() - 1)); 
     int hash = (previousHash - firstCharHash) * prime + lastChar; 

     return hash; 
    } 

    public static void main(String[] args) 
    { 
     hash2 hashify = new hash2(); 

     int firstHash = hashify.hash("mydog"); 
     System.out.println(firstHash); 
     System.out.println(hashify.hash("ydogr")); 
     System.out.println(hashify.rollHash(firstHash, "mydog", "ydogr")); 
    } 

}

我用101作爲我的素數。如果我的哈希溢出會影響它嗎？我認爲這是可取的，但我不確定。

這似乎是正確的方式去做這件事嗎？

來源

2010-02-22 c14ppy

爲什麼這個應用程序的主要是從「正常」的字符串哈希碼一代有什麼不同？ – CPerkins 2010-02-22 21:49:17

該算法非常簡單，從僞代碼很容易實現。你試過自己編碼了嗎？ – MAK 2010-02-23 20:28:37

按照我的理解它是一個功能最大限度地減少：

2^31 - sum (maxchar) * A^kx

其中maxchar = 62（用於A-Za-z0-9）。我剛剛通過Excel（OO Calc，精確地）計算出它，並且發現它的最大A是76或73，對於素數。

來源

2010-02-22 21:43:42

我記得一個略有不同的實現，它似乎來自sedgewick算法書（它也包含示例代碼 - 試圖查看它）之一。這裏是一個總結調整爲32位整數：

您使用模算術來防止您的整數在每次操作後溢出。

初始設置：

C =文本（「計算器」）
M =長度「的n-gram」
d的=你的字母表的大小（256）
q =一個大素數，使（d + 1）* q不溢出（8355967可能是一個不錯的選擇）
DM = d ^M-1模q

首先計算第一n-gram中的散列值：

h = 0 
for i from 1 to M: 
    h = (h*d + c[i]) mod q

，併爲每個以下的n-gram：

for i from 1 to lenght(c)-M: 
    // first subtract the oldest character 
    h = (h + d*q - c[i]*dM) mod q 

    // then add the next character 
    h = (h*d + c[i+M]) mod q

爲什麼你減去前增加d * Q的原因最古老的字符是因爲由於以前的模運算造成的小值，您可能會遇到負值。包括

錯誤，但我想你應該明白我的意思。嘗試找到sedgewick的算法書中的一個細節，減少錯誤和更好的描述。 :)

來源

2010-02-22 23:44:04 stmax

你是什麼意思由錯誤包括？如果我這樣做，我會陷入「負面價值」嗎？如何預防它？ – 2012-01-15 06:25:11

@ Myth17：我的意思是，你應該用我的（僞）代碼謹慎，因爲它可能包含錯誤/我還沒有廣泛的測試它。要計算 – stmax 2012-01-18 19:44:26

在拉賓-卡普串檢索算法算法中使用應允許下一個散列值的滾動散列爲：** S [I + 1..i + M] = S [i..i + M-1] - s [i] + s [i + m] **。您提供的算法不能用於此目的。 – 2013-04-29 20:12:38

不知道你的目的是什麼在這裏，但如果你想提高性能，使用math.pow將花費你遠遠超過你通過計算滾動散列值保存。

我建議你通過保持簡單和高效的開始，你很可能會發現這是速度不夠快。

來源

2010-02-24 21:14:00

最快的方法來計算權力？ – 2012-01-23 19:14:13

這取決於情況。簡單乘法通常更快。 – 2012-01-23 19:59:31

Rabin-Karp字符串搜索算法中使用的滾動哈希函數是否有任何工作實現？

回答

相關問題