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

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

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

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

Обзор

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

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

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

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

Алгоритм

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

1 функция РабинКарп(строка s[1..п], строка шаблон[1..м])2     шаблон := хэш(шаблон[1..м]);3     для я от 1 к п-м+14         hs := хэш(s[я..я+м-1])5         если hs = шаблон6             если s[я..я+м-1] = шаблон[1..м]7                 вернуть я8     вернуть не найденный

Строки 2, 4 и 6 требуют О (м) время. Однако строка 2 выполняется только один раз, а строка 6 выполняется только в случае совпадения значений хеш-функции, что вряд ли произойдет более чем несколько раз. Строка 5 выполняется O (п) раз, но каждое сравнение требует только постоянного времени, поэтому его влияние составляет O (п). Проблема в строке 4.

Наивное вычисление хеш-значения для подстроки s [i + 1..i + m] требует О (м) раз, потому что проверяется каждый символ. Поскольку вычисление хэша выполняется в каждом цикле, алгоритм с простым вычислением хэша требует О (mn) время, та же сложность, что и простые алгоритмы сопоставления строк. Для скорости хэш должен вычисляться за постоянное время. Хитрость в переменной hs уже содержит предыдущее хеш-значение s [i..i + m-1]. Если это значение можно использовать для вычисления следующего хеш-значения за постоянное время, то вычисление последовательных хеш-значений будет быстрым.

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

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

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

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

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

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

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

Например, если подстрока - "привет", база - 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. hash ("abr") = [([([(97 × 256)% 101 + 98]% 101) × 256]% 101) + 114]% 101 = 4


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

//           старый хэш (-ve escape) * старый 'a' смещение влево смещение базы новый 'a'    простой модуль хеш ("бюстгальтер") = [(4 + 101 - 97 * [(256% 101) * 256]% 101) * 256 + 97]% 101 = 30

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

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

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


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

hash '("бюстгальтер") = [([([(98 × 256)% 101 + 114]% 101) × 256]% 101) + 97]% 101 = 30

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

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

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

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

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

 1 функция RabinKarpSet(строка s[1..п], набор из строка подводные лодки, м): 2     набор hsubs := пустой набор 3     для каждого суб в подводные лодки 4         вставить хэш(суб[1..м]) в hsubs 5     hs := хэш(s[1..м]) 6     для я от 1 к п-м+1 7         если hs ∈ hsubs и s[я..я+м-1] ∈ подводные лодки 8             вернуть я 9         hs := хэш(s[я+1..я+м])10     вернуть не найденный

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

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

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

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

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