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

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

Вторая проблема заключается в пересчитывании хеша. При наивном пересчёте хеш-значения подстроки s[i+1..i+m] затрачивается время ${\displaystyle O(m)}$, и, так как это делается в каждом цикле, алгоритм будет затрачивать время ${\displaystyle \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 с высокой вероятностью будет выполняться ${\displaystyle n}$ раз, то есть при каждой итерации цикла. Так как она затрачивает время ${\displaystyle \Omega (m)}$, сам алгоритм будет требовать время ${\displaystyle \Omega (mn)}$.

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

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

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

${\displaystyle 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}}}$.

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

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

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

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

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

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