Просмотр кода страницы Алгоритм Рабина — Карпа

'''Алгоритм Рабина — Карпа''' — это алгоритм [[поиск подстроки|поиска строки]], который ищет шаблон, то есть подстроку, в тексте, используя [[хеширование]]. Он был разработан в [[1987 год]]у [[Рабин, Михаэль|Михаэлем Рабином]] и [[Карп, Ричард|Ричардом Карпом]]{{sfn|Rabin, Karp|1987}}.

Алгоритм редко используется для поиска одиночного шаблона, но имеет значительную теоретическую важность и очень эффективен в поиске совпадений множественных шаблонов одинаковой длины. Для текста длины ''n'' и шаблона длины ''m'' его среднее и лучшее время исполнения равно [[«O» большое и «o» малое|O]](''n'') при правильном выборе хеш-функции (смотрите ниже), но в худшем случае он имеет эффективность O(''nm''), что является одной из причин того, почему он не слишком широко используется. Для приложений, в которых допустимы ложные срабатывания при поиске, то есть, когда некоторые из найденных вхождений шаблона на самом деле могут не соответствовать шаблону, алгоритм Рабина — Карпа работает за гарантированное время O(''n'') и при подходящем выборе рандомизированной хеш-функции (смотрите ниже) вероятность ошибки можно сделать очень малой. Также алгоритм имеет уникальную особенность находить любую из заданных ''k'' строк одинаковой длины в среднем (при правильном выборе хеш-функции) за время O(''n'') независимо от размера ''k''.

Одно из простейших практических применений алгоритма Рабина — Карпа состоит в определении плагиата. Скажем, например, что студент пишет работу по ''[[Моби Дик]]у''. Коварный профессор находит различные исходные материалы по ''Моби Дику'' и автоматически извлекает список предложений в этих материалах. Затем алгоритм Рабина — Карпа может быстро найти в проверяемой статье примеры вхождения некоторых предложений из исходных материалов. Для устранения чувствительности алгоритма к небольшим различиям можно игнорировать детали, такие как [[ Чувствительность к регистру символов|регистр]] или [[пунктуация]], при помощи их удаления. Поскольку количество строк, которые мы ищем, ''k'', очень большое, обычные алгоритмы поиска одиночных строк становятся неэффективными.

== Поиск подстрок сдвигом и конкурирующие алгоритмы ==
Основной задачей алгоритма является нахождение строки длины ''m'', называемой ''образцом'', в тексте длины ''n''. Один из простейших алгоритмов для этой задачи просто ищет подстроку во всех возможных местах:

  '''1''' '''function''' NaiveSearch(''string'' s[1..n], ''string'' sub[1..m])
  '''2'''     '''for''' i '''from''' 1 '''to''' n-m+1
  '''3'''         '''for''' j '''from''' 1 '''to''' m
  '''4'''             '''if''' s[i+j-1] ≠ sub[j]
  '''5'''                 перейти к следующей итерации внешнего цикла
  '''6'''         '''return''' i
  '''7'''     '''return''' not found

Этот алгоритм хорошо работает во многих практических случаях, но совершенно неэффективен, например, на поиске строки из 10 тысяч символов «a», за которыми следует «b», в строке из 10 миллионов символов «a». В этом случае он показывает своё худшее время исполнения [[O-нотация|Θ]](''mn'').

[[Алгоритм Кнута — Морриса — Пратта]] уменьшает это время до Θ(''n''), единожды используя предвычисления для каждого символа текста; [[Алгоритм Бойера — Мура]] пропускает не один символ, а столько, сколько максимально возможно для того, чтобы поиск удался, эффективно уменьшая количество итераций через внешний цикл, поэтому количество символов, с которыми производится сравнение, может быть сравнимо с ''n/m'' в лучшем случае. Алгоритм Рабина — Карпа вместо этого фокусируется на ускорении действия строк 3-6, что будет рассмотрено в следующем разделе.

== Использование хеширования для поиска подстрок сдвигом ==
Вместо того, чтобы использовать более умный пропуск, алгоритм Рабина — Карпа пытается ускорить проверку эквивалентности образца с подстроками в тексте, используя [[хеш-функция|хеш-функцию]]. Хеш-функция — это функция, преобразующая каждую строку в числовое значение, называемое ''хеш-значением (хеш)''; например, мы можем иметь хеш от строки «hello» равным 5. Алгоритм использует тот факт, что если две строки одинаковы, то и их хеш-значения также одинаковы. Таким образом, всё, что нам нужно, это посчитать хеш-значение искомой подстроки и затем найти подстроку с таким же хеш-значением.

