Блог пользователя KAP

Автор KAP, история, 5 лет назад, По-русски

При решении задач на хеширование вам очень частно бывает надо уметь за $$$O(1)$$$ вычислять хеш любой подстроки заданной строки. Стандартный подход к таким задачам — давайте посчитаем хеши всех префиксов, а дальше будем с этим что-то делать...

(Это кросс-пост поста из моего блога.)

...Итак, стандартный подход устроен следующим образом. Начнем немного с начала. Определим хеш строки (хеш-функцию) так:

$$$h(s) = s_0 + s_1 \cdot p + s_2 \cdot p^2 + \ldots + s_{n-1} \cdot p^{n-1}.$$$

(Все вычисления здесь и ниже подразумеваются по некоторому модулю $$$M$$$.)

Посчитаем хеши всех префиксов:

$$$ H[i] = h(s[0..i]) = s_0 + s_1 \cdot p + \ldots + s_i \cdot p^i $$$

Массив $$$H[i]$$$ можно насчитать за $$$O(n)$$$ очевидным образом ($$$H[i] = H[i-1] + s_i \cdot p^i$$$, массив степеней $$$p$$$ можно насчитать заранее, будет полезно и в дальнейшем).

Хорошо. Но нам надо знать хеш произвольной подстроки, т.е. $$$h(s[i..j])$$$. Очевидно, чтобы его вычислить, нам понадобятся значения $$$H[i-1]$$$ и $$$H[j]$$$. (Особый случай $$$i=0$$$ мы рассматривать не будем, он простой.) Явно напрашивается записать

$$$H[j] - H[i-1] = s_i \cdot p^i + \ldots + s_j \cdot p^j = h(s[i..j]) \cdot p^i,$$$

но вот проблема — то, что получилось, это не настоящее значение хеш-функции для подстроки $$$s[i..j]$$$, а величина, в $$$p^i$$$ раз больше. В результате использовать полученное число просто так не получится.

* * *

