1

我从那个站点找到了一个 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;
}
4

2 回答 2

5

计算

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

大于通常的 32 位宽INT_MAX。int

如果您int的 s 是 32 位宽，则示例从一开始就有溢出，因为h*256*97 = 4521509888 > 2147483647.

于 2013-04-11T10:07:04.790 回答
1

“块长度”是模式的长度。由于您的代码中没有任何模式，因此数字 150 没有意义，除非这是您打算使用的模式的实际长度。

散列值必须取决于被散列的数据及其数量。因此，“abcde”、“abcd”、“abc”的哈希值可能都不同。

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

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

如果哈希匹配，则您可能会匹配两个字符序列，然后您将它们进行比较以查看是否存在真正的匹配。

这是算法的主要思想，这也是它比子字符串搜索的幼稚实现更快的原因。

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

于 2013-04-11T10:06:04.117 回答