Алгоритм Рабина — Карпа
Материал из Википедии — свободной энциклопедии
Алгоритм Рабина—Карпа — это алгоритм поиска строки, который ищет шаблон, то есть подстроку, в тексте используя хеширование. Он не широко используется для поиска одиночного шаблона, но имеет значительную теоретическую важность и очень эффективен в поиске совпадений множественных шаблонов. Для текста длины 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 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