Есть два стандартных способа решить эту проблему. Первый — хорошо, давайте разделим полученное выражение на $$$p^i$$$. Но у нас все вычисления — по модулю $$$M$$$, делить в арифметике по модулю возможно не всегда, и в любом случае не очень просто. В простейшем случае, когда $$$M$$$ простое, и $$$p$$$ (естественно) не делится на $$$M$$$, деление возможно и даже не очень сложно (по малой теореме Ферма надо просто умножить на $$$(p')^i$$$, где $$$p' = p^{M-2}$$$; можно заранее вычислить $$$p'$$$ и все его степени). Но лишний код писать все равно не охота.

Второй способ — хорошо, давайте поймем, что в конечном счете нам само значение $$$h(s[i..j])$$$ не нужно. Как правило, нам надо сравнивать хеши двух подстрок, пусть $$$s[i..j]$$$ и $$$s[i'..j']$$$. Мы можем вычислить значения $$$X=h(s[i..j]) \cdot p^i$$$ и $$$Y = h(s[i'..j']) \cdot p^{i'}$$$. Напрямую их сравнивать бессмысленно, но мы можем домножить их на подходящие степени, т.е. сравнить $$$X\cdot p^{i'}$$$ и $$$Y\cdot p^i$$$. Если эти два числа равны, то хеши соответствующих подстрок тоже равны.

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

Проблема еще и в том, что вам приходится про это помнить и учитывать это в основной программе. Вы бы, возможно, хотели бы написать функцию hash(i, j), которая вам вернет настоящий хеш подстроки $$$s[i,j]$$$ (или написать class StringWithHash с соответствущим методом), и дальше в основном коде не думать про то, что хеш не той системы. Но нет, так не получится...

* * *

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

А именно, посчитаем

$$$H[i] = h(s[i..n-1]) = s_i + s_{i+1} \cdot p + s_{i+2} \cdot p^2 + \ldots$$$

Вычислить такой массив за $$$O(n)$$$ тоже очень легко (просто $$$H[i] = H[i+1] \cdot p + s_i$$$, эдакий аналог схемы Горнера, даже проще чем раньше — не нужно вычислять $$$p^i$$$).

И теперь внимание фокус:

$$$h(s[i..j]) = H[i] - H[j+1] \cdot p^{j-i+1}.$$$

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

Заодно получили бонусом, что $$$i=0$$$ — это не особый случай. Особый случай теперь $$$j=n-1$$$, но он обходится легко — делаете $$$H[n] = 0$$$ и не надо писать никаких if'ов.

* * *

На самом деле, можно полностью симметрично отразить ситуацию. Выше мы определяли хеш так, что степени $$$p$$$ в формуле возрастали слева направо — как будто самый младший разряд «числа» — это его самая левая цифра.

Можно определить хеш строки наоборот:

$$$h(s) = s_0 \cdot p^{n-1} + s_1 \cdot p^{n-2} + \ldots + s_{n-1}.$$$

Тогда можно посчитать хеши префиксов: $$$H[i] = h(s[0..i])$$$ и аналогично можно вычислять честный хеш любой подстроки. (Правда, $$$i=0$$$ опять будет особым случаем, но это на самом деле ортогональный вопрос.)

* * *

Выше везде я полагал, что запись $$$s[i..j]$$$ включает как символ $$$i$$$, так и символ $$$j$$$. Можно рассматривать всё, как говорят, на полуинтервалах — символ $$$i$$$ включительно, символ $$$j$$$ невключительно (аналогично тому, как в питоне устроены срезы). Тогда написание хеширования еще несколько упрощается (например, $$$i=0$$$ не будет особым случаем ни при каком подходе). Но это тоже ортогональный вопрос.

* * *

Так что мораль: пишите хеширование без домножения и без деления.

  • Проголосовать: нравится
  • +13
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Удивительно, но такая простая идея относительно малоизвестна.

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

Особый случай теперь j=n−1, но он обходится легко — делаете H[n]=0 и не надо писать никаких if'ов.

Ну случай $$$i=0$$$ в исходном варианте тоже обходился легко -- посчитать в $$$1$$$-индексации и добавить $$$h[0]=0$$$.

Напрямую их сравнивать бессмысленно, но мы можем домножить их на подходящие степени, т.е. сравнить X⋅pi′ и Y⋅pi. Если эти два числа равны, то хеши соответствующих подстрок тоже равны.

Можно в универсальном виде. То есть, сравнить $$$X\cdot p^{n-i}$$$ и $$$Y \cdot p^{n-i'}$$$. В таком виде их и ключём в хеш-таблице можно использовать, т.к. у любой подстроки просто степень всегда начинается с $$$n$$$, а за исключением этого во всех ситуациях хеш получается одинаковый. Если строк много, то можно использовать $$$maxn$$$ вместо $$$n$$$. Не очень красиво, но для спортивной проги сойдёт.

Так что мораль: пишите хеширование без домножения и без деления.

Так а что значит без умножения? В $$$h(s[i..j]) = H[i] - H[j+1] \cdot p^{j-i+1}$$$ умножение есть.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

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

    Я наблюдаю, как у меня пишут школьники (в том числе учившие хеширование не у меня), и редко кто так пишет. Год назад на мероприятии vk fellowship также зашел разговор, выяснилось, что мало кто знает.

    Ну случай i=0 в исходном варианте тоже обходился легко -- посчитать в 1-индексации и добавить h[0]=0.

    Это понятно, но тоже костыль.

    Можно в универсальном виде.

    Да, конечно, так даже в мапу можно засовывать. Я не говорю, что это невозможно :)

    Так а что значит без умножения

    Не без умножения, а без домножения. Без каких-либо дополнительных действий после того, как получено значение хеша. Собственно я про это и пишу: "Полученные значения вам уже не надо ни на что домножать, вы можете их сравнивать, можете использовать как ключ в какой-нибудь мапе, и т.д. Вы можете написать class StringWithHash с таким методом, и потом в основной программе уже просто использовать результат вызова метода."

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I've been writing hashes like this for ages. The code turns out very short and easily extendable for the case of multiple hashes.

You could also add a full code so people can compare it with their implementaion.