Нужна помощь в понимании вычисления Rolling Hash в постоянное время для внедрения Рабина-Карпа - PullRequest
Новая
       37

Нужна помощь в понимании вычисления Rolling Hash в постоянное время для внедрения Рабина-Карпа

10 голосов
/ 24 мая 2011

Я пытался реализовать алгоритм Рабина-Карпа в Java. Мне трудно вычислить значение скользящего хэша в постоянное время. Я нашел одну реализацию в http://algs4.cs.princeton.edu/53substring/RabinKarp.java.html. Тем не менее я не мог понять, как работают эти две строки. 

txtHash = (txtHash + Q - RM*txt.charAt(i-M) % Q) % Q;
txtHash = (txtHash*R + txt.charAt(i)) % Q;

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

Ответы [ 2 ]

19 голосов
/ 06 мая 2013

Сначала вам нужно понять, как вычисляется хеш.

Давайте рассмотрим простой случай из 10 базовых строк.Как бы вы гарантировали, что хеш-код строки уникален?База 10 - это то, что мы используем для представления чисел, и у нас нет коллизий !!

"523" = 5 * 10 ^ 2 + 2 * 10 ^ 1 + 3 * 10 ^ 0 =523

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

Учитывая хеш «523», если вы хотите вычислить хеш «238», т. Е. Выдвинув крайнюю левую цифру 5 и введя новую цифру 8 справа, вы должны будете сделатьследующее:

1) убрать эффект 5 из хэша: hash = hash - 5 * 10 ^ 2 (523-500 = 23)

2) настроитьхэш оставшихся символов путем смещения на 1, хэш = хэш * 10

3) добавляет хэш нового символа: хэш = хэш + 8 (230 + 8 = 238, что, как мы и ожидали, является базовой10 хешей "238")

Теперь давайте расширим это на все символы ascii.Это подводит нас к основному 256 миру.Поэтому хэш той же строки «523» теперь равен

= 5 * 256 ^ 2 + 2 * 256 ^ 1 + 3 * 256 ^ 0 = 327680 + 512 + 3 = 328195.

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

Как мы можем решить это?Обычно это решается путем работы с модулем большого простого числа.Недостаток этого метода заключается в том, что теперь мы также получим ложные срабатывания, что является небольшой ценой, если перевести время выполнения вашего алгоритма из квадратичного в линейное!

Сложное уравнение, которое вы цитировали, не что иное, какописанные выше шаги 1-3 с модулем математики.Два свойства модуля, использованные выше: ->

a) (a * b)% p = ((a% p) * (b% p))% p

b) a% p = (a + p)% p

Давайте вернемся к шагам 1-3, указанным выше ->

1) (расширен с использованием свойства a)хэш = хэш - ((5% p) * (10 ^ 2% p)% p) ​​

против.то, что вы цитировали

txtHash = (txtHash + Q - RM * txt.charAt (iM)% Q)% Q;

ВотВот как они связаны!

  • RM = 10 ^ 3% p
  • txt.charAt (iM)% Q = 5% p
  • Дополнительный + Q, который вы видите, просто для того, чтобы гарантировать, что хэш не является отрицательным.См. Свойство b выше.

2 & 3) hash = hash * 10 + 8, против txtHash = (txtHash * R + txt.charAt (i))% Q;То же самое, но с модификацией окончательного результата хэша!

Если присмотреться к свойствам a & b более внимательно, это поможет вам разобраться!

6 голосов
/ 24 мая 2011

Это «скользящий» аспект хэша.Он исключает вклад самого старого символа (txt.charAt(i-M)) и включает вклад самого нового символа (txt.charAt(i)).

Хеш-функция определяется как: 

            M-1
hash[i] = ( SUM { input[i-j] * R^j } ) % Q
            j=0

(где я использую ^ для обозначения "степени".)

Но это может быть записано как эффективная рекурсивная реализация, как: 

hash[i] = (txtHash*R - input[i-M]*(R^M) + input[i]) % Q

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

Так, например, + Q в первом выражении не имеет математического эффекта, но гарантирует, чторезультат суммы всегда положительный (если он становится отрицательным, % Q не дает желаемого эффекта).Он также разбивает расчеты на этапы, предположительно для предотвращения переполнения чисел.

...