Алгоритм Рабина-Карпа: Поиск подстрок с помощью кольцевого хеширования
Задача поиска подстроки (паттерна) в большом тексте имеет множество решений. В то время как алгоритм Кнута-Морриса-Пратта (КМП) строит сложный префиксный автомат, Майкл Рабин и Ричард Карп в 1987 году подошли к проблеме с совершенно другой, алгебраической стороны. Они применили технику хеширования, создав изящный алгоритм, который до сих пор является стандартом для поиска плагиата в системах вроде Антиплагиат.
Идея алгоритма Рабина-Карпа очень проста: вместо посимвольного сравнения паттерна с каждым окном текста, мы вычисляем хеш от паттерна, а затем последовательно вычисляем хеш от каждого окна текста (длиной в паттерн). Если хеши совпали — мы проверяем строку посимвольно (чтобы исключить коллизии). Если хеши разные — строки точно не совпадают, и мы смещаем окно.
Однако вычисление обычного криптографического хеша (типа MD5) или суммы символов для каждого сдвинутого окна с нуля займет слишком много времени, превратив алгоритм в O(N*M). Гениальность метода кроется в использовании Кольцевого хеша (Rolling Hash) — математической функции, которая умеет "вычитать" старый символ, выпавший из окна слева, и "прибавлять" новый символ, вошедший в окно справа, за константное время O(1).
Математически, строка рассматривается как число в позиционной системе счисления по некоторому основанию B (обычно это простое число, равное размеру алфавита), а вычисления ведутся по большому простому модулю Q (чтобы число помещалось в регистр процессора). Полиномиальный хеш для окна рассчитывается так:
H = (c1*B^(m-1) + c2*B^(m-2) + ... + cm*B^0) mod Q
Когда окно сдвигается на одну позицию вправо (выпадает символ c1 и добавляется новый символ c_new), новый хеш пересчитывается мгновенно по формуле:
H_new = ( (H - c1*B^(m-1)) * B + c_new ) mod Q
Всего две операции умножения, одно сложение и вычитание — и мы получаем хеш следующего слова! Это обеспечивает алгоритму среднее время работы O(N + M).
Но почему алгоритм Рабина-Карпа так популярен в поиске плагиата, если КМП работает так же быстро в худшем случае? Ответ: Масштабируемость для множественного поиска. Если вам нужно найти в тексте не один паттерн, а 100 000 разных слов одновременно (как при проверке статьи на заимствования из сотен источников), КМП потребует построения гигантских автоматов. Алгоритм Рабина-Карпа решает это элегантно: он заранее вычисляет хеши для всех 100 000 искомых слов и складывает их в фильтр Блума или хеш-таблицу. Затем он просто один раз "катится" по проверяемому тексту кольцевым хешем, мгновенно проверяя, не совпал ли текущий блок с одним из 100 000 искомых фрагментов. Сложность поиска множества паттернов практически равна сложности поиска одного паттерна!
