STR Строки и тексты Приём
Полиномиальный хеш
Также: Polynomial rolling hash · rolling hash · скользящий хеш · многочленный хеш · хеширование строк · префиксные хеши · anti-hash test
Строку превращают в число: значение многочлена, коэффициенты которого — коды букв, по модулю большого простого. Посчитав такие числа для всех начал строки, сравнивают любые два куска за O(1), находят длину общего начала двух мест текста за O(log n) и катят хеш окна по тексту за одно действие на букву. Платят за это вероятностью ошибки — её надо уметь считать и не отдавать в руки противнику.
Разрежем первую часть «Войны и мира» на все куски по 16 букв подряд — их 244 485, разных 238 589 — и посчитаем хеш каждого по модулю 10⁹ + 7, любимому модулю олимпиадников. Хеш — это число от нуля до миллиарда, и кусков в четыре тысячи раз меньше, чем возможных хешей. Тем не менее у 29 пар разных кусков хеши совпали. «Мои дети — ce so» и «росилась между к» оба дают 498 024 809. Переключите модуль и длину куска, попробуйте другое основание: число совпадений почти не зависит от основания, но очень зависит от модуля.
Чёрная черта на каждой полосе — ожидание: если хеши ведут себя как случайные числа, пар с одним хешем среди k разных кусков в среднем k(k − 1)/(2p). При p = 10⁹ + 7 это 28,46, а нашлось 29. При p = 65 537 — 434 293 и 434 210. Расчёт сходится с опытом на всех модулях: хеш действительно разбрасывает куски романа как жребий. Плохо не это, а то, что пар кусков в первой части 28 миллиардов, и даже миллиард возможных значений их не вмещает. При модуле 2⁶¹ − 1 ожидается около одной стомиллионной пары, и не нашлось ни одной.
Хеш сравнивает строки за одно действие, но иногда ошибается. Статья о том, как устроить его, чтобы ошибался редко и предсказуемо, и как не дать противнику сделать так, чтобы он ошибался всегда.
Идея
Будем читать строку как число, записанное в системе счисления с основанием b: цифры — коды букв. Тогда число любого куска получается из чисел двух начал строки: из числа длинного начала вычесть число короткого, сдвинутое на нужное число разрядов. Чтобы числа не росли, всё считается по модулю большого простого p. Равные куски всегда дают равные числа, разные — почти никогда.
Полиномиальный хеш строки s = s₀s₁…sm−1 — это
$$h(s) = \bigl(s_0 b^{m-1} + s_1 b^{m-2} + \dots + s_{m-1}\bigr) \bmod p.$$Считать его удобно схемой Горнера: умножить накопленное на b, прибавить код следующей буквы, взять остаток. Если записать хеши всех начал строки, H[i] — хеш первых i букв, то
$$h(s[l..r)) = \bigl(H[r] - H[l]\cdot b^{\,r-l}\bigr) \bmod p.$$Это одна строчка арифметики: H[r] — число из r цифр, его старшие l цифр — это H[l], сдвинутое на r − l разрядов, а младшие — как раз кусок. Нужны ещё степени b, их тоже считают заранее. Проверьте формулу руками: модуль здесь 1009, основание 31, а под каждой буквой — хеш начала строки до неё включительно.
Два куска «абра» — в начале и в конце слова — дают 542, хотя считаются из совсем разных чисел: 542 − 0 · 31⁴ и 451 − 229 · 31⁴. Нажмите «Найти коллизию»: «абракада» и «адабр» тоже дают 99. При модуле 1009 хешей всего тысяча, и даже на слове из одиннадцати букв они повторяются. Переключите на 10⁹ + 7, и коллизия исчезнет.
Окно, которое едет по тексту, обновляется так же. Чтобы из хеша куска s[i..i + m) получить хеш следующего, надо вычесть вклад ушедшей буквы si · bm−1, сдвинуть на разряд и прибавить пришедшую букву: (h − si · bm−1) · b + si+m по модулю p. Три действия на букву при любой длине окна — на этом стоит алгоритм Рабина — Карпа.
Почему коллизии редки
Пусть p — простое число, большее кода любой буквы, а основание b выбрано случайно и равновероятно из 0, 1, …, p − 1. Тогда две разные строки длины L получают одинаковый хеш с вероятностью не больше (L − 1)/p.
Хеш строки — значение многочлена s₀xL−1 + … + sL−1 в точке x = b по модулю p. Хеши двух строк совпадают, когда в точке b обращается в ноль разность их многочленов. Строки разные, а коды меньше p, поэтому хотя бы один коэффициент разности не делится на p: это ненулевой многочлен степени не выше L − 1. Остатки по простому модулю образуют поле, а у ненулевого многочлена над полем корней не больше, чем его степень. Значит, «плохих» оснований не больше L − 1 из p.
Та же теорема и опыт с солью для хеш-таблиц — в главе курса о хешировании. Здесь важны два следствия.
Одно сравнение почти безопасно. Для кусков в тысячу букв и p = 10⁹ + 7 вероятность ошибки — меньше одной миллионной. Если сравнений q, вероятность хоть одной ошибки не больше q(L − 1)/p: вероятности ошибок складываются.
Много кусков друг с другом — опасно. Если надо найти одинаковые среди k кусков, сравниваются все пары, а их k²/2. Это задача о днях рождения: ожидаемое число ложных совпадений около k²/(2p). При p = 10⁹ + 7 и десяти тысячах кусков — 0,05, при ста тысячах — уже 5, а в первой части романа, где кусков 238 тысяч, их 29. Для таких задач берут модуль порядка 2⁶¹ или два модуля сразу, тогда даже сто миллионов кусков дают в среднем 0,002 ложной пары.
У Карпа и Рабина в работе, написанной в 1981 году и напечатанной в 1987-м, случайным было не основание, а модуль: двоичную строку читали как число и брали остаток от деления на случайное простое. Оценка там другая — сколько простых могут делить разность двух чисел, — но смысл тот же: противник не знает, что именно будет посчитано. Сегодня чаще фиксируют простой модуль и выбирают случайное основание: оценка проще, а арифметика быстрее.
Код
PrefixHash хранит хеши начал и степени основания, get — формула из раздела выше, lcp — двоичный поиск длины общего начала, о нём следующий раздел, window_hashes — окно, которое катится по тексту. Модуль по умолчанию — 2⁶¹ − 1. Python считает длинными целыми и переполнения не знает. В Go произведение двух остатков по такому модулю в 64 бита не помещается: mulmod берёт 128-битное произведение из bits.Mul64 и остаток из bits.Div64. В C++ для этого есть __int128 или приём для простых вида 2k − 1: остаток от деления x на 2⁶¹ − 1 равен (x >> 61) + (x & (2⁶¹ − 1)), с одним вычитанием модуля в конце, если сумма вышла больше него.
Первые строки вывода — пример со словом «абракадабра», те же числа, что в сцене. Дальше — четыре модуля на кусках романа, как в первой сцене, и первые три пары разных кусков с одним хешем по модулю 10⁹ + 7. Основание — 9 873 241, одно для всех модулей, для маленьких — его остаток. С другим основанием пары будут другими, а их число — снова около ожидаемого.
Насколько совпадают два места
Если первые k букв с позиций i и j совпадают, то совпадают и первые k − 1. Такое условие проверяют двоичным поиском: длина общего начала находится за log₂ n сравнений хешей, каждое за O(1). В первой части романа фраза «Пьер ничего» встречается на позициях 165 602 и 189 222, и функция lcp из листинга отвечает, что дальше совпадают 22 буквы: «Пьер ничего не понимал». Одна и та же фраза дважды, с разницей в двадцать с лишним тысяч знаков.
На общем начале держится многое.
- Сравнение кусков по алфавиту. Найти длину общего начала и сравнить следующую букву. Сортировка всех суффиксов текста таким сравнением даёт суффиксный массив за O(n log² n).
- Палиндромы. Посчитать хеши начал и для перевёрнутой строки: кусок — палиндром, если его хеш совпадает с хешем того же куска, прочитанного справа налево. Самый длинный палиндром с центром в данной точке — снова двоичный поиск.
- Период. Строка длины n имеет период q, если её начало длины n − q совпадает с концом той же длины: одно сравнение хешей на каждого кандидата.
- Сколько сравнений сделает перебор. Задача о счётчике сравнений из статьи про наивный поиск требует длину общего начала образца с каждым местом текста; её решают Z-функцией, но годится и хеш с двоичным поиском.
Сколько это стоит
| Операция | Время | Вероятность ошибки |
|---|---|---|
| хеши начал и степени | O(n), память O(n) | — |
| хеш куска | O(1) | — |
| равны ли два куска длины L | O(1) | ≤ (L − 1)/p, только «да» может быть ложным |
| длина общего начала двух мест | O(log n) | ≤ (n − 1) log₂ n / p |
| окно сдвинулось на букву | O(1) | — |
Ошибка всегда односторонняя: разные хеши — всегда разные куски, а одинаковые хеши — почти всегда одинаковые. Если ошибка недопустима, совпадение проверяют буквами. Это стоит O(L), но только на совпадениях, а их обычно мало.
Замер: текст abab… длины n и пятьдесят пар позиций, где он совпадает почти до конца. Длина общего начала — буква за буквой и двоичным поиском по хешам.
По буквам время растёт вместе с n, наклон 1. Двоичный поиск по хешам почти не замечает длины: при тексте в 65 536 букв в Python он быстрее больше чем в четыреста раз, в Go — примерно в триста. На прозе картина обратная: два случайных места романа расходятся на первой-второй букве, и буквенное сравнение заканчивается раньше, чем двоичный поиск сделает первый шаг. Хеш нужен там, где общие куски длинные: повторы, периоды, сравнение почти одинаковых строк.
Где ломается: модуль 2⁶⁴
Самая соблазнительная реализация — вообще не брать остаток. Если считать в 64-битных беззнаковых числах, переполнение само берёт остаток по модулю 2⁶⁴, и хеш выходит быстрым и вроде бы надёжным: значений 18 квинтиллионов. Но 2⁶⁴ — не простое число, теорема о корнях здесь не работает, и есть пара строк, хеши которых совпадают при любом нечётном основании.
Строки Туэ — Морса строятся удвоением: из S = a и T = b получаются S → ST, T → TS: abba и baab, abbabaab и baababba, и так далее. Двигайте длину и смотрите на младшие биты разности хешей.
Пусть Sk и Tk — строки Туэ — Морса длины 2k, а основание b нечётно. Тогда разность их полиномиальных хешей делится на 2 в степени 1 + (k − 1)(k + 4)/2. При k = 10, то есть на строках из 1024 букв, это 2⁶⁴: хеши по модулю 2⁶⁴ совпадают.
Хеш склейки XY равен h(X) · b|Y| + h(Y). Обозначим Dk = h(Sk) − h(Tk) и N = 2k. Тогда
$$D_{k+1} = h(S_k)\,b^N + h(T_k) - h(T_k)\,b^N - h(S_k) = D_k\,(b^N - 1),$$а D₀ = a − b = −1. Значит, Dk = −(b − 1)(b² − 1)(b⁴ − 1)…(b2k−1 − 1). При нечётном b множитель b − 1 чётный. Квадрат нечётного числа даёт остаток 1 при делении на 8, поэтому b² − 1 делится на 8. И каждый следующий множитель делится на 2 хотя бы на один раз больше предыдущего: b2t − 1 = (bt − 1)(bt + 1), а второй сомножитель чётный. Итого степень двойки в Dk не меньше 1 + 3 + 4 + … + (k + 1) = 1 + (k − 1)(k + 4)/2. При k = 10 это 64.
Листинг ниже проверяет это для основания 131: нули в конце разности — 1, 4, 8, 13, 19, 26, 34, 43, 53 и на десятом шаге все 64, ровно по оценке. Те же строки из 1024 букв совпадают по хешу при основаниях 3, 31, 10⁹ + 7 и при случайном 64-битном нечётном, а по модулю 2⁶¹ − 1 — нет. Случайное основание здесь не спасает: многочлен (x − 1)(x² − 1)…(x⁵¹² − 1) по модулю 2⁶⁴ обращается в ноль в каждой нечётной точке, и теорема о не более чем L − 1 корнях не работает, потому что 2⁶⁴ — не простое. Чётное основание ещё хуже: 256⁸ = 2⁶⁴, и при основании 256 в хеше остаются только последние восемь букв, так что «войнаabcdefgh» и «мирabcdefgh» совпадают.
То же с 32-битными хешами. Оценка даёт 2³² уже при k = 7: любые две строки Туэ — Морса из 128 букв совпадают по хешу String.hashCode из Java и по хешу, которым strings.Index в Go ищет длинные образцы. В Go это не ошибка, а только лишняя работа: поиск проверяет совпадение хешей сравнением строк.
В олимпиадах строки Туэ — Морса — стандартный тест против хеша без модуля, и решение с unsigned long long на нём получает неверный ответ при любом основании. Если основание и модуль известны заранее, коллизию для простого модуля около 10⁹ тоже находят быстро: по задаче о днях рождения хватает нескольких десятков тысяч случайных строк. Это задача о взломе хеша ниже. Защита — простой модуль порядка 2⁶¹ или два модуля и основание, которое программа выбирает случайно при запуске.
Где работает
- Поиск образца. Алгоритм Рабина — Карпа катит хеш окна по тексту и сравнивает буквы только там, где хеш совпал с хешем образца. В Go так ищет
strings.Index, когда фильтр по первому байту часто ошибается: основание 16 777 619, модуль 2³², совпадения проверяются сравнением строк. - Куски по содержимому. Сетевая файловая система LBFS (2001) катила по файлу окно из 48 байт и объявляла границу куска там, где у отпечатка окна 13 младших битов нулевые. Вставка в начало файла меняет только тот кусок, куда она попала: остальные границы стоят там же, где стояли, относительно текста, и остальные куски не надо пересылать заново. Тот же приём использует программа резервного копирования restic. Отпечаток здесь — отпечаток Рабина: многочлен с коэффициентами 0 и 1 по модулю случайного неприводимого многочлена, то есть та же идея в двоичной арифметике без переносов.
- Скользящие суммы. rsync тоже катит по файлу окно, но вместо многочлена у него пара сумм по модулю 2¹⁶ — простая сумма байтов и сумма с весами. Так описали его Эндрю Триджелл и Пол Маккеррас в 1996 году, по образцу контрольной суммы Adler-32.
- Олимпиады. Сравнение подстрок, палиндромы, периоды, общие куски двух строк, повторы: многие задачи, где честный алгоритм — суффиксное дерево или автомат, решаются хешами быстрее, чем пишется честный алгоритм.
История
Михаэль Рабин в 1981 году описал «отпечатки случайными многочленами»: строку битов читают как многочлен и берут остаток от деления на случайный неприводимый многочлен. В том же году вместе с Ричардом Карпом он написал работу о поиске образца отпечатками, напечатанную в 1987 году в IBM Journal of Research and Development: окно катится по тексту, отпечаток обновляется за постоянное время, а вероятность ошибки оценивается через случайный выбор модуля. Строки, которые ломают хеш по модулю степени двойки, гораздо старше. Последовательность из удвоений a → ab, b → ba изучал ещё Эжен Пруэ в 1851 году в теории чисел, Аксель Туэ в 1906 году построил на ней комбинаторику слов, а Марстон Морс в 1921-м — применил к геометрии.
Задачи
В первой задаче нужно отвечать на сотни тысяч вопросов «одинаковы ли эти два куска текста», и среди тестов есть строки Туэ — Морса. Во второй роли меняются: дано основание и модуль, а нужно построить две разные строки с одинаковым хешем.
Одинаковые куски Взломать хешДанные: «Война и мир», Л. Н. Толстой, общественное достояние