Однако существуют две проблемы, связанные с этим. Первая состоит в том, что, так как существует очень много различных строк, между двумя различными строками может произойти коллизия — совпадение их хешей. В таких случаях необходимо посимвольно проверять совпадение самих подстрок, что занимает достаточно много времени, если данные подстроки имеют большую длину (эту проверку делать не нужно, если ваше приложение допускает ложные срабатывания). При использовании достаточно хороших хеш-функций (смотрите далее) коллизии случаются крайне редко, и в результате среднее время поиска оказывается невелико.

Пример алгоритма (исходного кода приложения):

  '''1''' '''function''' RabinKarp(''string'' s[1..n], ''string'' sub[1..m])
  '''2'''     hsub := hash(sub[1..m])
  '''3'''     hs := hash(s[1..m])
  '''4'''     '''for''' i '''from''' 1 '''to''' (n-m+1)
  '''5'''         '''if''' hs = hsub
  '''6'''             '''if''' s[i..i+m-1] = sub
  '''7'''                 '''return''' i
  '''8'''         hs := hash(s[i+1..i+m])
  '''9'''     '''return''' not found

Строки 2, 3, и 6 затрачивают для исполнения время <math>\Omega(m)</math> каждая. Однако строки 2 и 3 исполняются только один раз, а строка 6 выполняется только когда хеш-значения совпадают, что происходит нечасто. Строка 5 выполняется <math>n</math> раз, но всегда требует постоянного времени.

Вторая проблема заключается в пересчитывании хеша. При наивном пересчёте хеш-значения подстроки <code>s[i+1..i+m]</code> затрачивается время <math>O(m)</math>, и, так как это делается в каждом цикле, алгоритм будет затрачивать время <math>\Omega(mn)</math>, то есть такое же, какое тратят и наиболее простые алгоритмы. Метод решения данной проблемы состоит в предположении того, что переменная <code>hs</code> уже содержит хеш-значение подстроки <code>s[i..i+m-1]</code>. Если использовать его для подсчёта следующего хеш-значения за постоянное время, тогда проблема будет решена.

Это достигается использованием так называемого [[кольцевой хеш|кольцевого хеша]]. Самым простым примером кольцевого хеша является добавление значений каждого следующего символа в подстроке и последующее использование данной формулы для подсчёта каждого следующего хеш-значения за фиксированное время:
  s[i+1..i+m] = s[i..i+m-1] - s[i] + s[i+m]
Такая формула не даёт никаких гарантий нечастого возникновения коллизий, и действительно несложно убедиться, что в большинстве приложений при её использовании выражение в 6 строке будет выполняться чаще, чем при использовании других, более «умных» кольцевых хеш-функций.

Заметим, что если мы очень неудачливы или имеем очень плохую хеш-функцию, например, такую, как постоянную функцию (hash=const), строка 6 с высокой вероятностью будет выполняться <math>n</math> раз, то есть при каждой итерации цикла. Так как она затрачивает время <math>\Omega(m)</math>, сам алгоритм будет требовать время <math>\Omega(mn)</math>.

== Используемая хеш-функция ==
Ключами к производительности алгоритма Рабина — Карпа являются низкая вероятность коллизий и эффективное вычисление [[хеш-функция|хеш-значения]] последовательных подстрок текста. Рабин и Карп{{sfn|Rabin, Karp|1987}} предложили использовать так называемый ''полиномиальный хеш'' (хотя любой другой [[кольцевой хеш]] также подойдёт). Для данного шаблона <math>p[1..m]</math> такой хеш определён следующим образом:
: <math>hash(p[1..m]) = \left(\sum_{i=1}^m p[i]x^{m-i}\right) \bmod q,</math>
где <math>q</math> — некоторое простое число, а <math>x</math> — число от <math>0</math> до <math>q-1</math>. Хеш-значения последовательных подстрок <math>s[i..i+m-1]</math> и <math>s[i+1..i+m]</math> для полиномиального хеша вычисляются следующим образом (заметим, что для эффективности число <math>x^{m-1} \bmod q</math> считается перед основной процедурой поиска алгоритма Рабина — Карпа):
: <math>hash(s[i+1..i+m]) = \left((hash(s[i..i+m-1]) - s[i]\cdot x^{m-1})\cdot x + s[i+m]\right) \bmod q</math>.
Например, пусть <math>x = 101</math>, <math>q</math> произвольно, и мы имеем текст «abracadabra» и ищем образец длины 3. Мы можем рассчитать хеш подстроки «bra» из хеша подстроки «abr» (предыдущая подстрока), вычитая число, добавленное для первой буквы 'a' из «abr», то есть <math>97\times 101^2</math> (<math>97</math> — ASCII для 'a'), умножая на основание <math>101</math> и, наконец, добавляя последнее число для «bra», то есть <math>97\times 101^0 = 97</math>. Чтобы избежать переполнения целых чисел, в большинстве реализаций после каждой из этих четырёх операций (умножение при вычислении <math>97\times 101^2</math> — это отдельная операция) нужно брать результат по модулю <math>q</math>.

