Алгоритм Рабина – Карпа - Rabin–Karp algorithm

В информатике , то Рабина-Карпа алгоритм или алгоритм Карп-Рабина является строка-поиска алгоритм , созданный Ричардом М. Карп и Майкл О. Рабина  ( 1987 ) , который использует хеширования , чтобы найти точное совпадение узора строки в тексте. Он использует скользящий хэш, чтобы быстро отфильтровать позиции текста, которые не могут соответствовать шаблону, а затем проверяет совпадение в оставшихся позициях. Обобщения одной и той же идеи можно использовать для поиска более чем одного совпадения одного шаблона или для поиска совпадений для более чем одного шаблона.

Чтобы найти одно совпадение с одним шаблоном, ожидаемое время алгоритма является линейным по объединенной длине шаблона и текста, хотя его временная сложность наихудшего случая является произведением двух длин. Чтобы найти несколько совпадений, ожидаемое время линейно зависит от входных длин плюс суммарная длина всех совпадений, которая может быть больше линейной. Напротив, алгоритм Ахо – Корасика может найти все совпадения нескольких шаблонов во времени и пространстве наихудшего случая, линейно по входной длине и количеству совпадений (вместо общей длины совпадений).

Практическое применение алгоритма - обнаружение плагиата . Учитывая исходный материал, алгоритм может быстро искать в бумаге экземпляры предложений из исходного материала, игнорируя такие детали, как регистр и знаки препинания. Из-за обилия искомых строк алгоритмы поиска по одной строке непрактичны.

Обзор

Наивный алгоритм сопоставления строк сравнивает данный шаблон со всеми позициями в данном тексте. Каждое сравнение занимает время, пропорциональное длине шаблона, а количество позиций пропорционально длине текста. Следовательно, время наихудшего случая для такого метода пропорционально произведению двух длин. Во многих практических случаях это время можно значительно сократить, прервав сравнение в каждой позиции, как только будет обнаружено несоответствие, но эта идея не может гарантировать никакого ускорения.

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

Хеш-функция - это функция, которая преобразует каждую строку в числовое значение, называемое ее хеш-значением ; например, мы могли бы иметь hash("hello")=5. Если две строки равны, их хеш-значения также равны. Для хорошо спроектированной хеш-функции обратное верно в приблизительном смысле: неравные строки вряд ли будут иметь равные хеш-значения. Алгоритм Рабина-Карпа вычисляет в каждой позиции текста хэш-значение строки, начинающейся с этой позиции, с той же длиной, что и образец. Если это хеш-значение равно хеш-значению шаблона, он выполняет полное сравнение в этой позиции.

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

Алгоритм

Алгоритм такой, как показано:

function RabinKarp(string s[1..n], string pattern[1..m])
    hpattern := hash(pattern[1..m]);
    for i from 1 to n-m+1
        hs := hash(s[i..i+m-1])
        if hs = hpattern
            if s[i..i+m-1] = pattern[1..m]
                return i
    return not found

Строки 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]. Если это значение можно использовать для вычисления следующего значения хеш-функции за постоянное время, то вычисление последовательных значений хеш-функции будет быстрым.

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

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

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

Для хорошей производительности требуется хорошая функция хеширования для обнаруженных данных. Если хеширование плохое (например, создание одного и того же хеш-значения для каждого ввода), тогда строка 6 будет выполняться O ( n ) раз (т.е. на каждой итерации цикла). Поскольку посимвольное сравнение строк длиной m занимает O (m) времени, тогда весь алгоритм занимает время O ( mn ) в худшем случае .

Используемая хеш-функция

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

Например, если подстрока - "привет", база - 256, а простой модуль - 101, то хеш-значение будет

 [(104 × 256 ) % 101  + 105] % 101  =  65
 (ASCII of 'h' is 104 and of 'i' is 105)

'%' - это 'mod' или по модулю, или остаток после целочисленного деления, оператор


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

Например, если у нас есть текст «abracadabra» и мы ищем образец длины 3, хэш первой подстроки «abr» с использованием 256 в качестве основы и 101 в качестве основного модуля будет:

