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”的散列可能会完全不同。

在此算法中，通过首先比较两者的哈希值，避免将模式与文本的同长部分进行不必要的比较。

如果哈希值不同，您知道两个字符序列是不同的，并且没有匹配，所以您可以移动到文本中的下一个位置并重复该过程。

如果哈希匹配，你有两个字符序列的潜在匹配，然后你比较它们，看看是否有真正的匹配。

这是算法的主要思想，这是什么使它比子字符串搜索的天真实现更快。

在计算哈希值时用质数除的目的是为了获得散列值更均匀的分布。如果你选择一个非常大的素数，它不会有太多的影响。如果选择一个非常小的素数，则可以减少散列值的总数，并增加散列匹配的几率，从而增加不必要的子串比较的几率。