Рабин-Карп: сравнивать числа вместо строк

Если ты напишешь формулу пересчёта хеша при сдвиге окна, объяснишь, откуда берутся ложные срабатывания и почему их число около n / q, - листай до «Теперь сам».

Как думаешь, что будет при маленьком модуле

Наивный поиск тратит на позицию до m сравнений. Идея: превратить образец в число, каждое окно текста - тоже в число, и сравнивать числа. Одно сравнение на позицию при любой длине образца.

Числа приходится держать маленькими, поэтому от каждого берут остаток от деления на q. Прежде чем читать дальше, ответь себе: что случится, если взять q = 13? Остатков всего тринадцать, а разных окон в тексте тысячи. Алгоритм начнёт врать? Станет медленным? Или ничего не изменится?

На что это похоже

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

Угол не говорит «это она». Он говорит «это точно не она» - и говорит быстро. Чем больше цифр напечатано в углу, тем реже приходится читать квитанцию зря.

Механизм: окно как число и пересчёт за одно действие

Сначала на цифрах, без остатков. Текст 2718281828459045, образец 1828, длина образца m = 4. Каждое окно из четырёх цифр - обычное четырёхзначное число:

окно с позиции 0:   2 7 1 8                  2718
окно с позиции 1:     7 1 8 2                7182

7182 = (2718 − 2 · 1000) · 10 + 2
        │      │           │    └ пришедшая цифра
        │      │           └ сдвиг на разряд влево
        │      └ ушедшая цифра в старшем разряде: вес 10^(m−1) = 1000
        └ старое окно

Три действия вместо четырёх сравнений - и число действий не зависит от m. При образце в тысячу символов пересчёт стоит те же три действия.

Для букв всё то же, только основание не 10, а число x, большее всех кодов символов, и цифрами служат коды: ord("a") = 97. Больше кодов - затем же, зачем основание 10 больше любой цифры: тогда разные строки дают разные числа. Для латинских букв и байтов годится 256, в этом уроке оно и взято; у русских букв коды больше тысячи, и основание для них берут больше. Окно abr - это число 97 · 256² + 98 · 256 + 114. Такой способ превратить строку в число называют полиномиальным хешем: символы - коэффициенты многочлена от x.

Беда в размере. Окно из тысячи символов - число из тысячи «цифр» по основанию 256, и арифметика над ним стоит ту же тысячу действий. Поэтому все вычисления ведут по модулю q: после каждого действия берут остаток от деления на q. Остаток суммы и произведения можно считать по остаткам слагаемых и множителей, так что формула пересчёта остаётся той же, а числа остаются небольшими, сколько бы символов ни было в окне.

Цена модуля - ложное срабатывание: разные окна могут дать один остаток. Возьмём q = 11:

позиция    0     1     2     3     4     5     6
окно      2718  7182  1828  8281  2818  8182  1828
mod 11     1    10     2     9     2     9     2
                       ▲           ▲           ▲
образец 1828 mod 11 = 2:   вхождение     ложное     вхождение

Показаны первые семь окон из тринадцати; у остальных шести остаток другой. Окно 2818 - не образец, но 2818 mod 11 = 2, как и у 1828. Поэтому совпадение хешей - не ответ, а повод сравнить строки посимвольно.

Правило

Хеш окна пересчитывается при сдвиге за постоянное время: h_новый = ((h_старый − код_ушедшего · x^(m−1)) · x + код_пришедшего) mod q. Степень x^(m−1) mod q считается один раз до поиска. Если хеш окна не равен хешу образца, вхождения здесь точно нет. Если равен - вхождение возможно, и строки сравниваются посимвольно. При случайных данных ложных срабатываний в среднем n / q, и общая цена - около n + m действий плюс m на каждое срабатывание, истинное или ложное. Худший случай остаётся n · m: он достигается, когда срабатываний много.

Разбор: программа и первый пересчёт руками

def rk(t, p, x, q):
    n = len(t)
    m = len(p)
    hp = 0                            # хеш образца
    ht = 0                            # хеш текущего окна
    st = 1                            # x^(m-1) mod q
    i = 0
    while i < m:
        hp = (hp * x + ord(p[i])) % q
        ht = (ht * x + ord(t[i])) % q
        if i > 0:
            st = st * x % q
        i = i + 1
    nashli = 0
    lozh = 0
    i = 0
    while True:
        if hp == ht:                  # хеши совпали - проверяем строки
            j = 0
            while j < m and t[i + j] == p[j]:
                j = j + 1
            if j == m:
                nashli = nashli + 1
            else:
                lozh = lozh + 1
        if i + m >= n:
            break
        ht = ((ht - ord(t[i]) * st) * x + ord(t[i + m])) % q
        i = i + 1
    return [nashli, lozh]

Первый цикл считает оба хеша схемой «умножь накопленное на x, прибавь следующий код» - m действий. Второй идёт по позициям и на каждой делает одно сравнение чисел и один пересчёт.

