Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа — различия между версиями
(→Преимущества) |
|||
| Строка 79: | Строка 79: | ||
== Сравнение с другими алгоритмами == | == Сравнение с другими алгоритмами == | ||
=== Преимущества === | === Преимущества === | ||
| − | * Быстрая скорость работы — <tex>O(n + m)</tex>, где <tex>n</tex> | + | * Быстрая скорость работы — <tex>O(n + m)</tex>, где <tex>n</tex> — длина строки, <tex>m</tex> — длина образца. |
* Простая и понятная реализация. | * Простая и понятная реализация. | ||
| + | |||
=== Недостатки === | === Недостатки === | ||
* Возможно подобрать входные данные так, что количество ложных срабатываний будет недопустимо большим (см. Пример худшего случая). | * Возможно подобрать входные данные так, что количество ложных срабатываний будет недопустимо большим (см. Пример худшего случая). | ||
Версия 19:42, 15 июня 2015
Алгоритм Рабина-Карпа предназначен для поиска подстроки в строке.
Содержание
Метод хеширования
Наивный алгоритм поиска подстроки в строке работает за в худшем случае — слишком долго. Чтобы ускорить этот процесс, можно воспользоваться методом хеширования.
| Определение: |
| Пусть дана строка . Тогда полиномиальным хешем строки называется число , где — некоторое натуральное число, а - код -ого символа строки . |
Проблему переполнения при вычислении хешей довольно больших строк можно решить так: будем считать хеши по модулю — некоторому большому числу (будем брать , чтобы модуль брался автоматически при переполнении типов). Число для их подсчета должно быть, во-первых, больше кода самого большого символа в строках, а во-вторых, взаимно простым с модулем (в нашем случае — с , т.е. оно должно быть нечетным).
Использование полиномиального хеша именно с убывающими степенями позволяет нам, зная хеш некоторой строки, посчитать хеш строки, образованной удалением первого символа и добавлением символа в конец, за :
.
.
Получается : .
Решение
Алгоритм
Алгоритм начинается с подсчета и .
Для вычисляется и сравнивается с . Если они оказались равны, то образец скорее всего содержится в строке начиная с позиции , хотя возможны и ложные срабатывания алгоритма. Если требуется свести такие срабатывания к минимуму или исключить вовсе, то применяют сравнение некоторых символов из этих строк, которые выбраны случайным образом, или применяют явное сравнение строк, как в наивном алгоритме поиска подстроки в строке. В первом случае проверка произойдет быстрее, но вероятность ложного срабатывания, хоть и небольшая, останется. Во втором случае проверка займет время, равное длине образца, но полностью исключит возможность ложного срабатывания.
Для ускорения работы алгоритма оптимально предпосчитать .
Псевдокод
Приведем пример псевдокода, который находит все вхождения строки в строку и возвращает массив позиций, откуда начинаются вхождения.
vector<int> rabinKarp (s : string, w : string):
vector<int> answer
int n = s.length
int m = w.length
int hashS = hash(s[1..m])
int hashW = hash(w[1..m])
for i = 1 to n - m + 1
if hashS == hashW
answer.add(i)
hashS = (p * hashS - p * hash(s[i]) + hash(s[i + m])) mod r // r — некоторое большое число, p — некоторое просто число
return answer
Новый хеш был получен с помощью быстрого пересчёта. Для сохранения корректности алгоритма нужно считать, что — пустой символ.
Рекомендуется брать (чтобы модуль брался автоматически при переполнении типов), а - простое число, больше кода самого большого символа в строках.
Время работы
Изначальный подсчёт хешей выполняется за .
Каждая итерация выполняется за , В цикле всего итераций.
Итоговое время работы алгоритма .
Пример худшего случая
Если количество подстрок данной строки превышает количество хешей (а это выполняется тогда, когда длина строки больше , так как количество различных значений полиномиального хеша совпадает с ), то наступление коллизий неизбежно. Но даже при относительно небольших строках вероятность коллизий может быть высока, не говоря уже о способах составления специальных строк, где алгоритм на хешах выдаёт частые ложные срабатывания.
Например, возьмем за строку Туэ-Морса[1] длиной , , — любое просто число.
Обозначим за строку для фиксированного , а за инвертированную строку .
Покажем, что при , . Ведь если это так, то сами по себе и встретятся в больших строках много-много раз.
Разберемся, что значит . Можно смело заменить коды символов на нули и единицы в коэффициентах многочлена — тем самым мы просто сократим обе части на .
Что такое ? Нетрудно сообразить, что эта величина есть: . То есть это знакопеременная сумма степеней , где знаки чередуются по тому же правилу, что и символы в строке.
Будем последовательно выносить из этой суммы множители за скобку:
Покажем, что :
Нужно понять, на какую максимальную степень двойки делится каждая из скобок. Заметим, что -ая скобка делится на -ую и ещё на какое-то чётное число . Это означает, что если -ая скобка делится на , то -ая скобка делится по меньшей мере на .
Получается, что делится по меньшей мере на . Значит достаточно взять , чтобы в рассматриваемой строке было очень много различных подстрок, чьи хеши совпадут.
Сравнение с другими алгоритмами
Преимущества
- Быстрая скорость работы — , где — длина строки, — длина образца.
- Простая и понятная реализация.
Недостатки
- Возможно подобрать входные данные так, что количество ложных срабатываний будет недопустимо большим (см. Пример худшего случая).
См. также
- Наивный алгоритм поиска подстроки в строке
- Поиск наибольшей общей подстроки двух строк с использованием хеширования
Примечания
Источники информации
- Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд Алгоритмы: построение и анализ, 3-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2014. — 1328 с.: ил. — ISBN 978-5-8459-1794-2 (рус.) — страницы 1036–1041.
- Codeforces: Anti-hash test
