Алгоритм Рабина — Карпа

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

Алгоритм редко используется для поиска одиночного шаблона, но имеет значительную теоретическую важность и очень эффективен в поиске совпадений множественных шаблонов одинаковой длины. Для текста длины n и шаблона длины m его среднее и лучшее время исполнения равно 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». В этом случае он показывает своё худшее время исполнения Θ(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 затрачивают для исполнения время $\Omega (m)$ каждая. Однако строки 2 и 3 исполняются только один раз, а строка 6 выполняется только когда хеш-значения совпадают, что происходит нечасто. Строка 5 выполняется $n$ раз, но всегда требует постоянного времени.

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

Это достигается использованием так называемого кольцевого хеша. Самым простым примером кольцевого хеша является добавление значений каждого следующего символа в подстроке и последующее использование данной формулы для подсчёта каждого следующего хеш-значения за фиксированное время:

 s[i+1..i+m] = s[i..i+m-1] - s[i] + s[i+m]

Такая формула не даёт никаких гарантий нечастого возникновения коллизий, и действительно несложно убедиться, что в большинстве приложений при её использовании выражение в 6 строке будет выполняться чаще, чем при использовании других, более «умных» кольцевых хеш-функций.

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

Используемая хеш-функция

Ключами к производительности алгоритма Рабина — Карпа являются низкая вероятность коллизий и эффективное вычисление хеш-значения последовательных подстрок текста. Рабин и Карп предложили использовать так называемый полиномиальный хеш (хотя любой другой кольцевой хеш также подойдёт). Для данного шаблона $p[1..m]$ такой хеш определён следующим образом:

$hash(p[1..m])=\left(\sum _{i=1}^{m}p[i]x^{m-i}\right){\bmod {q}},$

где $q$ — некоторое простое число, а $x$ — число от $0$ до $q-1$. Хеш-значения последовательных подстрок $s[i..i+m-1]$ и $s[i+1..i+m]$ для полиномиального хеша вычисляются следующим образом (заметим, что для эффективности число $x^{m-1}{\bmod {q}}$ считается перед основной процедурой поиска алгоритма Рабина — Карпа):

$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}}$.

Например, пусть $x=101$, $q$ произвольно, и мы имеем текст «abracadabra» и ищем образец длины 3. Мы можем рассчитать хеш подстроки «bra» из хеша подстроки «abr» (предыдущая подстрока), вычитая число, добавленное для первой буквы 'a' из «abr», то есть $97\times 101^{2}$ ($97$ — ASCII для 'a'), умножая на основание $101$ и, наконец, добавляя последнее число для «bra», то есть $97\times 101^{0}=97$. Чтобы избежать переполнения целых чисел, в большинстве реализаций после каждой из этих четырёх операций (умножение при вычислении $97\times 101^{2}$ — это отдельная операция) нужно брать результат по модулю $q$.

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

Современная модификация полиномиального хеша, предложенная Дитзфелбингером и др., лишена этих недостатков. Отличие этого варианта в том, что простое число $q$ фиксируется, а число $x$ случайно выбирается из диапазона от $0$ до $q-1$ перед началом работы алгоритма (при этом $x$ совсем не обязательно должно быть простым). Доказано, что для такой хеш-функции вероятность коллизии при поиске шаблона в строке $s[1..n]$ при $q>n^{c}$ для какого-то $c>2$ не превосходит $1/n^{c-2}$, при естественном условии что $0\leq s[i]<q$ для всех $i=1,2,\ldots ,n$. Для ускорения модульной арифметики $q$ можно выбирать равным степени двойки минус один (так называемые простые числа Мерсенна): для 32-битовых машин лучше всего подходит $q=2^{31}-1$, для 64-битовых — $q=2^{61}-1$; взятие по модулю $q$ для таких значений $q$ вычисляется с помощью быстрых побитовых операций. Другой возможный выбор — значения $q=2^{32}-5$ или $q=2^{64}-59$, для которых тоже существуют быстрые алгоритмы взятия остатка от деления на $q$ (при этом диапазон допустимых значений $x$ немного сужают). Можно выбирать $x$ лишь один раз при старте программы, а затем использовать его во всех хешах.

Заблуждения о полиномиальном хеше

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

Имеет популярность следующая интерпретация полиномиального хеша: каждая строка представляется числом с основанием $x$ и затем это число берётся по модулю $q$. Такая интерпретация не добавляет ясности в природу эффективности данного хеша, в то время как интерпретация полиномиального хеша как собственно полинома с коэффициентами, равными значениям символов, достаточно просто приводит к доказательству малой вероятности коллизии при случайном выборе $x$: рассмотрим две различные строки $p_{1}[1..m]$ и $p_{2}[1..m]$; полиномиальные хеши этих строк равны тогда и только тогда, когда $\sum _{i=1}^{m}(p_{1}[i]-p_{2}[i])x^{m-i}\equiv 0{\pmod {q}}$; но из теоремы Безу следует, что нетождественный нулю полином $\sum _{i=1}^{m}(p_{1}[i]-p_{2}[i])x^{m-i}$ степени $m-1$ в поле вычетов по модулю $q$ ($q$ выбирается простым, именно чтобы превратить кольцо вычетов в поле) имеет не более $m-1$ корней, а значит, вероятность коллизии $p_{1}$ и $p_{2}$ при случайном выборе $x$ не превосходит $(m-1)/q$; поэтому если $q>n^{c}\geq m^{c}$ для какого-то $c>1$, вероятность коллизии двух различных строк длины $m$ не превосходит $(m-1)/q<n/q<1/n^{c-1}$ (отсюда, в частности, получается вероятность ошибки $1/n^{c-2}$ для поиска шаблона в строке).

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

Рабин — Карп и поиск множества образцов

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

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

 function RabinKarpSet(string s[1..n], set of string subs, m) {
     set hsubs := $\emptyset$
     for each sub in subs
         hsubs := hsubs $\cup$ {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 не найдено
 }

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

См. также

• Алгоритм Бойера — Мура
• Алгоритм Кнута — Морриса — Пратта
• Алгоритм Ахо — Корасик

Литература

• Кормен Т. Х., Лейзерсон Ч. Е., Ривест Р. Л., Штайн К. Алгоритмы: построение и анализ = Introduction to Algorithms / под ред. С. Н. Тригуба; пер. с англ. И. В. Красиков, Н. А. Орехов, В. Н. Романов. — 2-е изд. — М.: Вильямс, 2005. — 801 с. — ISBN 5-8459-0857-4.
• Rabin M. O., Karp R. M. Efficient randomized pattern-matching algorithms // IBM Journal of Research and Development. — IBM, 1987. — Т. 31, № 2. — С. 249–260. — doi:10.1147/rd.312.0249.
• Dietzfelbinger M., Gil J., Matias Y., Pippenger N. Polynomial hash functions are reliable // Proceedings of the 19th International Colloquium on Automata, Languages and Programming (ICALP'92). — London, UK: Springer-Verlag, 1992. — С. 235–246. — 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. — Berlin, Germany: Springer-Verlag, 2000. — С. 73–89. — doi:10.1007/3-540-45247-8_7.
• Pachocki J., Radoszewski J. Where to use and how not to use polynomial string hashing // Olympiads in Informatics. — Vilnus, Lithuania: Vilnus University, 2013. — Т. 7. — С. 90–100.