Проверим пересчёт на цифровом примере, q = 11. Хеш окна 2718 равен 2718 mod 11 = 1. Вес старшего разряда: 1000 mod 11 = 10. Ушла цифра 2, пришла цифра 2:

(1 − 2 · 10) · 10 + 2 = −19 · 10 + 2 = −188
−188 mod 11 = 10          потому что −188 = −18 · 11 + 10
проверка: 7182 mod 11 = 10

Сошлось, хотя по дороге число стало отрицательным. Python возвращает остаток от нуля до q − 1 и для отрицательных чисел, поэтому в программе об этом заботиться не пришлось. В большинстве других языков это не так - см. «Что ломается».

Разбор: сколько стоит маленький модуль

Текст строит генератор из прошлого урока, но в десять раз длиннее: t = tekst(10000, 4, 1), образец - десять символов t[5000:5010], основание x = 256. Вхождение одно. Наивный поиск на этих данных делает 13 302 сравнения символов.

q            ложных срабатываний    ожидаемо n / q
13                  765                 769
101                 110                  99
1 009                 9                  10
65 521                1                 0,15
1 000 003             0                 0,01

Ответ на вопрос из начала урока: при q = 13 алгоритм не врёт - каждое срабатывание перепроверяется, и найдено ровно одно вхождение. Он делает лишнюю работу: 765 раз хеш совпал напрасно.

Столбец n / q получается просто. Остаток случайного окна с равными шансами попадает в любой из q вариантов, значит с нужным совпадает в среднем одно окно из q. Окон около n. Модуль выбирают большим - порядка миллиона и больше; тогда ложные срабатывания случаются реже одного на миллион окон. Потолок задают языки с числами фиксированного размера: там модуль обязан быть таким, чтобы промежуточные произведения не переполнялись. В Python целые не переполняются, но чем они длиннее, тем медленнее арифметика.

Теперь граница. Текст "a" * 1000, образец "a" * 10: вхождение на каждой из 991 позиций, все срабатывания истинные, каждое перепроверяется десятью сравнениями - 9910 сравнений, столько же, сколько у наивного поиска. Хеш экономит на позициях, где образца НЕТ. Там, где он есть, проверка всё равно стоит m.

Что ломается без этого

Первое: отрицательный остаток. В C, Java, JavaScript и Go выражение -188 % 11 равно -1, а не 10. Хеш окна становится отрицательным, с хешем образца не совпадает никогда, и поиск молча ничего не находит. Лечится вторым остатком - взять остаток, прибавить q и взять остаток ещё раз: ((ht - kod * st) % q + q) % q.

Второе: степень на единицу больше. Вес ушедшего символа - x^(m−1), а не x^m: старший из m разрядов имеет номер m − 1. С x^m пересчёт вычитает не то, и хеши окон превращаются в мусор начиная со второго окна. Первое окно при этом считается верно, поэтому тест «образец в начале текста» проходит.

Третье: поверить хешу без проверки. Без посимвольного сравнения программа на замере выше сообщила бы 766 вхождений при q = 13. При большом q ошибка редкая и потому особенно неприятная: она проявится раз в месяц на чужих данных.

Четвёртое: известные заранее x и q. Тот, кто их знает, может подобрать строки с одинаковым хешем и превратить каждое окно в срабатывание - получится худший случай по заказу. Это та же атака, что на хеш-таблицу в разделе про хеширование, и защита та же: выбирать основание случайно при запуске программы.

Зачем это в работе

Первый сюжет - много образцов одной длины. Сложи их хеши в множество, и один проход по тексту проверяет каждое окно против всех образцов сразу: вопрос «есть ли такой хеш в множестве» стоит одно действие независимо от числа образцов. Так ищут заимствования: хеши всех кусков по сорок символов из одной работы сравниваются с хешами кусков из тысяч других.

Второй - синхронизация файлов. Программа rsync находит в новой версии файла блоки, которые уже есть в старой, скользя по файлу окном и пересчитывая контрольную сумму тем же приёмом «убрать ушедший байт, добавить пришедший». Программы резервного копирования так же режут файлы на куски по содержимому, чтобы вставка одного байта в начало не меняла все куски после него.

Третий - поиск в двумерных данных и сравнение подстрок между собой. Хеши всех префиксов строки, посчитанные один раз, дают хеш ЛЮБОЙ подстроки за одно вычитание, и вопрос «равны ли эти два куска» решается без посимвольного сравнения. На этом построена половина приёмов олимпиадного программирования на строках.

Теперь сам

Текст 271828182, образец 8281, основание 10, модуль q = 7. Хеш первого окна: 2718 mod 7 = 2. Вес старшего разряда: 1000 mod 7 = 6. Пересчитай хеш для окна с позиции 1 по формуле, а затем скажи, на каких позициях хеш окна совпадёт с хешем образца и сколько из этих срабатываний ложные. Остатки окон по порядку: 2718 → 2, 1828 → 1, 8281 → 0, 2818 → 4, 8182 → 6; окно с позиции 1 - твоё.