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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Надёжность)
м (rollbackEdits.php mass rollback)
 
(не показаны 44 промежуточные версии 6 участников)
Строка 2: Строка 2:
 
==Метод хеширования==
 
==Метод хеширования==
  
[[Наивный алгоритм поиска подстроки в строке]] работает за <tex>O\left(n^2\right)</tex> в худщем случае - слишком долго. Чтобы ускорить этот процесс, можно воспользоваться методом [[Хеш-таблица#Хеширование|хеширования]].
+
[[Наивный алгоритм поиска подстроки в строке]] работает за <tex>O\left(n^2\right)</tex> в худшем случае слишком долго. Чтобы ускорить этот процесс, можно воспользоваться методом [[Хеш-таблица#Хеширование|хеширования]].
 
{{Определение
 
{{Определение
|definition = Пусть дана строка <tex>s[1..n]</tex>. Тогда полиномиальным хешем строки <tex>s</tex> называется число <tex>h = \mathrm{hash}(s[1..n]) = p^{n - 1} s[1] + ... + p^{0} s[n]</tex>, где <tex>p</tex> - некоторое натуральное число, а <tex>s[i]</tex> - код <tex>i</tex>-ого символа строки <tex>s</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>r</tex> - некоторому большому числу (будем брать <tex>r =2^{64}</tex>, чтобы модуль брался автоматически при переполнении типов). Число <tex>p</tex> для их подсчета должно быть, во-первых, больше кода самого большого символа в строках, а во-вторых, взаимно простым с модулем (в нашем случае — с 2^{64}, т.е. оно должно быть нечетным).
+
Проблему переполнения при вычислении хешей довольно больших строк можно решить так <tex>{-}</tex> считать хеши по модулю <tex>r=2^{64}</tex> (или <tex>2^{32}</tex>), чтобы модуль брался автоматически при переполнении типов.
  
Использование полиномиального хеша именно с убывающими степенями <tex>p</tex> позволяет нам, зная хеш некоторой строки, посчитать хеш строки, образованной удалением первого символа и добавлением символа в конец, за <tex>O(1)</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>\mathrm{hash}(s[i + 1..i + m - 1]) = (\mathrm{hash}(s[i..i + m - 1]) - p^{m - 1} s[i]) \bmod r</tex>.
Строка 14: Строка 36:
 
<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 + 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^{m} s[i] + 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[1..m])</tex> и <tex>\mathrm{hash}(p[1..m])</tex>.
+
===Алгоритм===
  
Для <tex>i \in [1..n - m + 1]</tex> вычисляется <tex>\mathrm{hash}(s[i..i + m - 1])</tex> и сравнивается с <tex>\mathrm{hash}(p[1..m])</tex>. Если они оказались равны, то образец <tex>p</tex> скорее всего содержится в строке <tex>s</tex> начиная с позиции <tex>i</tex>, хотя возможны и ложные срабатывания алгоритма. Если требуется свести такие срабатывания к минимуму или исключить вовсе, то применяют сравнение некоторых символов из этих строк, которые выбраны случайным образом, или применяют явное сравнение строк, как в [[Наивный алгоритм поиска подстроки в строке|наивном алгоритме поиска подстроки в строке]]. В первом случае проверка произойдет быстрее, но вероятность ложного срабатывания, хоть и небольшая, останется. Во втором случае проверка займет время, равное длине образца, но полностью исключит возможность ложного срабатывания.  
+
Алгоритм начинается с подсчета <tex>\mathrm{hash}(s[0..m-1])</tex> и <tex>\mathrm{hash}(p[0..m-1])</tex>, а также с подсчета <tex>p^{m}</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> и возвращает массив позиций, откуда начинаются вхождения.
 
Приведем пример псевдокода, который находит все вхождения строки <tex>w</tex> в строку <tex>s</tex> и возвращает массив позиций, откуда начинаются вхождения.
 
  '''vector<int>''' rabinKarp (s : '''string''', w : '''string'''):
 
  '''vector<int>''' rabinKarp (s : '''string''', w : '''string'''):
Строка 30: Строка 54:
 
     '''int''' n = s.length
 
     '''int''' n = s.length
 
     '''int''' m = w.length
 
     '''int''' m = w.length
     '''int''' hashS = hash(s[1..m])
+
     '''int''' hashS = hash(s[0..m - 1])
     '''int''' hashW = hash(w[1..m])
+
     '''int''' hashW = hash(w[0..m - 1])
     '''for''' i = 1 '''to''' n - m + 1
+
     '''for''' i = 0 '''to''' n - m
 
         '''if''' hashS == hashW
 
         '''if''' hashS == hashW
 
               answer.add(i)
 
               answer.add(i)
Строка 40: Строка 64:
 
Новый хеш <tex>hashS</tex> был получен с помощью быстрого пересчёта. Для сохранения корректности алгоритма нужно считать, что <tex>s[n + 1]</tex> {{---}} пустой символ.
 
Новый хеш <tex>hashS</tex> был получен с помощью быстрого пересчёта. Для сохранения корректности алгоритма нужно считать, что <tex>s[n + 1]</tex> {{---}} пустой символ.
  
Рекомендуется брать <tex>r = 2^{64}</tex> (чтобы модуль брался автоматически при переполнении типов), а <tex>p</tex> - больше кода самого большого символа в строках.
+
===Время работы===
 
 
==Время работы==
 
  
 
Изначальный подсчёт хешей выполняется за <tex>O(m)</tex>.  
 
Изначальный подсчёт хешей выполняется за <tex>O(m)</tex>.  
Строка 50: Строка 72:
 
Итоговое время работы алгоритма <tex>O(n + m)</tex>.
 
Итоговое время работы алгоритма <tex>O(n + m)</tex>.
  
== Надёжность ==
+
Однако, если требуется исключить ложные срабатывания алгоритма полностью, т.е. придется проверить все полученные позиции вхождения на истинность, то в худшем случае итоговое время работы алгоритма будет <tex>O(n</tex> <tex>\cdot</tex> <tex>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 = 10</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>O(n + m)</tex>, где <tex>n</tex> — длина строки, <tex>m</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>2^{64}</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>. Значит достаточно взять <tex>k >= 12</tex>, чтобы в рассматриваемой строке было очень много различных подстрок, чьи хеши совпадут.
 
  
 
== См. также ==
 
== См. также ==
 
*[[Наивный алгоритм поиска подстроки в строке]]
 
*[[Наивный алгоритм поиска подстроки в строке]]
 
*[[Поиск наибольшей общей подстроки двух строк с использованием хеширования]]
 
*[[Поиск наибольшей общей подстроки двух строк с использованием хеширования]]
 
== Примечания ==
 
<references>
 
</references>
 
  
 
== Источники информации ==
 
== Источники информации ==
 
* ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', 3-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2014. — 1328 с.: ил. — ISBN 978-5-8459-1794-2 (рус.) — страницы 1036–1041.
 
* ''Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд'' '''Алгоритмы: построение и анализ''', 3-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2014. — 1328 с.: ил. — ISBN 978-5-8459-1794-2 (рус.) — страницы 1036–1041.
*[http://codeforces.ru/blog/entry/4898 Codeforces: Anti-hash test]
 
  
 
[[Категория:Алгоритмы и структуры данных]]
 
[[Категория:Алгоритмы и структуры данных]]
 
[[Категория:Поиск подстроки в строке]]
 
[[Категория:Поиск подстроки в строке]]
 
[[Категория: Хеширование]]
 
[[Категория: Хеширование]]
 +
[[Категория:Точный поиск]]

Текущая версия на 19:28, 4 сентября 2022

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

Метод хеширования

Наивный алгоритм поиска подстроки в строке работает за [math]O\left(n^2\right)[/math] в худшем случае — слишком долго. Чтобы ускорить этот процесс, можно воспользоваться методом хеширования.

Определение:
Пусть дана строка [math]s[0..n-1][/math]. Тогда полиномиальным хешем (англ. polynomial hash) строки [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]2^{32}[/math]), чтобы модуль брался автоматически при переполнении типов.

Для работы алгоритма потребуется считать хеш подстроки [math]s[i..j][/math]. Делать это можно следующим образом:

Рассмотрим хеш [math]s[0..j][/math]:

[math]\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][/math]

Разобьем это выражение на две части:

[math]\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])[/math]

Вынесем из последней скобки множитель [math]p^{i}[/math]:

[math]\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])[/math]

Выражение в первой скобке есть не что иное, как хеш подстроки [math]s[0..i-1][/math], а во второй — хеш нужной нам подстроки [math]s[i..j][/math]. Итак, мы получили, что:

[math]\mathrm{hash}(s[0..j]) = \mathrm{hash}(s[0..i-1]) + p^{i}\mathrm{hash}(s[i..j])[/math]

Отсюда получается следующая формула для [math]\mathrm{hash}(s[i..j])[/math]:

[math]\mathrm{hash}(s[i..j]) = (1/p^{i})(\mathrm{hash}(s[0..j]) - \mathrm{hash}(s[0..i-1]))[/math]

Однако, как видно из формулы, чтобы уметь считать хеш для всех подстрок начинающихся с [math]i[/math], нужно предпосчитать все [math]p^{i}[/math] для [math]i \in [0..n - 1][/math]. Это займет много памяти. Но поскольку нам нужны только подстроки размером [math]m[/math] [math]{-}[/math] мы можем подсчитать хеш подстроки [math]s[0..m-1][/math], а затем пересчитывать хеши для всех [math]i \in [0..n - m][/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^{i} 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]{-}[/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[/math] [math]\cdot[/math] [math]m)[/math].

Сравнение с другими алгоритмами

Преимущества:

  • Быстрая скорость работы — [math]O(n + m)[/math], где [math]n[/math] — длина строки, [math]m[/math] — длина образца;
  • Простая и понятная реализация;

Недостатки:

  • Возможно подобрать входные данные так, что количество ложных срабатываний будет недопустимо большим;

См. также

Источники информации

  • Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн Клиффорд Алгоритмы: построение и анализ, 3-е издание. Пер. с англ. — М.:Издательский дом "Вильямс", 2014. — 1328 с.: ил. — ISBN 978-5-8459-1794-2 (рус.) — страницы 1036–1041.