В информатике алгоритм Рабина–Карпа или алгоритм Карпа–Рабина — это алгоритм поиска строк, созданный Ричардом М. Карпом и Майклом О. Рабином (1987), который использует хеширование для поиска точного совпадения строки шаблона в тексте. Он использует скользящий хеш для быстрой фильтрации позиций текста, которые не могут соответствовать шаблону, а затем проверяет наличие совпадений в оставшихся позициях. Обобщения той же идеи могут использоваться для поиска более одного совпадения одного шаблона или для поиска совпадений для более чем одного шаблона.
Чтобы найти одно совпадение одного шаблона, ожидаемое время алгоритма линейно по объединенной длине шаблона и текста, хотя его наихудшая временная сложность является произведением двух длин. Чтобы найти несколько совпадений, ожидаемое время линейно по длинам входных данных плюс объединенная длина всех совпадений, которая может быть больше линейной. Напротив, алгоритм Ахо–Корасика может найти все совпадения нескольких шаблонов в худшем случае по времени и пространству, линейным по длине входных данных и количеству совпадений (вместо общей длины совпадений).
Практическое применение алгоритма — обнаружение плагиата . При наличии исходного материала алгоритм может быстро искать в документе примеры предложений из исходного материала, игнорируя такие детали, как регистр и пунктуация. Из-за обилия искомых строк алгоритмы поиска по одной строке непрактичны.
Наивный алгоритм сопоставления строк сравнивает заданный шаблон со всеми позициями в заданном тексте. Каждое сравнение занимает время, пропорциональное длине шаблона, а количество позиций пропорционально длине текста. Следовательно, наихудшее время для такого метода пропорционально произведению двух длин. Во многих практических случаях это время можно значительно сократить, обрезая сравнение в каждой позиции, как только обнаруживается несоответствие, но эта идея не может гарантировать никакого ускорения.
Несколько алгоритмов сопоставления строк, включая алгоритм Кнута–Морриса–Пратта и алгоритм поиска строк Бойера–Мура , сокращают время сопоставления строк в худшем случае, извлекая больше информации из каждого несовпадения, что позволяет им пропускать позиции текста, которые гарантированно не соответствуют шаблону. Вместо этого алгоритм Рабина–Карпа достигает своего ускорения, используя хэш-функцию для быстрого выполнения приблизительной проверки для каждой позиции, а затем выполняя точное сравнение только в тех позициях, которые прошли эту приблизительную проверку.
Хэш-функция — это функция, которая преобразует каждую строку в числовое значение, называемое ее хэш-значением ; например, у нас может быть hash("hello")=5. Если две строки равны, их хэш-значения также равны. Для хорошо спроектированной хэш-функции обратное верно в приблизительном смысле: строки, которые не равны, вряд ли будут иметь одинаковые хэш-значения. Алгоритм Рабина–Карпа вычисляет в каждой позиции текста хэш-значение строки, начинающейся в этой позиции с той же длиной, что и шаблон. Если это хэш-значение равно хэш-значению шаблона, он выполняет полное сравнение в этой позиции.
Для того чтобы это работало хорошо, хэш-функция должна быть выбрана случайным образом из семейства хэш-функций, которые вряд ли дадут много ложных срабатываний , то есть позиций текста, которые имеют то же значение хэша, что и шаблон, но на самом деле не соответствуют шаблону. Эти позиции излишне увеличивают время работы алгоритма, не производя совпадения. Кроме того, используемая хэш-функция должна быть скользящей хэш-функцией , хэш-функцией, значение которой можно быстро обновлять от каждой позиции текста к следующей. Пересчет хэш-функции с нуля в каждой позиции будет слишком медленным.
Алгоритм выглядит следующим образом:
функция РабинКарп ( строка s [ 1. . n ], строка pattern [ 1. . m ]) hpattern := hash ( pattern [ 1. . m ]); для i от 1 до n - m + 1 hs := хэш ( s [ i .. i + m - 1 ]) если hs = hpattern если s [ i .. i + m - 1 ] = шаблон [ 1. . m ] вернуть я возврат не найденСтроки 2, 4 и 6 требуют O ( m ) времени каждая. Однако строка 2 выполняется только один раз, а строка 6 выполняется только в том случае, если значения хэша совпадают, что вряд ли произойдет больше нескольких раз. Строка 5 выполняется O( n ) раз, но каждое сравнение требует только постоянного времени, поэтому его влияние составляет O( n ). Проблема в строке 4.
Наивное вычисление хэш-значения для подстроки s[i+1..i+m]требует O ( m ) времени, поскольку каждый символ проверяется. Поскольку вычисление хэша выполняется в каждом цикле, алгоритм с наивным вычислением хэша требует O (mn) времени, той же сложности, что и простой алгоритм сопоставления строк. Для скорости хэш должен быть вычислен за постоянное время. Хитрость в том, что переменная hsуже содержит предыдущее хэш-значение s[i..i+m-1]. Если это значение можно использовать для вычисления следующего хэш-значения за постоянное время, то вычисление последующих хэш-значений будет быстрым.
Этот трюк можно использовать с помощью rolling hash . rolling hash — это хеш-функция, специально разработанная для этой операции. Тривиальная (но не очень хорошая) rolling hash-функция просто добавляет значения каждого символа в подстроке. Эта формула rolling hash может вычислить следующее значение хеша из предыдущего значения за постоянное время:
s[i+1..i+m] = s[i..i+m-1] - s[i] + s[i+m]
Эта простая функция работает, но приведет к тому, что оператор 5 будет выполняться чаще, чем другие более сложные функции хеширования, такие как те, которые обсуждаются в следующем разделе.
Хорошая производительность требует хорошей функции хеширования для встречающихся данных. Если хеширование плохое (например, выдает одно и то же значение хеширования для каждого ввода), то строка 6 будет выполнена O ( n ) раз (т. е. на каждой итерации цикла). Поскольку посимвольное сравнение строк длиной m занимает O ( m ) времени, весь алгоритм в худшем случае занимает O ( mn ) времени.
Ключ к производительности алгоритма Рабина–Карпа — эффективное вычисление хэш-значений последовательных подстрок текста. Отпечаток Рабина — популярная и эффективная скользящая хэш-функция. Описанная здесь хэш-функция не является отпечатком Рабина, но работает так же хорошо. Она рассматривает каждую подстроку как число в некоторой базе, причем база обычно равна размеру набора символов.
Например, если подстрока — «hi», основание — 256, а простой модуль — 101, то значение хэш-функции будет следующим:
[(104 × 256) % 101 + 105] % 101 = 65 ( ASCII-код «h» равен 104, а «i» равен 105)
'%' - это 'mod' или остаток от деления по модулю, оператор
Технически этот алгоритм похож только на истинное число в представлении недесятичной системы, поскольку, например, у нас может быть «основание» меньше одной из «цифр». Смотрите хэш-функцию для более подробного обсуждения. Существенное преимущество, достигаемое с помощью скользящего хеша, такого как отпечаток Рабина, заключается в том, что можно вычислить хэш-значение следующей подстроки из предыдущей, выполняя только постоянное количество операций, независимо от длины подстрок.
Например, если у нас есть текст «abracadabra» и мы ищем шаблон длиной 3, то хэш первой подстроки «abr», использующий 256 в качестве основания и 101 в качестве простого модуля, будет следующим:
// ASCII-символ a = 97, b = 98, r = 114.хэш("abr") = [ ( [ ( [ (97 × 256) % 101 + 98 ] % 101 ) × 256 ] % 101 ) + 114 ] % 101 = 4
Затем мы можем вычислить хэш следующей подстроки, «bra», из хеша «abr», вычитая число, добавленное для первой «a» в «abr», т. е. 97 × 256 2 , умножая на основание и прибавляя для последней «a» в «bra», т. е. 97 × 256 0 . Вот так:
// старый хэш (-ve Avoider)* старый 'a' левое смещение базы сдвиг базы новый 'a' простой модульхэш("бюстгальтер") = [ ( 4 + 101 - 97 * [(256%101)*256] % 101 ) * 256 + 97 ] % 101 = 30* (-ve Avoider) = "underflow Avoider". Необходимо, если для вычислений используются целые числа без знака. Поскольку мы знаем все хэши для простого модуля $p$, мы можем гарантировать отсутствие underflow, добавив p к старому хешу перед вычитанием значения, соответствующего старому 'a' (mod p).
последнее '* 256' — это сдвиг вычитаемого хеша влево
хотя ((256%101)*256)%101 то же самое, что и 256 2 % 101, чтобы избежать переполнения целочисленных максимумов, когда строка шаблона длиннее (например, «Рабин-Карп» состоит из 10 символов, 256 9 — это смещение без модуляции), базовое смещение длины шаблона предварительно вычисляется в цикле, модулируя результат на каждой итерации
Если мы сопоставляем строку поиска "bra", используя аналогичное вычисление хэша ("abr"),
хэш'("бра") = [ ( [ ( [ ( 98 × 256) %101 + 114] % 101 ) × 256 ] % 101) + 97 ] % 101 = 30Если рассматриваемые подстроки длинные, этот алгоритм обеспечивает значительную экономию по сравнению со многими другими схемами хеширования.
Теоретически существуют другие алгоритмы, которые могли бы обеспечить удобное перевычисление, например, умножение ASCII-значений всех символов так, чтобы сдвиг подстроки повлек за собой только деление предыдущего хеша на значение первого символа, а затем умножение на новое значение последнего символа. Однако ограничением является ограниченный размер целочисленного типа данных и необходимость использования модульной арифметики для уменьшения масштаба результатов хеша (см. статью о хеш-функциях ). Между тем, наивные хеш-функции не производят большие числа быстро, но, как и сложение ASCII-значений, могут вызвать много коллизий хеша и, следовательно, замедлить алгоритм. Поэтому описанная хеш-функция обычно является предпочтительной в алгоритме Рабина–Карпа.
Алгоритм Рабина–Карпа уступает алгоритму Кнута–Морриса–Пратта , алгоритму поиска строк Бойера–Мура и другим более быстрым алгоритмам поиска строк с одним шаблоном из-за его медленного поведения в худшем случае. Однако это полезный алгоритм для поиска нескольких шаблонов .
Чтобы найти любой из большого числа, скажем, k , шаблонов фиксированной длины в тексте, простой вариант алгоритма Рабина–Карпа использует фильтр Блума или заданную структуру данных для проверки того, принадлежит ли хэш заданной строки набору хэш-значений шаблонов, которые мы ищем:
функция RabinKarpSet ( строка s [ 1. . n ] , набор строковых подстановок , m ) : установить hsubs := пустойНабор foreach подпрограмма в подпрограммах вставить хэш ( sub [ 1. . m ]) в hsubs hs := хэш ( s [ 1. . m ]) для i от 1 до n - m + 1 если hs ∈ hsubs и s [ i .. i + m - 1 ] ∈ subs вернуть я hs := хэш ( s [ i + 1. . i + m ]) возврат не найденМы предполагаем, что все подстроки имеют фиксированную длину m .
Наивный способ поиска k шаблонов — повторить поиск одного шаблона, что займет O ( n+m ) времени, в сумме за O ( (n+m)k ) времени. Напротив, приведенный выше алгоритм может найти все k шаблонов за O ( n + km ) ожидаемого времени, предполагая, что проверка хэш-таблицы работает за O (1) ожидаемого времени.