// ASCII a = 97, b = 98, r = 114. 
hash("abr") =  [ ( [ ( [  (97 × 256) % 101 + 98 ] % 101 ) × 256 ] %  101 ) + 114 ]   % 101   =  4


Затем мы можем вычислить хэш следующей подстроки, «bra», из хеш-значения «abr», вычитая число, добавленное для первой «a» строки «abr», то есть 97 × 256 2 , умножая на основание и добавляя для последнего а из «бюстгальтера», т.е. 97 × 256 0 . Вот так:

//           old hash   (-ve avoider)*   old 'a'   left base offset      base shift    new 'a'    prime modulus
hash("bra") =     [ ( 4   + 101         -  97 * [(256%101)*256] % 101 ) * 256         +    97 ] % 101              =  30

* (-ve escapeider) = "избежание потери значимости". Необходимо, если для расчетов используются целые числа без знака. Поскольку мы знаем все хеши для простого модуля $ p $, мы можем гарантировать отсутствие потери значимости, добавив p к старому хешу перед вычитанием значения, соответствующего старому 'a' (mod p).

последний '* 256' - это сдвиг вычитаемого хеша влево

хотя ((256% 101) * 256)% 101 совпадает с 256 2  % 101, чтобы избежать переполнения целочисленных максимумов, когда строка шаблона длиннее (например, 'Rabin-Karp' составляет 10 символов, 256 9 - смещение без модуляции ), базовое смещение длины шаблона предварительно вычисляется в цикле, модулируя результат на каждой итерации.


Если мы подбираем строку поиска "bra", используя аналогичный расчет хеш-функции ("abr"),

hash'("bra") =  [ ( [ ( [ ( 98 × 256) %101  + 114] % 101 ) × 256 ] % 101) + 97 ] % 101 = 30

Если рассматриваемые подстроки длинные, этот алгоритм обеспечивает большую экономию по сравнению со многими другими схемами хеширования.

Теоретически существуют другие алгоритмы, которые могут обеспечить удобный пересчет, например, умножение вместе значений ASCII всех символов так, чтобы смещение подстроки повлекло за собой только деление предыдущего хэша на значение первого символа, а затем умножение на новое значение последнего символа. Однако ограничением является ограниченный размер целочисленного типа данных и необходимость использования модульной арифметики для уменьшения результатов хеширования (см. Статью о хэш-функциях ). Между тем, наивные хеш-функции не создают быстро большие числа, но, как и добавление значений ASCII, могут вызвать множество хеш-коллизий и, следовательно, замедлить алгоритм. Следовательно, описанная хеш-функция обычно является предпочтительной в алгоритме Рабина – Карпа.

Поиск по нескольким образцам

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

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

function RabinKarpSet(string s[1..n], set of string subs, m):
    set hsubs := emptySet
    foreach sub in subs
        insert hash(sub[1..m]) into hsubs
    hs := hash(s[1..m])
    for i from 1 to n-m+1
        if hs  hsubs and s[i..i+m-1]  subs
            return i
        hs := hash(s[i+1..i+m])
    return not found

Мы предполагаем, что все подстроки имеют фиксированную длину m .

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

использованная литература

  • Карп, Ричард М .; Рабин, Майкл О. (март 1987 г.). «Эффективные алгоритмы рандомизированного сопоставления с образцом». Журнал исследований и разработок IBM . 31 (2): 249–260. CiteSeerX  10.1.1.86.9502 . DOI : 10.1147 / rd.312.0249 .
  • Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стейн, Клиффорд (2001-09-01) [1990]. «Алгоритм Рабина – Карпа». Введение в алгоритмы (2-е изд.). Кембридж, Массачусетс : MIT Press. С. 911–916. ISBN 978-0-262-03293-3.
  • Чандан, К. Сельчук; Сапино, Мария Луиза (2010). Управление данными для поиска мультимедиа . Издательство Кембриджского университета. С. 205–206. ISBN 978-0-521-88739-7. (для расширения фильтра Блума)
  • Еще одно объяснение

внешние ссылки