Karp Rabin的素數和塊長度

Question

我發現了一個來自that網站的rabin karp代碼，並更改爲嘗試。更改的代碼如下。你可以在hashtable.txt中看到單詞和它們的散列值。下面的例子hashtable.txt似乎是正確的。

但是，當我將M（塊長度）更改爲150時，我得到錯誤的結果。例如在hashtable.txt中，第一行和第六行必須相同，但它們的散列值是不同的。

或者當我將q（素數）更改爲683303時，它也會得到錯誤的結果。

rabin karp算法中素數與塊長度之間的關係是什麼？錯誤結果的原因是什麼？

#include<stdio.h> 
#include<string.h> 
#include <fstream> 
#include <iostream> 
// d is the number of characters in input alphabet 
#define d 256 
int M = 80; 
/* 
txt -> text 
q -> A prime number 
*/ 
using namespace std; 

void writeTable(char *txt, int q) 
{ 
ofstream myfile; 
myfile.open ("hashtable.txt"); 
int N = strlen(txt); 
int i, j; 
int t = 0; // hash value for txt 
int h = 1; 

// The value of h would be "pow(d, M-1)%q" 
for (i = 0; i < M-1; i++) 
    h = (h*d)%q; 

// Calculate the hash value of pattern and first window of text 
for (i = 0; i < M; i++) 
{ 
    t = (d*t + txt[i])%q; 
} 

// Slide the pattern over text one by one 
for (i = 0; i <= N - M; i++) 
{ 
    myfile << t <<" "; 
    for (long z = i; z < M+i; z++){myfile<<txt[z];}myfile<<"\n"; 

    // Calulate hash value for next window of text: Remove leading digit, 
    // add trailing digit   
    if (i < N-M) 
    { 
     t = (d*(t - txt[i]*h) + txt[i+M])%q; 

     // We might get negative value of t, converting it to positive 
     if(t < 0) 
      t = (t + q); 
    } 
} 

myfile.close(); 
} 

/* Driver program to test above function */ 
int main() 
{ 
    char *txt ="abcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcde"; 

int q = 683303; // A prime number 

writeTable(txt, q); 

printf("finish"); 
getchar(); 
return 0; 
} 

Answer 1

計算

t = (d*(t - txt[i]*h) + txt[i+M])%q; 

可能溢出。 txt[i]的最大值是d-1，並且h可以大到q-1。所以如果(q-1)*(d-1)*d > INT_MAX，就有可能發生整數溢出。這限制了可安全選擇的素數的大小爲INT_MAX/(d*(d-1)) + 1。

如果q比越大，造成對M容許值的限制，即M必須是這樣的

h <= INT_MAX/(d*(d-1)) 

安全地防止溢出。

隨着q = 683303和M = 80，你會得到h = 182084，並

h*d*(d-1) = 182084 * 256 * 255 = 11886443520 

大於INT_MAX如果int爲32個位寬，因爲它通常是。

如果您的int s是32位寬，則您從示例開始就溢出，因爲h*256*97 = 4521509888 > 2147483647。

Answer 2

「塊長度」是模式的長度。由於您的代碼中沒有任何模式，因此數字150沒有意義，除非這是您打算使用的模式的實際長度。

散列的值必須取決於被散列的數據和數量。所以，「abcde」，「abcd」，「abc」的散列可能會完全不同。

在此算法中，通過首先比較兩者的哈希值，避免將模式與文本的同長部分進行不必要的比較。

如果哈希值不同，您知道兩個字符序列是不同的，並且沒有匹配，所以您可以移動到文本中的下一個位置並重復該過程。

如果哈希匹配，你有兩個字符序列的潛在匹配，然後你比較它們，看看是否有真正的匹配。

這是算法的主要思想，這是什麼使它比子字符串搜索的天真實現更快。

在計算哈希值時用質數除的目的是爲了獲得散列值更均勻的分佈。如果你選擇一個非常大的素數，它不會有太多的影響。如果選擇一個非常小的素數，則可以減少散列值的總數，並增加散列匹配的機率，從而增加不必要的子串比較的機率。