Простое число и длина блока в Карп Рабин

Question

Я нашел код Рабина Карпа с этого сайта и решил попробовать. Измененный код ниже. Вы можете увидеть слова и их значения хеша в hashtable.txt. для примера ниже hashtable.txt кажется правильным.

Но когда я изменил M (длина блока) на 150, я получаю неправильные результаты. Например, в hashtable.txt первая и шестая строки должны быть одинаковыми, но их значения хеша различны.

Или когда я изменил q (простое число) на 683303, это тоже дает неверные результаты.

Какова связь между простым числом и длиной блока в алгоритме Рабина Карпа, и какова причина неправильных результатов?

#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 бита, как обычно.

Если твой ints имеют ширину 32 бита, у вас есть переполнение для примера с самого начала, потому что h*256*97 = 4521509888 > 2147483647,

Answer 2

"Длина блока" - это длина шаблона. Поскольку в вашем коде нет шаблона, число 150 не имеет смысла, если только это не фактическая длина шаблона, который вы намереваетесь использовать.

Значения хэшей должны зависеть от хэшируемых данных и их объема. Таким образом, хэши "abcde", "abcd", "abc", вероятно, будут разными.

В этом алгоритме вы избегаете ненужного сравнения шаблона с частью текста одинаковой длины, сначала сравнивая хеши обоих.

Если хэши разные, вы знаете, что две последовательности символов различны и совпадений нет, поэтому вы можете перейти к следующей позиции в тексте и повторить процедуру.

Если хэши совпадают, у вас есть потенциальное совпадение двух последовательностей символов, а затем вы сравниваете их, чтобы увидеть, есть ли реальное совпадение.

Это основная идея алгоритма, и именно это делает его быстрее, чем наивные реализации поиска по подстроке.

Цель деления на простое число при вычислении хешей состоит в том, чтобы попытаться получить более равномерное распределение хеш-значений. Если вы выберете очень большое простое число, оно не будет иметь большого эффекта. Если вы выберете очень маленькое простое число, вы уменьшите общее число значений хеш-функции и увеличите шансы совпадений хеш-значений и, следовательно, шансы ненужного сравнения подстрок.