Существуют ли какие-либо рабочие реализации скользящей хеш-функции, используемой в алгоритме поиска строк Рабина-Карпа?

Question

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

Например:

"stackoverflow", разбитый на 5 граммов, будет:

"стек", "тако", "акков", "чкове", "kover", "overf", "verfl", "erflo", "rflow"

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

Я знаю, что в общем случае эта хеш-функция генерируется как:

H = c ₁ a ^{k - 1} + c ₂ a ^{k - 2} + c ₃ a ^{k - 3} + ... + c _k a ⁰ , где a - константа, а c1, ..., ck - входные символы.

Если вы перейдете по этой ссылке в алгоритме поиска строки Рабина-Карпа , он скажет, что «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 в качестве прайма. Имеет ли значение, если мои хеши переполнятся? Я думаю, что это желательно, но я не уверен.

Похоже, это правильный путь?

Answer 1

Я помню немного отличную реализацию, которая, кажется, была из одной из книг по алгоритмам Седжвика (она также содержит пример кода - попробуйте поискать его).Вот сводка, скорректированная на 32-битные целые числа:

вы используете арифметику по модулю, чтобы предотвратить переполнение целого числа после каждой операции.

изначально установлено:

• c = текст("stackoverflow")
• M = длина "n-граммов"
• d = размер вашего алфавита (256)
• q = большое простое число, так что (d + 1) * q не переполняется (8355967 может быть хорошим выбором)
• dM = d ^M-1 mod q

сначала вычислитехэш-значение первого n-грамма:

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

и для каждого следующего n-грамма:

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 перед вычитанием самого старого символаэто потому, что вы можете столкнуться с отрицательными значениями из-за небольших значений, вызванных предыдущей операцией по модулю.

ошибок включены, но я думаю, вы должны понять.попытайтесь найти одну из книг алгоритмов Седжвика для деталей, меньше ошибок и лучшего описания.:)

Answer 2

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

Я предлагаю вам начать с простого и эффективного, и вы, скорее всего, найдете это достаточно быстрым.

Answer 3

Как я понимаю, это минимизация функции для:

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

, где maxchar = 62 (для A-Za-z0-9). Я только что вычислил это по Excel (точно OO Calc) :) и максимальное A, которое он нашел, составляет 76 или 73 для простого числа.