Альтернатива брутфорсу. Текстовый поиск с хеш-функцией

Ранее я уже писал об азах текстового поиска, теперь хочу продолжить и написать о том, как развиваются алгоритмы в сторону эффективности.
Итак, как Майкл Рабин и Ричард Карп разогнали алгоритм?


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

Первое приближение

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

private int GetHashOfString(string s)
{
    int result = 0;
    for (int i = 0; i < s.Length; i++)
    {
        result += s[i];
    }
    return result;
}


Сама функция поиска подстроки будет выглядеть так:

public int Match(string input, string pattern)
{
    int inputLength = input.Length;
    int patternLength = pattern.Length;
    int patternHash = GetHashOfString(pattern);
    int substringHash;

    for (int i = 0; i <= inputLength - patternLength; i++)
    {
        substringHash = GetHashOfString(input.Substring(i, patternLength));
        if (patternHash == substringHash)
        {
            bool success = true;
            for (int j = 0; j < patternLength; j++)
            {
                if (input[i + j] != pattern[j])
                {
                    success = false;
                    break;
                }
            }
            if (success)
                return i;
        }
    }
    return -1;
}


Разгоняем алгоритм

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



Код изменится следующим образом:

...
int patternHash = GetHashOfString(pattern);
int substringHash = GetHashOfString(input.Substring(0, patternLength));

for (int i = 0; i <= inputLength - patternLength; i++)
{
    if (i > 0)
        substringHash =
            substringHash - input[i - 1] + input[i + patternLength - 1];
    if (patternHash == substringHash)
...


Продолжаем разгон?

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



Как получить на новом шаге значение хеша из предыдущего значения? Так как длина шаблона у нас постоянная, то можно один раз вычислить и запомнить основание в степени длины шаблона за вычетом единицы: maxBase = 61^(length–1). Вместо вычитания значения выкидываемого кода, мы вычитаем его значение, помноженное на maxBase, то есть ‘a’*61^3.
После этого необходимо добавить новый код и помножить полученное значение на основание нашей системы (61).
Это можно записать в виде псевдокода:

substringHash = substringHash - input[i - 1];
substringHash = substringHash + input[i + patternLength - 1];
substringHash = substringHash * base; // base – основание системы

Другой вопрос: а что будет с хешем при большей длине строки (точнее при достаточно большой длине шаблона)? 61 в шестой степени (для длины 7 символов) уже не вмещается в четырёхбайтовое целое.

На помощь приходит «арифметика по модулю». Мы не будем хранить огромные числа, которые невозможно уместить в тридцатидвухразрядный int, мы будем брать их остаток от деления на некое простое число q.
На всякий случай скажу, что «арифметика по модулю» базируется на таких тождествах, как:
(a + b + c) mod x = (a mod x + b mod x + c mod x) mod x
(a * b * c) mod x = (a mod x * b mod x * c mod x) mod x

Реализуем алгоритм

Итак, хеш-функция будет состоять не из суммы кодов символов, помноженных на выбранное основание base в соответствующей степени, а из этой суммы, взятой по модулю q. Значения q и base будем выбирать больше длины алфавита, то есть для ASCII это будет > 256, а для юникода > 65536.

Наша функция для строки s длиной 3 символа будет иметь вид:
((ascii(s[0]) * base^2) mod q + (ascii(s[1]) * base^1) mod q + (ascii(s[2]) * base^0) mod q) mod q

Поскольку длина шаблона во время одного поиска остаётся неизменной, неизменной остаётся и base^(length–1) mod q. Вычисление этой величины вынесем в отдельный метод:

private int GetMaxBase(int length, int q, int b)
{
    int result = 1;
    for (int i = 0; i < length - 1; i++)
        result = (result * b) % q;
    return result;
}


Как и ранее, создадим метод для хеш-функции:

private int GetHashOfString(string s, int q, int b)
{
    int result = 0;
    int length = s.Length;

    for (int i = 0; i < length; i++)
        result = (b * result + s[i]) % q;
    return result;
}

Теперь сама функция поиска:
public int Match(string input, string pattern, int b, int q)
{
    int inputLength = input.Length;
    int patternLength = pattern.Length;
находим значение base^(patternLength — 1) по модулю q
    int maxBase = GetMaxBase(patternLength, q, b);
предварительно находим хеш-значения для шаблона и первой подстроки
    int patternHash = GetHashOfString(pattern, q, b);
    int substringHash =
        GetHashOfString(input.Substring(0, patternLength), q, b);

    for (int i = 0; i <= inputLength - patternLength; i++)
    {
если хеш-значения совпали — сравниваем строки полностью
        if (patternHash == substringHash)
        {
            bool success = true;
            for (int j = 0; j < patternLength; j++)
            {
                if (input[i + j] != pattern[j])
                {
                    success = false;
                    break;
                }
            }
            if (success)
                return i;
        }
если мы не на последнем шаге, находим новое значение хеш-функции
        if (i != inputLength - patternLength)
            substringHash =
                (b * (substringHash - input[i] * maxBase) +
                input[i + patternLength]) % q;
если получилось отрицательное число, делаем его положительным :)
        if (substringHash < 0) substringHash += q;
    }
    return -1;
}

Наконец-то

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

Надеюсь, что в скором будущем смогу написать о том, в какую сторону двигались другие люди, пытаясь найти эффективные алгоритмы поиска подстроки. Спасибо тем, кто дочитал до конца.

Проект с тестами можно скачать здесь