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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Метод хеширования)
(Добавлен пример строки когда алгоритм не работает)
Строка 42: Строка 42:
  
 
Изначальный подсчёт хешей выполняется за <tex>O(m)</tex>. В цикле всего <tex>n - m + 1</tex> итераций, каждая выполняется за <tex>O(1)</tex>. Итоговое время работы алгоритма <tex>O(n + m)</tex>.
 
Изначальный подсчёт хешей выполняется за <tex>O(m)</tex>. В цикле всего <tex>n - m + 1</tex> итераций, каждая выполняется за <tex>O(1)</tex>. Итоговое время работы алгоритма <tex>O(n + m)</tex>.
 +
 +
== Надёжность ==
 +
Если количество подстрок данной строки близко к количеству хешей, то наступление [[Разрешение_коллизий | коллизий]] очень вероятно. Но даже при относительно небольших строках возможны частые ложные срабатывания.
 +
 +
Например если взять <tex> r = 2^{32}, p = 237 </tex>, за <tex> s </tex> принять [[Слово_Туэ-Морса | строку Туэ-Морса]]<ref>[http://codeforces.ru/blog/entry/4898 Codeforces: Anti-hash test]</ref> длиной <tex> 1024 </tex> , то алгоритм находит лишние вхождения почти в половине случаев.
 +
 +
== Примечания ==
 +
<references>
 +
</references>
  
 
== Литература ==
 
== Литература ==
Строка 48: Строка 57:
 
==Ссылки==
 
==Ссылки==
 
*[[Наивный алгоритм поиска подстроки в строке]]
 
*[[Наивный алгоритм поиска подстроки в строке]]
 +
*[http://codeforces.ru/blog/entry/4898 Codeforces: Anti-hash test]
  
 
[[Категория:Алгоритмы и структуры данных]]
 
[[Категория:Алгоритмы и структуры данных]]
 
[[Категория:Поиск подстроки в строке]]
 
[[Категория:Поиск подстроки в строке]]
 
[[Категория: Хеширование]]
 
[[Категория: Хеширование]]

Версия 19:44, 6 мая 2014

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

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

Для решения задачи удобно использовать полиномиальный хеш, так его легко пересчитывать: [math]hash(s[1..n]) = (p^{n - 1} s[1] + ... + p^{0} s[n]) \bmod r[/math], где [math]p[/math] — это некоторое простое число, а [math]r[/math] — некоторое большое число, для уменьшения числа коллизий (обычно берётся [math]2^{32}[/math] или [math]2^{64}[/math], чтобы модуль брался автоматически при переполнении типов). Стоит обратить внимание, что если 2 строчки имеют одинаковый хэш, то они в большинстве таких случаев равны.

При удалении первого символа строки и добавлении символа в конец считать хеш новой строки при помощи хеша изначальной строки возможно за [math]O(1)[/math]:

[math]hash(s[i + 1..i + m - 1]) = (hash(s[i..i + m - 1]) - p^{m - 1} s[i]) \bmod r[/math].

[math]hash(s[i + 1..i + m]) = (p \cdot hash(s[i + 1..i + m - 1]) + s[i + m]) \bmod r[/math].

Получается : [math]hash(s[i + 1..i + m]) = (p \cdot hash(s[i..i + m - 1]) - p^{m} s[i] + s[i + m]) \bmod r[/math].

Следует учесть, что использующаяся здесь функция [math] \bmod [/math] - математический остаток от деления; если для хеша используется знаковый тип, то во избежание деления с остатком отрицательного числа к нему нужно добавлять [math] r [/math] умноженное на достаточно большое число.

Алгоритм

Алгоритм начинается с подсчета [math]hash(s[1..m])[/math] и [math]hash(p[1..m])[/math].

Для [math]i \in [1..n - m + 1][/math] вычисляется [math]hash(s[i..i + m - 1])[/math] и сравнивается с [math]hash(p[1..m])[/math]. Если они оказались равны, то образец [math]p[/math] скорее всего содержится в строке [math]s[/math] начиная с позиции [math]i[/math], хотя возможны и ложные срабатывания алгоритма. Если требуется свести такие срабатывания к минимуму или исключить вовсе, то применяют сравнение некоторых символов из этих строк, которые выбраны случайным образом, или применяют явное сравнение строк, как в наивном алгоритме поиска подстроки в строке. В первом случае проверка произойдет быстрее, но вероятность ложного срабатывания, хоть и небольшая, останется. Во втором случае проверка займет время, равное длине образца, но полностью исключит возможность ложного срабатывания.

Для ускорения работы алгоритма оптимально предпосчитать [math]p^{m}[/math].

Псевдокод

 RabinKarp (s[1..n], p[1..m])
      hp = hash(p[1..m])
      h = hash(s[1..m])
      for i = 1 to n - m + 1
           if h == hp
                answer.add(i)
           h = (p * h - p[math]^{m}[/math] * hash(s[i]) + hash(s[i + m])) mod r
           if h < 0
                h += r
      if answer.size() == 0
           return not found
      else
           return answer

Новый хеш [math]h[/math] был получен с помощью быстрого пересчёта. Для сохранения корректности алгоритма нужно считать, что [math]s[n + 1][/math] — пустой символ.

Время работы

Изначальный подсчёт хешей выполняется за [math]O(m)[/math]. В цикле всего [math]n - m + 1[/math] итераций, каждая выполняется за [math]O(1)[/math]. Итоговое время работы алгоритма [math]O(n + m)[/math].

Надёжность

Если количество подстрок данной строки близко к количеству хешей, то наступление коллизий очень вероятно. Но даже при относительно небольших строках возможны частые ложные срабатывания.

Например если взять [math] r = 2^{32}, p = 237 [/math], за [math] s [/math] принять строку Туэ-Морса[1] длиной [math] 1024 [/math] , то алгоритм находит лишние вхождения почти в половине случаев.

Примечания

Литература

Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — 2-е изд. — М.: Издательский дом «Вильямс», 2007. — С. 1296.

Ссылки