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

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

Алгоритм редко используется для поиска одиночного шаблона, но имеет значительную теоретическую важность и очень эффективен в поиске совпадений множественных шаблонов. Для текста длины n и шаблона длины m, его среднее время исполнения и лучшее время исполнения это O(n), но в (весьма нежелательном) худшем случае он имеет производительность O(nm), что является одной из причин того, почему он не слишком широко используется. Однако, алгоритм имеет уникальную особенность находить любую из k строк менее, чем за время O(n) в среднем, независимо от размера k.

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

Основной проблемой алгоритма является нахождение постоянной строки длины m, называемой образцом, в тексте длины n; например, нахождение строки "sun" в предложении "Hello sunshine in this vale of tears". Один из простейших алгоритмов для этой задачи просто ищет подстроку во всех возможных местах:

1 function NaiveSearch(string s[1..n], string sub[1..m])

2 for i from 1 to n

3 for j from 1 to m

4 if s[i+j-1] ≠ sub[j]

5 jump to next iteration of outer loop

6 return i

7 return not found

Этот алгоритм хорошо работает во многих практических случаях, но совершенно не эффективен например на поиске строки из 10000 "a", за которыми следует "b" в строке из 10 миллионов букв "a". В этом случае он показывает своё худшее время исполнения Θ(mn).

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

Вместо того, чтобы использовать более умный пропуск, А.Р.-К. пытается ускорить проверку эквивалентности образца с подстроками в тексте используя хэш-функцию. Хэш-функция — это функция, которая преобразует каждую строку в числовое значение, называемое хэш-значение; например, мы можем иметь hash("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 каждая, требуют время Ω(m). Однако, строки 2 и 3 исполняются только один раз, а строка 6 выполняется только в случае, когда хэш-значения совпадают, что не может произойти чаще, чем несколько раз. Строка 5 выполняется n раз, но всегда требует постоянного времени. Теперь рассмотрим вторую проблему: строку 8.

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

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

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

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

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

Ключом к производительности А.Р.-К. является эффективное вычисление хэш-значения последовательных подстрок текста. Одна популярная и эффективная кольцевая хэш-функция интерпретирует каждую подстроку как число в некоторой системе счисления, основание которой является большим простым числом. Например, если подстрока "hi" и основание системы счисления 101, хэш-значение будет 104 × 1011 + 105 × 1010 = 10609 (ASCII код 'h' — 104 и 'i' — 105)

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

Например, если мы имеем текст "abracadabra" и ищем образец длины 3, мы можем рассчитать хэш подстроки "bra" из хэша подстроки "abr" (предыдущая подстрока), вычитая число добавленное для первой буквы 'a' из "abr", т.е. 97 × 1012 (97 — ASCII для 'a' и 101 — основание, которое мы используем), умножение на основание и наконец добавляя последнее число для "bra", т.е. 97 × 1010 = 97. Если подстроки в запросе длинны, этот алгоритм достигает большой экономии сравнимо с многими другими схемами хэширования.

Теоретически, существуют другие алгоритмы, которые могут обеспечить сравнимый объём вычислений, например, умножая ASCII-значения всех символов, в результате сдвиг подстроки будет влечь за собой только деление на первый символ и умножение на последний. Ограничением, однако, является размер типа данных целого числа и необходимость использовать модульную арифметику для уменьшения результатов хэширования, см. статью хэш-функция; тем не менее, эти простые хэш-функции, которые быстро не производят большие числа, такие как просто добавление ASCII-кодов, наиболее вероятно генерируют большое количество хэш-коллизий и следовательно — замедляют алгоритм. Из этого следует, что описанная хэш-функция является предпочитаемой для алгоритма Рабина-Карпа. 

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

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

function RabinKarpSet(string s[1..n], set of string subs, m) {

set hsubs := emptySet

for each sub in subs

insert hash(sub[1..m]) into hsubs

hs := hash(s[1..m])

for i from 1 to n

if hs ∈ hsubs

if s[i..i+m-1] = a substring with hash hs

return i

hs := hash(s[i+1..i+m])

return not found

}

Здесь мы предполагаем, что все подстроки имеют фиксированную длину m, но это предположение может быть убрано. Мы просто сравниваем текущее хэш-значение c хэш-значениями всех подстрок одновременно, используя быстрый просмотр в нашей структуре данных множества, и затем проверяя любое совпадение, которое мы находим со всеми подстроками с этим хэш-значением.

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

Лит.: Karp and Rabin’s original paper: Karp, Richard M.; Rabin, Michael O. (March 1987). «Efficient randomized pattern-matching algorithms». IBM Journal of Research and Development 31 (2), 249—260. Томас Х. Кормен и др. Глава 32. Поиск подстрок // Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 0-07-013151-1.