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

Модуль "Поиск" • урок 5 из 7 • ~10 минут

Алгоритм Рабина-Карпа и скользящий хеш

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

Возьмем сквозной пример модуля: ищем образец ABABAC в тексте ABABADABABAC, считая буквам веса A = 1, B = 2, C = 3, D = 4 при основании 10 и модуле 199. Хеш первого окна ABABAD равен 23, второго окна BABADA - 7.

Но если бы мы считали хеш-сумму каждого нового текстового окна "с нуля", алгоритм работал бы так же медленно, как наивный O(N·M). Секрет скорости Рабина-Карпа - скользящий (кольцевой) хеш. Когда окно смещается по тексту на один символ вправо, из старого хеша математически вычитается влияние самого первого (выпавшего) символа, и прибавляется влияние нового символа. Этот пересчет занимает константное время O(1).

Откуда взяты база 10 и веса букв

Веса A = 1, B = 2, C = 3, D = 4 и основание 10 выбраны исключительно ради наглядности: при них хеш выглядит как обычное десятичное число, которое читается глазами. Образец ABABAC превращается в 121213, окно ABABAD - в 121214.

В настоящих программах основанием берут размер алфавита - например, 256 для однобайтовой кодировки, - а весами настоящие коды символов: у буквы A это 65, а не 1. Наглядности в таком хеше нет, зато нет и лишней работы: код символа уже лежит в памяти.

Вес задан и букве D, хотя в образце ABABAC ее нет. Так и должно быть: веса назначаются всему алфавиту текста, а не буквам образца. Окно ABABAD алгоритм обязан уметь посчитать, иначе ему нечего будет сравнивать с образцом.

Схема Горнера и множитель старшего разряда

Хеш окна - это его запись как числа в системе счисления с выбранным основанием, от которого берут остаток по модулю q. Само число считают по схеме Горнера, слева направо, ровно так же, как человек читает многозначное число: на каждом символе прежнее значение умножается на основание и к нему прибавляется вес очередной буквы. Для ABABAC получается 121213, а его остаток по модулю 199 равен 22.

Вот эти шесть шагов целиком, для образца ABABAC:

Первые три шага модуль ничего не меняет: числа еще меньше 199. На четвертом шаге 1212 уже больше модуля, поэтому от него остается 18 - и дальше счет идет от остатка, а не от полного числа. Тем же порядком считается хеш первого окна текста ABABAD: пять шагов совпадают, а на последнем 181 * 10 + 4 = 1814 дает остаток 23.

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

В нашем примере M = 6, основание 10, модуль 199, поэтому h = 10⁵ mod 199 = 100000 mod 199 = 102. Дальше весь пересчет окна укладывается в одну строку:

Проверим на первом же сдвиге. Хеш окна ABABAD равен 23, выпадает A с весом 1, входит следующая по тексту A, тоже с весом 1: (10 * (23 - 1 * 102) + 1) mod 199 = -789 mod 199 = 7. Ровно это число тренажер показывает для окна BABADA. Промежуточный результат получился отрицательным - в языке C остаток от деления отрицательного числа тоже отрицателен, поэтому в коде ниже стоит отдельная строка, прибавляющая модуль обратно.

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

Отрицательные промежуточные значения в четвертом столбце - это не ошибка: к ним прибавляют модуль, пока результат не станет неотрицательным. Например, -789 + 199 * 4 = 7.

Два окна из семи дали остаток 22, тот же, что у образца. Одно из них, окно 6, - настоящее вхождение. Второе, окно 2, - ложная тревога: строка ABADAB на образец не похожа, а остаток совпал. Об этом следующий раздел.

Зачем нужен переход к остатку

Резонный вопрос: зачем нужен модуль, если 121213 и так число и его можно сравнивать напрямую? Дело в том, что настоящий образец редко бывает длиной в шесть букв.

• Числа становятся астрономическими. Образец в 50 символов при основании 256 дает число порядка 256⁵⁰. В 64-битный регистр помещается около 20 десятичных цифр, а здесь их больше сотни.
• Скорость падает до наивной. С такими числами процессор за один такт не работает, нужна длинная арифметика. Пересчет окна перестает стоить O(1), и вся идея алгоритма пропадает.
• Модуль работает предохранителем. Он сжимает сколь угодно большое число в диапазон от 0 до q-1, и вся арифметика остается в штатных машинных типах.

Коллизии

Хеш - это число фиксированного размера (обычно это остаток по некоторому модулю). Из-за ограниченного диапазона значений хеша две совершенно разные строки могут дать одинаковое числовое значение. Это называется коллизией.

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

В тренажере ниже модуль намеренно взят маленьким (199), и коллизия действительно случается: окно ABADAB дает тот же остаток 22, что и образец ABABAC. Спасает только посимвольная проверка, которая эту ложную тревогу отсеивает.

В учебниках такую ложную тревогу называют холостым срабатыванием алгоритма. Именно из-за него у Рабина-Карпа плохая худшая оценка: если хеши будут совпадать на каждом окне, посимвольная проверка запустится всюду и алгоритм скатится к наивному перебору, то есть к O(M(N-M+1)). В среднем же, при разумном модуле, холостые срабатывания редки, и работа занимает O(N+M).

Выбор модуля в прикладных программах

