Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа — различия между версиями
Martoon (обсуждение | вклад) м (→Метод хеширования) |
м (rollbackEdits.php mass rollback) |
||
(не показаны 74 промежуточные версии 8 участников) | |||
Строка 2: | Строка 2: | ||
==Метод хеширования== | ==Метод хеширования== | ||
− | + | [[Наивный алгоритм поиска подстроки в строке]] работает за <tex>O\left(n^2\right)</tex> в худшем случае — слишком долго. Чтобы ускорить этот процесс, можно воспользоваться методом [[Хеш-таблица#Хеширование|хеширования]]. | |
+ | {{Определение | ||
+ | |definition = Пусть дана строка <tex>s[0..n-1]</tex>. Тогда '''полиномиальным хешем''' (англ. ''polynomial hash'') строки <tex>s</tex> называется число <tex>h = \mathrm{hash}(s[0..n-1]) = p^{0} s[0] + ... + p^{n - 1} s[n-1]</tex>, где <tex>p</tex> — некоторое простое число, а <tex>s[i]</tex> <tex>{-}</tex> код <tex>i</tex>-ого символа строки <tex>s</tex>. | ||
+ | }} | ||
+ | Проблему переполнения при вычислении хешей довольно больших строк можно решить так <tex>{-}</tex> считать хеши по модулю <tex>r=2^{64}</tex> (или <tex>2^{32}</tex>), чтобы модуль брался автоматически при переполнении типов. | ||
− | + | Для работы алгоритма потребуется считать хеш подстроки <tex>s[i..j]</tex>. Делать это можно следующим образом: | |
− | <tex> | + | Рассмотрим хеш <tex>s[0..j]</tex>: |
− | <tex>hash(s[ | + | <tex>\mathrm{hash}(s[0..j]) = s[0] + p s[1] +...+ p^{i-1} s[i-1] + p^{i} s[i] +...+ p^{j-1} s[j-1] + p^{j} s[j]</tex> |
− | + | Разобьем это выражение на две части: | |
− | + | <tex>\mathrm{hash}(s[0..j]) = (s[0] + p s[1] +...+ p^{i-1} s[i-1]) + (p^{i} s[i] +...+ p^{j-1} s[j-1] + p^{j} s[j])</tex> | |
− | + | Вынесем из последней скобки множитель <tex>p^{i}</tex>: | |
− | + | <tex>\mathrm{hash}(s[0..j]) = (s[0] + p s[1] +...+ p^{i-1} s[i-1]) + p^{i}(s[i] +...+ p^{j-i-1} s[j-1] + p^{j-i} s[j])</tex> | |
− | + | Выражение в первой скобке есть не что иное, как хеш подстроки <tex>s[0..i-1]</tex>, а во второй — хеш нужной нам подстроки <tex>s[i..j]</tex>. Итак, мы получили, что: | |
− | + | <tex>\mathrm{hash}(s[0..j]) = \mathrm{hash}(s[0..i-1]) + p^{i}\mathrm{hash}(s[i..j])</tex> | |
− | + | Отсюда получается следующая формула для <tex>\mathrm{hash}(s[i..j])</tex>: | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | + | <tex>\mathrm{hash}(s[i..j]) = (1/p^{i})(\mathrm{hash}(s[0..j]) - \mathrm{hash}(s[0..i-1]))</tex> | |
− | + | Однако, как видно из формулы, чтобы уметь считать хеш для всех подстрок начинающихся с <tex>i</tex>, нужно предпосчитать все <tex>p^{i}</tex> для <tex>i \in [0..n - 1]</tex>. Это займет много памяти. Но поскольку нам нужны только подстроки размером <tex>m</tex> <tex>{-}</tex> мы можем подсчитать хеш подстроки <tex>s[0..m-1]</tex>, а затем пересчитывать хеши для всех <tex>i \in [0..n - m]</tex> за <tex>O(1)</tex> следующим образом: | |
− | + | <tex>\mathrm{hash}(s[i + 1..i + m - 1]) = (\mathrm{hash}(s[i..i + m - 1]) - p^{m - 1} s[i]) \bmod r</tex>. | |
− | + | <tex>\mathrm{hash}(s[i + 1..i + m]) = (p \cdot \mathrm{hash}(s[i + 1..i + m - 1]) + s[i + m]) \bmod r</tex>. | |
− | |||
− | == | + | Получается : <tex>\mathrm{hash}(s[i + 1..i + m]) = (p \cdot \mathrm{hash}(s[i..i + m - 1]) - p^{i} s[i] + s[i + m]) \bmod r</tex>. |
+ | |||
+ | ==Решение== | ||
+ | |||
+ | ===Алгоритм=== | ||
+ | |||
+ | Алгоритм начинается с подсчета <tex>\mathrm{hash}(s[0..m-1])</tex> и <tex>\mathrm{hash}(p[0..m-1])</tex>, а также с подсчета <tex>p^{m}</tex>, для ускорения ответов на запрос. | ||
+ | |||
+ | Для <tex>i \in [0..n - m]</tex> вычисляется <tex>\mathrm{hash}(s[i..i + m - 1])</tex> и сравнивается с <tex>\mathrm{hash}(p[0..m-1])</tex>. Если они оказались равны, то образец <tex>p</tex> скорее всего содержится в строке <tex>s</tex> начиная с позиции <tex>i</tex>, хотя возможны и ложные срабатывания алгоритма. Если требуется свести такие срабатывания к минимуму или исключить вовсе, то применяют сравнение некоторых символов из этих строк, которые выбраны случайным образом, или применяют явное сравнение строк, как в [[Наивный алгоритм поиска подстроки в строке|наивном алгоритме поиска подстроки в строке]]. В первом случае проверка произойдет быстрее, но вероятность ложного срабатывания, хоть и небольшая, останется. Во втором случае проверка займет время, равное длине образца, но полностью исключит возможность ложного срабатывания. | ||
+ | |||
+ | Если требуется найти индексы вхождения нескольких образцов, или сравнить две строки <tex>{-}</tex> выгоднее будет предпосчитать все степени <tex>p</tex>, а также хеши всех префиксов строки <tex>s</tex>. | ||
+ | |||
+ | ===Псевдокод=== | ||
+ | Приведем пример псевдокода, который находит все вхождения строки <tex>w</tex> в строку <tex>s</tex> и возвращает массив позиций, откуда начинаются вхождения. | ||
+ | '''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<tex>^{m}</tex> * hash(s[i]) + hash(s[i + m])) '''mod''' r <font color=green>// r — некоторое большое число, p — некоторое просто число</font> | ||
+ | '''return''' answer | ||
+ | |||
+ | Новый хеш <tex>hashS</tex> был получен с помощью быстрого пересчёта. Для сохранения корректности алгоритма нужно считать, что <tex>s[n + 1]</tex> {{---}} пустой символ. | ||
+ | |||
+ | ===Время работы=== | ||
+ | |||
+ | Изначальный подсчёт хешей выполняется за <tex>O(m)</tex>. | ||
+ | |||
+ | Каждая итерация выполняется за <tex>O(1)</tex>, В цикле всего <tex>n - m + 1</tex> итераций. | ||
+ | |||
+ | Итоговое время работы алгоритма <tex>O(n + m)</tex>. | ||
+ | |||
+ | Однако, если требуется исключить ложные срабатывания алгоритма полностью, т.е. придется проверить все полученные позиции вхождения на истинность, то в худшем случае итоговое время работы алгоритма будет <tex>O(n</tex> <tex>\cdot</tex> <tex>m)</tex>. | ||
+ | |||
+ | == Сравнение с другими алгоритмами == | ||
+ | Преимущества: | ||
+ | * Быстрая скорость работы — <tex>O(n + m)</tex>, где <tex>n</tex> — длина строки, <tex>m</tex> — длина образца; | ||
+ | * Простая и понятная реализация; | ||
+ | |||
+ | Недостатки: | ||
+ | * Возможно подобрать входные данные так, что количество ложных срабатываний будет недопустимо большим; | ||
+ | |||
+ | == См. также == | ||
*[[Наивный алгоритм поиска подстроки в строке]] | *[[Наивный алгоритм поиска подстроки в строке]] | ||
+ | *[[Поиск наибольшей общей подстроки двух строк с использованием хеширования]] | ||
+ | |||
+ | == Источники информации == | ||
+ | * ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', 3-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2014. — 1328 с.: ил. — ISBN 978-5-8459-1794-2 (рус.) — страницы 1036–1041. | ||
[[Категория:Алгоритмы и структуры данных]] | [[Категория:Алгоритмы и структуры данных]] | ||
[[Категория:Поиск подстроки в строке]] | [[Категория:Поиск подстроки в строке]] | ||
[[Категория: Хеширование]] | [[Категория: Хеширование]] | ||
+ | [[Категория:Точный поиск]] |
Текущая версия на 19:28, 4 сентября 2022
Алгоритм Рабина-Карпа предназначен для поиска подстроки в строке.
Метод хеширования
Наивный алгоритм поиска подстроки в строке работает за в худшем случае — слишком долго. Чтобы ускорить этот процесс, можно воспользоваться методом хеширования.
Определение: |
Пусть дана строка | . Тогда полиномиальным хешем (англ. polynomial hash) строки называется число , где — некоторое простое число, а код -ого символа строки .
Проблему переполнения при вычислении хешей довольно больших строк можно решить так
считать хеши по модулю (или ), чтобы модуль брался автоматически при переполнении типов.Для работы алгоритма потребуется считать хеш подстроки
. Делать это можно следующим образом:Рассмотрим хеш
:
Разобьем это выражение на две части:
Вынесем из последней скобки множитель
:
Выражение в первой скобке есть не что иное, как хеш подстроки
, а во второй — хеш нужной нам подстроки . Итак, мы получили, что:
Отсюда получается следующая формула для
:
Однако, как видно из формулы, чтобы уметь считать хеш для всех подстрок начинающихся с
, нужно предпосчитать все для . Это займет много памяти. Но поскольку нам нужны только подстроки размером мы можем подсчитать хеш подстроки , а затем пересчитывать хеши для всех за следующим образом:.
.
Получается :
.Решение
Алгоритм
Алгоритм начинается с подсчета
и , а также с подсчета , для ускорения ответов на запрос.Для наивном алгоритме поиска подстроки в строке. В первом случае проверка произойдет быстрее, но вероятность ложного срабатывания, хоть и небольшая, останется. Во втором случае проверка займет время, равное длине образца, но полностью исключит возможность ложного срабатывания.
вычисляется и сравнивается с . Если они оказались равны, то образец скорее всего содержится в строке начиная с позиции , хотя возможны и ложные срабатывания алгоритма. Если требуется свести такие срабатывания к минимуму или исключить вовсе, то применяют сравнение некоторых символов из этих строк, которые выбраны случайным образом, или применяют явное сравнение строк, как вЕсли требуется найти индексы вхождения нескольких образцов, или сравнить две строки
выгоднее будет предпосчитать все степени , а также хеши всех префиксов строки .Псевдокод
Приведем пример псевдокода, который находит все вхождения строки
в строку и возвращает массив позиций, откуда начинаются вхождения.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
* hash(s[i]) + hash(s[i + m])) mod r // r — некоторое большое число, p — некоторое просто число
return answer
Новый хеш
был получен с помощью быстрого пересчёта. Для сохранения корректности алгоритма нужно считать, что — пустой символ.Время работы
Изначальный подсчёт хешей выполняется за
.Каждая итерация выполняется за
, В цикле всего итераций.Итоговое время работы алгоритма
.Однако, если требуется исключить ложные срабатывания алгоритма полностью, т.е. придется проверить все полученные позиции вхождения на истинность, то в худшем случае итоговое время работы алгоритма будет
.Сравнение с другими алгоритмами
Преимущества:
- Быстрая скорость работы — , где — длина строки, — длина образца;
- Простая и понятная реализация;
Недостатки:
- Возможно подобрать входные данные так, что количество ложных срабатываний будет недопустимо большим;
См. также
Источники информации
- Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд Алгоритмы: построение и анализ, 3-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2014. — 1328 с.: ил. — ISBN 978-5-8459-1794-2 (рус.) — страницы 1036–1041.