Рабин и Карп доказали, что если <math>x=2</math> (то есть <math>x</math> фиксируется) и простое число <math>q</math> выбирается случайно из диапазона <math>[2..n^3]</math>, то вероятность коллизии при поиске шаблона в тексте длины <math>n</math> не превосходит <math>O(1/n)</math>. Но у такой хеш-функции два существенных недостатка: во-первых, алгоритм выбора случайного простого числа достаточно громоздкий, а во-вторых, модульная арифметика делает такой хеш очень медленным на практике (отметим, что вся арифметика в формуле для хешей последовательных подстрок должна быть по модулю <math>q</math>, то есть взятие модуля выполнится четыре раза).

Современная модификация полиномиального хеша, предложенная Дитзфелбингером и др.{{sfn|Dietzfelbinger, Gil, Matias, Pippinger|1992}}, лишена этих недостатков. Отличие этого варианта в том, что простое число <math>q</math> фиксируется, а число <math>x</math> случайно выбирается из диапазона от <math>0</math> до <math>q-1</math> перед началом работы алгоритма (при этом <math>x</math> совсем не обязательно должно быть простым). Доказано{{sfn|Dietzfelbinger, Gil, Matias, Pippinger|1992}}, что для такой хеш-функции вероятность коллизии при поиске шаблона в строке <math>s[1..n]</math> при <math>q > n^c</math> для какого-то <math>c > 2</math> не превосходит <math>1/n^{c-2}</math>, при естественном условии что <math>0 \le s[i] < q</math> для всех <math>i = 1,2,\ldots,n</math>. Для ускорения модульной арифметики <math>q</math> можно выбирать равным степени двойки минус один (так называемые простые [[числа Мерсенна]]): для 32-битовых машин лучше всего подходит <math>q = 2^{31}-1</math>, для 64-битовых — <math>q = 2^{61}-1</math>; взятие по модулю <math>q</math> для таких значений <math>q</math> вычисляется с помощью быстрых побитовых операций<ref name="Bit">S. E. Anderson. [https://graphics.stanford.edu/~seander/bithacks.html Bit twiddling hacks.] {{Wayback|url=https://graphics.stanford.edu/~seander/bithacks.html |date=20200601123740 }}</ref>. Другой возможный выбор — значения <math>q = 2^{32} - 5</math> или <math>q = 2^{64} - 59</math>, для которых тоже существуют быстрые алгоритмы взятия остатка от деления на <math>q</math>{{sfn|Krovetz, Rogaway|2000}} (при этом диапазон допустимых значений <math>x</math> немного сужают). Можно выбирать <math>x</math> лишь один раз при старте программы, а затем использовать его во всех хешах.

=== Заблуждения о полиномиальном хеше ===
Ещё раз отметим, что предоставляемые полиномиальным хешем гарантии отсутствия коллизий весьма сильны: даже если кто-то, зная <math>q</math>, но не зная <math>x</math>, специально будет подбирать шаблон и строку длины <math>n</math> для поиска так, чтобы алгоритм Рабина — Карпа с полиномиальным хешем давал как можно больше коллизий, всё равно, при <math>q > n^c</math> для какого-то <math>c > 2</math> (то есть при достаточно большом <math>q</math> и не сверхбольшом <math>n</math>) и если <math>x</math> выбирается действительно случайно, вероятность даже одной коллизии будет не больше <math>1 / n^{c-2}</math>, то есть очень мала. Для достижения этого результат важно, что <math>q</math> является простым числом. Например, частая ошибка — полагать <math>q = 2^{32}</math> или <math>q = 2^{64}</math> (то есть вообще не использовать модульную арифметику); примером строки, в которой можно найти много коллизий полиномиального хеша для таких <math>q = 2^k</math>, причём независимо от выбора числа <math>x</math>, является [[последовательность Морса — Туэ]].{{sfn|Pachocki, Radoszewski|2013}}

Имеет популярность следующая интерпретация полиномиального хеша: каждая строка представляется числом с основанием <math>x</math> и затем это число берётся по модулю <math>q</math>. Такая интерпретация не добавляет ясности в природу эффективности данного хеша, в то время как интерпретация полиномиального хеша как собственно ''[[Многочлен|полинома]]'' с коэффициентами, равными значениям символов, достаточно просто приводит к доказательству малой вероятности коллизии при случайном выборе <math>x</math>{{sfn|Dietzfelbinger, Gil, Matias, Pippinger|1992}}: рассмотрим две различные строки <math>p_1[1..m]</math> и <math>p_2[1..m]</math>; полиномиальные хеши этих строк равны тогда и только тогда, когда <math>\sum_{i=1}^m (p_1[i] - p_2[i])x^{m-i} \equiv 0 \pmod{q}</math>; но из теоремы Безу [[Многочлен над конечным полем#Корни многочлена|следует]], что нетождественный нулю полином <math>\sum_{i=1}^m (p_1[i] - p_2[i])x^{m-i}</math> степени <math>m-1</math> в [[Конечное поле#Поле с простым числом элементов и связь с кольцами вычетов|поле вычетов по модулю <math>q</math>]] (<math>q</math> выбирается простым, именно чтобы превратить [[кольцо вычетов]] в поле) имеет не более <math>m-1</math> корней, а значит, вероятность коллизии <math>p_1</math> и <math>p_2</math> при случайном выборе <math>x</math> не превосходит <math>(m-1)/q</math>; поэтому если <math>q > n^c \ge m^c</math> для какого-то <math>c > 1</math>, вероятность коллизии ''двух'' различных строк длины <math>m</math> не превосходит <math>(m-1)/q < n/q < 1/n^{c-1}</math> (отсюда, в частности, получается вероятность ошибки <math>1/n^{c-2}</math> для поиска шаблона в строке).

Также иногда можно встретить рекомендацию использовать простое число в качестве <math>x</math>, но, по-видимому, кроме эмпирических наблюдений на некоторых весьма ограниченных объёмах данных такие советы ничем более не обоснованы.

== Рабин — Карп и поиск множества образцов ==
Из-за медленного поведения в худшем случае алгоритм Рабина — Карпа хуже [[алгоритм Кнута — Морриса — Пратта|алгоритма Кнута — Морриса — Пратта]], [[алгоритм Бойера — Мура|алгоритма Бойера — Мура]] и других быстрых алгоритмов [[поиск подстроки|поиска строк]]. Тем не менее, алгоритм Рабина — Карпа можно использовать для поиска набора образцов за линейное время в лучшем случае и квадратичное в труднодостижимом худшем случае; хотя и здесь он проигрывает в худшем случае [[Алгоритм Ахо-Корасик|алгоритму Ахо — Корасик]], имеющему линейное время работы.

Если мы хотим найти в данном тексте любой образец из большого набора, скажем, ''k'' образцов фиксированной одинаковой длины, мы можем модифицировать алгоритм Рабина — Карпа, используя [[хеш-таблица|хеш-таблицу]] или любую другую [[Множество (тип данных)|структуру данных]] для проверки того, что хеш данной строки принадлежит набору хеш-значений образцов, которые мы ищем:

  '''function''' RabinKarpSet(''string'' s[1..n], ''set'' of ''string'' subs, m) {
      ''set'' hsubs := <math>\varnothing</math>
      '''for each''' sub '''in''' subs
          hsubs := hsubs <math>\cup</math> {hash(sub[1..m])}
      hs := hash(s[1..m])
      '''for''' i '''from''' 1 '''to''' (n-m+1)
          '''if''' hs ∈ hsubs
              '''if''' s[i..i+m-1] = string из subs с хешем hs
                  '''return''' i
          hs := hash(s[i+1..i+m])
      '''return''' не найдено
  }

<!-- //совершенно неясно как можно убрать это предположение. совсем недавно были работы на эту тему, но решения там совсем непростые (см. «Approximating LZ77 via Small-Space Multiple-Pattern Matching»).
Здесь мы предполагаем, что все подстроки имеют фиксированную длину ''m'', но это предположение может быть убрано. Мы просто сравниваем текущее хеш-значение c хеш-значениями всех подстрок одновременно, используя быстрый просмотр в нашей структуре данных множества, и затем проверяя любое совпадение, которое мы находим со всеми подстроками с этим хеш-значением.
-->

Другие алгоритмы могут искать одиночный образец за время O(''n''), и следовательно, они могут быть использованы для поиска ''k'' образцов за время O(''n'' ''k''). В противоположность им, вариант алгоритма Рабина — Карпа выше может найти все ''k'' образцов за ожидаемое время O(''n''+''k''), потому что хеш-таблица, используемая для проверки случая, когда хеш подстроки равен хешу любого из образцов, использует O(1) времени. На практике из-за относительной простоты реализации и быстроты работы этот вариант нередко может оказаться предпочтительнее [[Алгоритм Ахо-Корасик|алгоритма Ахо — Корасик]].

== См. также ==
* [[Алгоритм Бойера — Мура]]
* [[Алгоритм Кнута — Морриса — Пратта]]
* [[Алгоритм Ахо — Корасик]]

== Примечания ==
{{Примечания}}

== Литература ==
* {{книга
  |автор=[[Кормен, Томас|Кормен Т. Х.]], [[Лейзерсон, Чарльз|Лейзерсон Ч. Е.]], [[Ривест, Рональд|Ривест Р. Л.]], [[Штайн, Клиффорд|Штайн К.]]
  |заглавие= [[Алгоритмы: построение и анализ]]
  |оригинал=Introduction to Algorithms
  |год=2005
  |страниц=801
  |место=М.
  |издательство= Вильямс
  |isbn=5-8459-0857-4
  |издание=2-е изд
  |ответственный=под ред. {{nobr|С. Н. Тригуба}}; пер. с англ. {{nobr|И. В. Красиков}}, {{nobr|Н. А. Орехов}}, {{nobr|В. Н. Романов}}
  |ref=Кормен, Лейзерсон, Ривест, Штайн
}}
* {{статья
  |автор=[[Рабин, Майкл Озер|Rabin M. O.]], [[Карп, Ричард|Karp R. M.]]
  |заглавие= Efficient randomized pattern-matching algorithms
  |издание= [[:en:IBM Journal of Research and Development|IBM Journal of Research and Development]]
  |издательство=IBM
  |номер=2
  |том=31
  |страницы=249–260
  |год=1987
  |ref=Rabin, Karp
  |doi=10.1147/rd.312.0249
}}
* {{статья
  |автор=Dietzfelbinger M., Gil J., Matias Y., [[:en:Nick Pippenger|Pippenger N.]]
  |заглавие= Polynomial hash functions are reliable
  |издание= Proceedings of the 19th [[:en:International Colloquium on Automata, Languages and Programming|International Colloquium on Automata, Languages and Programming (ICALP'92)]]
  |издательство= Springer-Verlag
  |место= London, UK
  |страницы=235–246
  |год=1992
  |ref=Dietzfelbinger, Gil, Matias, Pippinger
  |doi=10.1007/3-540-55719-9_77
}}
* {{статья
  |автор=Krovetz T., Rogaway P.
  |заглавие= Fast universal hashing with small keys and no preprocessing: the PolyR construction
  |издание= Proceedings of the  International Conference on Information Security and Cryptology
  |издательство= Springer-Verlag
  |место= Berlin, Germany
  |страницы=73–89
  |год=2000
  |ref=Krovetz, Rogaway
  |doi=10.1007/3-540-45247-8_7
}}
* {{статья
  |автор=Pachocki J., Radoszewski J.
  |заглавие= [https://www.mii.lt/olympiads_in_informatics/pdf/INFOL119.pdf Where to use and how not to use polynomial string hashing]
  |издание= Olympiads in Informatics
  |издательство= Vilnus University
  |место= Vilnus, Lithuania
  |страницы=90–100
  |том=7
  |год=2013
  |ref=Pachocki, Radoszewski
}}
{{Строки}}
[[Категория:Поиск подстроки|Рабина — Карпа]]
[[Категория:Сопоставление с образцом|Рабина — Карпа]]
[[Категория:Хеширование]]