Модуль 199 в тренажере взят маленьким намеренно: чтобы коллизия случилась уже на втором окне и ее было видно. В прикладных программах поступают иначе:

• берут большое простое число (простое - это число, которое делится нацело только на единицу и на само себя: 2, 3, 5, 7, ..., 101, 199), такое, чтобы произведение основания на модуль еще помещалось в машинное слово. Распространенный выбор - 1000000007: сам модуль влезает в 32 бита, а умножения при пересчете ведут в 64-битном типе. Чем больше модуль, тем реже холостые срабатывания, а простое число нужно, чтобы остатки распределялись равномерно и у модуля не оказалось общих делителей с весами символов;
• либо пользуются трюком с переполнением: считают в типе unsigned long long и не берут остаток вовсе. Выход за границу типа математически равносилен взятию остатка по 2⁶⁴. Это не простое число, коллизий будет чуть больше, зато из внутреннего цикла исчезает деление - самая дорогая операция в пересчете.

Реализация на языках C и C++

Ниже приведена классическая реализация с вычислением хеша по схеме Горнера и использованием кольцевого хеша при сдвиге.

Модулем взято большое простое число 1000000007, и этот выбор сразу задает требование к типам. При пересчете окна возникает произведение вида основание умножить на модуль, оно доходит до нескольких триллионов и в int не помещается, поэтому хеши хранятся в long long. В учебных примерах вместо этого нередко берут маленький модуль вроде 101: тогда вся арифметика влезает в int, но холостые срабатывания случаются примерно на каждом сотом окне, и посимвольная проверка запускается постоянно.

Приведение (unsigned char) в строках вычисления хеша тоже не косметическое. Тип char в C знаковый, и у байтов со значением больше 127 - а это все буквы кириллицы в однобайтовых кодировках и любой байт UTF-8 - код оказывается отрицательным. Тогда хеш образца уходит в минус, а хеш окна после первого же сдвига приводится к неотрицательному диапазону, и совпасть они больше не могут: поиск находит вхождение в самом начале текста и пропускает все остальные.

#include <stdio.h>
#include <string.h>

#define D 256  // Размер алфавита (база)
#define Q 1000000007LL // Большое простое число: чем больше модуль, тем реже холостые срабатывания

void searchRabinKarp(const char* pat, const char* txt) {
    int M = strlen(pat);
    int N = strlen(txt);
    long long p = 0; // хеш образа
    long long t = 0; // хеш текущего окна текста
    long long h = 1; // множитель для старшего разряда: D^(M-1) % Q

    // Вычисляем значение h
    for (int i = 0; i < M - 1; i++) {
        h = (h * D) % Q;
    }

    // Считаем начальный хеш образа и хеш первого текстового окна
    for (int i = 0; i < M; i++) {
        p = (D * p + (unsigned char)pat[i]) % Q;
        t = (D * t + (unsigned char)txt[i]) % Q;
    }

    // Скользим окном по тексту
    for (int i = 0; i <= N - M; i++) {
        // Если хеши совпали, проверяем символы (защита от коллизий)
        if (p == t) {
            int j;
            for (j = 0; j < M; j++) {
                if (txt[i + j] != pat[j]) break;
            }
            if (j == M) {
                printf("Найдено на индексе %d\n", i);
            }
        }
        
        // Вычисляем хеш для следующего окна за O(1)
        if (i < N - M) {
            // (t - (выпавший символ * h)) * D + вошедший символ
            t = (D * (t - (unsigned char)txt[i] * h) + (unsigned char)txt[i + M]) % Q;
            
            // Защита от отрицательных остатков в языке C
            if (t < 0) {
                t = (t + Q); 
            }
        }
    }
}

Приведенный выше код на C собирается и компилятором C++ без единой правки - это проверено сборкой в режиме C++17. Но если вы пишете на C++, привычнее другая запись: std::string и std::vector вместо указателей и ручного выделения памяти. Посимвольную проверку после совпадения остатков берет на себя compare.

#include <string>
#include <vector>

// Поиск всех вхождений по остаткам характеристических чисел
std::vector<std::size_t> rabinKarp(const std::string& txt, const std::string& pat) {
    const long long D = 256;              // основание: размер алфавита
    const long long Q = 1000000007;       // большое простое число
    std::vector<std::size_t> found;
    const std::size_t m = pat.size();
    const std::size_t n = txt.size();
    if (m == 0 || m > n) return found;

    long long h = 1, p = 0, t = 0;
    for (std::size_t i = 1; i < m; ++i)
        h = h * D % Q;                    // вес старшего разряда
    for (std::size_t i = 0; i < m; ++i) {
        p = (D * p + static_cast<unsigned char>(pat[i])) % Q;
        t = (D * t + static_cast<unsigned char>(txt[i])) % Q;
    }

    for (std::size_t i = 0; i + m <= n; ++i) {
        // остатки равны - обязаны сверить строки посимвольно
        if (p == t && txt.compare(i, m, pat) == 0) found.push_back(i);
        if (i + m < n) {
            t = (D * (t - static_cast<unsigned char>(txt[i]) * h)
                 + static_cast<unsigned char>(txt[i + m])) % Q;
            if (t < 0) t += Q;            // остаток в C++ бывает отрицательным
        }
    }
    return found;
}