Изменения

Перейти к: навигация, поиск

Поиск подстроки в строке с использованием хеширования. Алгоритм Рабина-Карпа

1788 байт добавлено, 07:53, 8 октября 2020
Нет описания правки
[[Наивный алгоритм поиска подстроки в строке]] работает за <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>s[0..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>\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>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>p^{m}</tex>. Однако, если Если требуется, например, найти индексы вхождения нескольких образцов, или, сравнить две строки <tex>{-}</tex> выгоднее будет предпосчитать все степени <tex>p</tex>, а также хеши всех префиксов строки <tex>s</tex>.
===Псевдокод===
'''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
Итоговое время работы алгоритма <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> — длина образца.;* Простая и понятная реализация.;
=== Недостатки ===:* Возможно подобрать входные данные так, что количество ложных срабатываний будет недопустимо большим (см. Пример худшего случая).;
== См. также ==
*[[Наивный алгоритм поиска подстроки в строке]]
*[[Поиск наибольшей общей подстроки двух строк с использованием хеширования]]
 
== Примечания ==
<references>
</references>
== Источники информации ==
* ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', 3-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2014. — 1328 с.: ил. — ISBN 978-5-8459-1794-2 (рус.) — страницы 1036–1041.
*[http://codeforces.ru/blog/entry/4898 Codeforces: Anti-hash test]
[[Категория:Алгоритмы и структуры данных]]
[[Категория:Поиск подстроки в строке]]
[[Категория: Хеширование]]
[[Категория:Точный поиск]]
Анонимный участник
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/48536...75084»

Навигация