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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Алгоритм Рабина — Карпа — это алгоритм поиска строки, который ищет шаблон, то есть подстроку, в тексте, используя хеширование. Он был разработан в 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-m+1
 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

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

Вторая проблема заключается в пересчитывании хэша. При наивном пересчёте хэш-значения подстроки 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) времени.

Литература[править | править вики-текст]