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

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

¶История

Алгоритм был предложен в 1987 году в статье «Randomized algorithms» (Michael O. Rabin, Richard M. Karp) как практическое применение хеширования для решения задачи поиска подстроки. В отличие от более ранних алгоритмов (например, алгоритма Кнута — Морриса — Пратта, 1977 год), Рабин и Карп сделали акцент на вероятностный подход: алгоритм использует хеш-функцию, которая может давать ложные срабатывания (коллизии), но при правильном выборе параметров вероятность ошибки пренебрежимо мала. Алгоритм стал одним из первых, где хеширование применялось для обработки строк, и оказал влияние на развитие методов поиска в биоинформатике, текстовых редакторах и системах обнаружения плагиата.

¶Принцип работы

¶Хеширование подстрок

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

Наиболее распространённая хеш-функция — полиномиальный хеш (также называемый хешем Рабина — Карпа). Для строки S длины m хеш вычисляется по формуле: \[ h(S) = (s_0 \cdot b^{m-1} + s_1 \cdot b^{m-2} + \dots + s_{m-1} \cdot b^0) \mod M \] где \( s_i \) — числовое значение символа (например, код ASCII), \( b \) — основание (обычно выбирается простое число, например 131 или 257), \( M \) — модуль (большое простое число, например \( 2^{64} \) в реализации с переполнением). При переходе от фрагмента \( T[i..i+m-1] \) к \( T[i+1..i+m] \) хеш обновляется: \[ h_{i+1} = (h_i - T[i] \cdot b^{m-1}) \cdot b + T[i+m] \mod M \]

¶Сравнение хешей

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

¶Псевдокод

`` function RabinKarp(text, pattern): n = length(text) m = length(pattern) if m > n: return [] hpattern = hash(pattern[0..m-1]) htext = hash(text[0..m-1]) for i from 0 to n-m: if htext == hpattern: if text[i..i+m-1] == pattern: // посимвольная проверка add i to result if i < n-m: htext = (htext - text[i] b^(m-1)) b + text[i+m] // скользящее хеширование return result ``

¶Характеристики

¶Временная сложность

• Средний случай: O(n + m) — при условии, что коллизии хешей редки, а посимвольные сравнения выполняются лишь для небольшого числа позиций.
• Худший случай: O(n·m) — если хеш-функция даёт много коллизий (например, когда все фрагменты текста имеют одинаковый хеш, что маловероятно при хорошей хеш-функции). На практике худший случай встречается редко.
• Лучший случай: O(n + m) — когда ни одно хеш-значение не совпадает с хешем образца, и посимвольные сравнения не выполняются.

¶Пространственная сложность

O(1) — алгоритм использует константный объём дополнительной памяти (несколько переменных для хранения хешей и степеней основания).

¶Вероятность коллизии

При правильном выборе модуля M (большое простое число) и основания b вероятность коллизии для двух различных строк длины m составляет примерно 1/M. Для M = \( 2^{64} \) (в реализации с 64-битным целочисленным переполнением) вероятность коллизии пренебрежимо мала. Однако при использовании модуля, не являющегося простым, или при переполнении целых чисел без модуля, коллизии могут возникать чаще.

¶Применение

Алгоритм Рабина — Карпа широко применяется в задачах, где требуется быстрый поиск подстроки в больших объёмах данных:

• Поиск в текстовых редакторах и поисковых системах: например, в утилите grep (реализация GNU grep использует алгоритм Рабина — Карпа для поиска по шаблонам фиксированной длины).
• Обнаружение плагиата: системы вроде MOSS (Measure Of Software Similarity) используют алгоритм для поиска совпадающих фрагментов кода.
• Биоинформатика: поиск коротких последовательностей ДНК или РНК в геноме (например, для поиска участков с определённым паттерном).
• Сжатие данных: в алгоритмах типа LZ77 и LZ78 для поиска повторяющихся фрагментов.
• Криптография: в некоторых протоколах аутентификации (например, для проверки целостности сообщений с помощью хешей).

¶Модификации

¶Алгоритм с несколькими образцами

Алгоритм Рабина — Карпа можно обобщить для поиска одновременно нескольких образцов (например, для поиска всех слов из словаря). Для этого используется хеш-таблица, в которую помещаются хеши всех образцов. При обработке текста для каждого фрагмента вычисляется хеш и проверяется его наличие в таблице. Если хеш найден, выполняется посимвольное сравнение с каждым образцом, имеющим такой же хеш. Средняя сложность остаётся O(n + m·k), где k — количество образцов.

¶Алгоритм с двумя хешами

Для снижения вероятности коллизий используется два независимых хеша (с разными модулями или основаниями). Совпадение считается достоверным только при совпадении обоих хешей, что уменьшает вероятность ложного срабатывания до 1/(M1·M2).

¶Алгоритм с хешированием по модулю степени двойки

В некоторых реализациях (например, в стандартной библиотеке Python для поиска подстроки) используется хеширование по модулю \( 2^{64} \) с переполнением целых чисел. Это упрощает вычисления, но может приводить к коллизиям при определённых входных данных (например, при длинных строках с повторяющимися символами).

¶Критика и ограничения

• Чувствительность к выбору хеш-функции: при неудачном выборе основания или модуля (например, когда основание и модуль не взаимно просты) алгоритм может давать большое количество коллизий, что ухудшает производительность до O(n·m).
• Необходимость посимвольной проверки: даже при совпадении хешей требуется полное сравнение строк, что может замедлять работу при большом числе ложных срабатываний.
• Ограничение на длину образца: при очень длинных образцах (например, более 10^6 символов) вычисление хешей может потребовать больших чисел, что выходит за пределы стандартных целочисленных типов. В таких случаях используют модульную арифметику с большими числами или альтернативные алгоритмы (например, алгоритм Кнута — Морриса — Пратта).
• Не подходит для поиска с регулярными выражениями: алгоритм работает только для точных совпадений подстрок фиксированной длины.

¶Сравнение с другими алгоритмами

¶Интересные факты

• Алгоритм Рабина — Карпа был одним из первых, где хеширование применялось для поиска строк, и до сих пор используется в учебных курсах по алгоритмам и структурам данных.
• В стандартной библиотеке языка Python (модуль re) для поиска по шаблонам фиксированной длины используется именно алгоритм Рабина — Карпа.
• В 1990-х годах алгоритм был адаптирован для поиска в сжатых данных без предварительной распаковки (алгоритм «сжатого поиска»).

¶Источники

• Michael O. Rabin, Richard M. Karp. «Randomized algorithms», 1987.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. «Introduction to Algorithms», 3rd edition, 2009.
• Donald E. Knuth. «The Art of Computer Programming», Volume 3: Sorting and Searching, 2nd edition, 1998.
• Статья «Rabin–Karp algorithm» в англоязычной Википедии (по состоянию на 2023 год).