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

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

Сорт	Строковый поиск
Худшая производительность	$O(mn)$ плюс $O(m)$ время предварительной обработки
Средняя производительность	$O(n)$
Наихудшая пространственная сложность	$O(1)$

В информатике алгоритм Рабина-Карпа или алгоритм Карпа-Рабина представляет собой алгоритм поиска строк, созданный Ричардом М. Карпом и Майклом О. Рабином ( 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 ).

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

Основная статья: Отпечаток пальца Рабина

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

Например, если подстрока — «hi», основание — 256, а простой модуль — 101, то значение хеш-функции будет равно

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

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

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

Например, если у нас есть текст «абракадабра» и мы ищем шаблон длиной 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. ² , умножая на основание и добавляя к последнему букву «бюстгальтер», т. е. 97 × 256. ⁰ . Вот так:

//           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 избегатель) = «предотвращение переполнения». Необходимо, если для вычислений используются целые числа без знака. Потому что мы знаем все хеши $h\leq p$ для простого модуля $p$ мы можем гарантировать отсутствие опустошения, добавив p к старому хешу перед вычитанием значения, соответствующего старому 'a' (mod p).}

_{последнее '*256' — это сдвиг вычитаемого хеша влево}

_{хотя ((256%101)*256)%101 то же самое, что 256 ² % 101, чтобы избежать переполнения целочисленных максимумов, когда строка шаблона длиннее (например, «Рабин-Карп» состоит из 10 символов, 256 ⁹ — смещение без модуляции), базовое смещение длины шаблона предварительно рассчитывается в цикле, модулируя результат на каждой итерации}

Если мы находим строку поиска «бюстгальтер», используя аналогичный расчет хеша («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).

Ссылки

Источники

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

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

• «Алгоритм Рабина – Карпа / Rolling Hash» (PDF) . MIT 6.006: Введение в алгоритмы 2011 — Конспекты лекций . Массачусетский технологический институт.