|
|
| Строка 49: |
Строка 49: |
| | | | |
| | Итоговое время работы алгоритма <tex>O(n + m)</tex>. | | Итоговое время работы алгоритма <tex>O(n + m)</tex>. |
| − |
| |
| − | ===Пример худшего случая===
| |
| − | Если количество подстрок данной строки превышает количество хешей (а это выполняется тогда, когда длина строки больше <tex>r</tex>, так как количество различных значений полиномиального хеша совпадает с <tex>r</tex>), то наступление [[Разрешение_коллизий | коллизий]] неизбежно. Но даже при относительно небольших строках вероятность коллизий может быть [[Хеш-таблица#Введение | высока]], не говоря уже о способах составления специальных строк, где алгоритм на хешах выдаёт частые ложные срабатывания.
| |
| − |
| |
| − | Например, возьмем за <tex>S</tex> [[Слово_Туэ-Морса | строку Туэ-Морса]]<ref>[http://codeforces.ru/blog/entry/4898 Codeforces: Anti-hash test]</ref> длиной <tex>2^{k}</tex>, <tex>r = 2^{64}</tex>, <tex>p</tex> — любое просто число.
| |
| − |
| |
| − | Обозначим за <tex>S_k</tex> строку <tex>S</tex> для фиксированного <tex>k</tex> , а за <tex>S'_k</tex> инвертированную строку <tex>S</tex>.
| |
| − |
| |
| − | Покажем, что при <tex>k < 12</tex>, <tex>\mathrm{hash}(S_k) = \mathrm{hash}(S'_k)</tex>. Ведь если это так, то сами по себе <tex>S_k</tex> и <tex>S'_k</tex> встретятся в б''о''льших строках много-много раз.
| |
| − |
| |
| − | Разберемся, что значит <tex>\mathrm{hash}(S_k) = \mathrm{hash}(S'_k)</tex>. Можно смело заменить коды символов на нули и единицы в коэффициентах многочлена — тем самым мы просто сократим обе части на <tex>\sum\limits_{i=0}^{2^k - 1} 65 \cdot p^i</tex>.
| |
| − |
| |
| − | Величина <tex>\mathrm{hash}(S_k) - \mathrm{hash}(S'_k)</tex> есть некоторое число <tex>T = p^{0} - p^{1} - p^{2} + p^{3} - p^{4} + p^{5} + p^{6} - p^{7} ... \pm p^{2^k - 1}</tex>. То есть это сумма степеней <tex>p</tex>, где знаки чередуются по тому же правилу, что и символы в строке.
| |
| − |
| |
| − | Будем последовательно выносить из этой суммы множители за скобку:
| |
| − |
| |
| − | <tex>T = (p^{1} - 1)( - p^{0} + p^{2} + p^{4} - p^{6} + p^{8} - p^{10} - p^{12} + p^{14} ...) = </tex>
| |
| − |
| |
| − | <tex> = (p^{1} - 1)(p^{2} - 1)(p^{0} - p^{4} - p^{8} + p^{12} ...) = ... = (p^{1} - 1)(p^{2} - 1)(p^{4} - 1) ... (p^{2^{k-1}} - 1).</tex>
| |
| − |
| |
| − | Покажем, что <tex>T</tex> <tex>\mathrm{mod}</tex> <tex>r = 0</tex>:
| |
| − |
| |
| − | Нужно понять, на какую максимальную степень двойки делится каждая из <tex>k - 1</tex> скобок. Заметим, что <tex>(i + 1)</tex>-ая скобка <tex>p^{2^{i + 1}} - 1 = (p^{2i} - 1)(p^{2i} + 1)</tex> делится на <tex>i</tex>-ую и ещё на какое-то чётное число <tex>p^{2i} + 1</tex>. Это означает, что если <tex>i</tex>-ая скобка делится на <tex>2^r</tex>, то <tex>(i + 1)</tex>-ая скобка делится по меньшей мере на <tex>2^{r + 1}</tex>.
| |
| − |
| |
| − | Получается, что <tex>(p^1 - 1)(p^2 - 1)(p^4 - 1)...(p^{2k - 1} - 1)</tex> делится по меньшей мере на <tex>2 \cdot 2^2 \cdot 2^3 \cdot ... = 2^{k(k - 1) / 2}</tex>.
| |
| − |
| |
| − | Мы показали, что если k < 12, то величина <tex>\mathrm{hash}(S_k) - \mathrm{hash}(S'_k) = 0</tex>, то есть <tex>\mathrm{hash}(S_k) = \mathrm{hash}(S'_k)</tex>. Значит достаточно взять <tex>k >= 12</tex>, чтобы в рассматриваемой строке было очень много различных подстрок, чьи хеши совпадут.
| |
| | | | |
| | == Сравнение с другими алгоритмами == | | == Сравнение с другими алгоритмами == |
Версия 22:32, 15 июня 2015
Алгоритм Рабина-Карпа предназначен для поиска подстроки в строке.
Метод хеширования
Наивный алгоритм поиска подстроки в строке работает за [math]O\left(n^2\right)[/math] в худшем случае — слишком долго. Чтобы ускорить этот процесс, можно воспользоваться методом хеширования.
| Определение: |
| Пусть дана строка [math]s[0..n-1][/math]. Тогда полиномиальным хешем строки [math]s[/math] называется число [math]h = \mathrm{hash}(s[0..n-1]) = p^{0} s[0] + ... + p^{n - 1} s[n-1][/math], где [math]p[/math] — некоторое простое число, а [math]s[i][/math] [math]{-}[/math] код [math]i[/math]-ого символа строки [math]s[/math]. |
Проблему переполнения при вычислении хешей довольно больших строк можно решить так [math]{-}[/math] считать хеши по модулю [math]r=2^{64}[/math], чтобы модуль брался автоматически при переполнении типов.
Использование полиномиального хеша именно с убывающими степенями [math]p[/math] позволяет нам, зная хеш некоторой строки, посчитать хеш строки, образованной удалением первого символа и добавлением символа в конец, за [math]O(1)[/math]:
[math]\mathrm{hash}(s[i + 1..i + m - 1]) = (\mathrm{hash}(s[i..i + m - 1]) - p^{m - 1} s[i]) \bmod r[/math].
[math]\mathrm{hash}(s[i + 1..i + m]) = (p \cdot \mathrm{hash}(s[i + 1..i + m - 1]) + s[i + m]) \bmod r[/math].
Получается : [math]\mathrm{hash}(s[i + 1..i + m]) = (p \cdot \mathrm{hash}(s[i..i + m - 1]) - p^{m} s[i] + s[i + m]) \bmod r[/math].
Решение
Алгоритм
Алгоритм начинается с подсчета [math]\mathrm{hash}(s[0..m-1])[/math] и [math]\mathrm{hash}(p[0..m-1])[/math], а также с подсчета [math]p^{m}[/math], для ускорения ответов на запрос.
Для [math]i \in [0..n - m][/math] вычисляется [math]\mathrm{hash}(s[i..i + m - 1])[/math] и сравнивается с [math]\mathrm{hash}(p[0..m-1])[/math]. Если они оказались равны, то образец [math]p[/math] скорее всего содержится в строке [math]s[/math] начиная с позиции [math]i[/math], хотя возможны и ложные срабатывания алгоритма. Если требуется свести такие срабатывания к минимуму или исключить вовсе, то применяют сравнение некоторых символов из этих строк, которые выбраны случайным образом, или применяют явное сравнение строк, как в наивном алгоритме поиска подстроки в строке. В первом случае проверка произойдет быстрее, но вероятность ложного срабатывания, хоть и небольшая, останется. Во втором случае проверка займет время, равное длине образца, но полностью исключит возможность ложного срабатывания.
Для ускорения работы алгоритма оптимально предпосчитать [math]p^{m}[/math]. Однако, если требуется, например, найти индексы вхождения нескольких образцов, или, сравнить две строки [math]{-}[/math] выгоднее будет предпосчитать все степени [math]p[/math], а также хеши всех префиксов строки [math]s[/math].
Псевдокод
Приведем пример псевдокода, который находит все вхождения строки [math]w[/math] в строку [math]s[/math] и возвращает массив позиций, откуда начинаются вхождения.
vector<int> rabinKarp (s : string, w : string):
vector<int> answer
int n = s.length
int m = w.length
int hashS = hash(s[0..m-1])
int hashW = hash(w[0..m-1])
for i = 0 to n - m
if hashS == hashW
answer.add(i)
hashS = (p * hashS - p[math]^{m}[/math] * hash(s[i]) + hash(s[i + m])) mod r // r — некоторое большое число, p — некоторое просто число
return answer
Новый хеш [math]hashS[/math] был получен с помощью быстрого пересчёта. Для сохранения корректности алгоритма нужно считать, что [math]s[n + 1][/math] — пустой символ.
Время работы
Изначальный подсчёт хешей выполняется за [math]O(m)[/math].
Каждая итерация выполняется за [math]O(1)[/math], В цикле всего [math]n - m + 1[/math] итераций.
Итоговое время работы алгоритма [math]O(n + m)[/math].
Сравнение с другими алгоритмами
Преимущества
- Быстрая скорость работы — [math]O(n + m)[/math], где [math]n[/math] — длина строки, [math]m[/math] — длина образца.
- Простая и понятная реализация.
Недостатки
- Возможно подобрать входные данные так, что количество ложных срабатываний будет недопустимо большим (см. Пример худшего случая).
См. также
Примечания
Источники информации
- Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд Алгоритмы: построение и анализ, 3-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2014. — 1328 с.: ил. — ISBN 978-5-8459-1794-2 (рус.) — страницы 1036–1041.
- Codeforces: Anti-hash test
