Понимание того, как скользящий хэш работает с модулем в алгоритме Рабина Карпа

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

Рассмотрим последовательность 5 цифр в числе 123456.

Первый фрагмент 12345. Сохраняю значение, в следующем окне приходит 6 и уходит 1.

Таким образом, новый хэш будет (12345-1*10^4)*10 + 6 = 23456. Это довольно интуитивно понятно.

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

Таким образом, 12345 уменьшится до 23. Как же тогда из этого я получу скользящий хэш для следующего окна, 23456?


string algorithm hash rabin-karp
person SexyBeast    schedule 23.04.2016    source источник

Ответы (2)


arrow_upward
6
arrow_downward

Вы вычисляете его так же, как вычисляете 23456, но всегда по модулю 101.

(((23 - (10^4 mod 101))*10) mod 101 + 6) mod 101 = 24.

это значение, которое вы хотите, потому что 23456 mod 101 = 24.

person dejvuth    schedule 23.04.2016
comment
Спасибо. Это было легко понять! - person SexyBeast; 23.04.2016
comment
Вы пропустили первый? Разве не должно быть (((23 - (1*10^4 по модулю 101))*10) по модулю 101 + 6) по модулю 101 = 24 ? - person Alexandru Antochi; 20.06.2020

arrow_upward
2
arrow_downward

Ответ @dejvuth правильный - я бы добавил это специально при выполнении рабин-карпа, так это то, что иногда вы можете получить значение модуля -ve - в этом случае лучше взять +ve эквивалент этого значения модуля - так что проверить, был ли тот же модуль замечен раньше, проще.

Например: с этим шаблоном "abcdabc" и хеш-функцией: hash(i) = (49*S[i]+7*S[i+1]+1*S[i+2])%1123

Результат:

"abc" -> 1046
"bcd" -> 1103
"cda" -> 33
"dab" -> 62
"abc" -> -77

второе появление результатов "abc" - это -77, что по модулю эквивалентно 1046, поскольку (-77 + 1123 = 1046)

PS: в настоящее время у меня недостаточно репутации, чтобы добавить это в качестве комментария.

person Ravi    schedule 22.07.2020
comment
Я не могу отблагодарить вас за этот ответ. Я еще не знаю модульной арифметики, поэтому потратил 2 часа на то, чтобы в основном исправить то, что не было сломано. - person Poseidon Broger; 07.01.2021