Алгоритмы
Rabin-Karp: Хеширование строк
Цели урока
- Понять идею хеш-поиска
- Реализовать Rolling Hash
- Понимать проблему коллизий
- Применять для множественного поиска
Предварительные знания
- Наивный поиск подстроки
Зачем сравнивать 1000 символов, если можно сравнить 2 числа? Rabin-Karp использует математическую магию хеширования для молниеносного поиска.
- Поиск плагиата в текстах
- Антивирусы (поиск сигнатур)
- Дедупликация данных
- Поиск похожих изображений (perceptual hashing)
Хеширование превращает поиск строки в арифметику
Ричард Карп и Майкл Рабин опубликовали свой алгоритм в 1987 году в статье Efficient randomized pattern-matching algorithms. Их идея отличалась от KMP: вместо сравнения символов сравнивать хеши. Хешируем шаблон один раз, затем хешируем каждое окно текста и сравниваем числа. Приём, который делает это быстрым, это полиномиальный скользящий хеш. Когда окно сдвигается на один символ вправо, хеш не пересчитывается заново. Вычитается вклад уходящего символа и добавляется вклад нового за константное время, а окно трактуется как число в некоторой системе счисления по модулю простого числа. Совпадение хешей затем проверяется посимвольно, чтобы исключить коллизии. В среднем время линейное, а та же идея скользящего хеша позже легла в основу поиска по многим шаблонам и разбиения данных на блоки в системах вроде rsync.
Идея: сравниваем хеши
**Идея Rabin-Karp:** вместо посимвольного сравнения - сравниваем хеши. Если хеши разные - строки точно разные. Если равны - проверяем.
**Проблема:** вычислять хеш для каждой позиции - O(m), всего O(nm). Не лучше наивного!
**Решение:** Rolling Hash - пересчитываем хеш за O(1) при сдвиге.
Если hash(pattern) ≠ hash(text[i:i+m]), то:
Rolling Hash
**Полиномиальный хеш:** представляем строку как число в системе счисления base.
**Rolling update:**
**Коллизии:** разные строки могут иметь одинаковый хеш. При равенстве хешей ВСЕГДА проверяйте строки!
Зачем нужен mod (модуль)?
Реализация Rabin-Karp
| Случай | Сложность | Причина |
|---|---|---|
| Best/Average | O(n + m) | Мало коллизий |
| Worst | O(nm) | Все хеши совпадают (много коллизий) |
**Double hashing:** используйте два хеша с разными base и mod. Вероятность коллизии ≈ 1/mod² - практически 0.
Почему при pattern_hash == window_hash мы ВСЁ РАВНО сравниваем строки?
Применения
**1. Поиск нескольких паттернов:**
**2. Поиск плагиата (общие подстроки):**
**3. Longest Common Substring (бинарный поиск по длине):**
**Rabin-Karp vs KMP:** KMP гарантирует O(n+m), Rabin-Karp проще и лучше для множественного поиска.
Для поиска 100 паттернов одной длины в тексте, что эффективнее?
Rabin-Karp
- Сравниваем хеши, не строки
- Rolling Hash: O(1) на сдвиг
- O(n+m) average, O(nm) worst (коллизии)
- Double hashing уменьшает коллизии
- Отлично для множественного поиска
Связанные темы
Rabin-Karp - основа для многих строковых алгоритмов.
Связанные уроки
- alg-23-pattern-matching — Rabin-Karp - хеш-ответ на наивный поиск
- ds-06-hash-intro — Скользящий хеш опирается на базовые идеи хеширования
- alg-24-kmp — Оба дают O(n+m); KMP точен, RK вероятностен
- crypto-19-hash-functions — Коллизии хешей объясняют ложные срабатывания Rabin-Karp