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

Часть 1 — Алгоритм Кнута — Морриса — Пратта
Часть 2 — Алгоритм Бойера — Мура

Устройство алгоритма

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

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

Что это все значит

Все очень просто.

У нас есть двоичный алфавит, где .

Вычислим хеш паттерна:

Вычислим хеш подстроки .

Они не совпадают, значит двигаем паттерн на символ правее.

Вычислим хеш подстроки .

Хеши подстроки и паттерна снова не совпадают, значит двигаем паттерн еще на символ правее.

Вычислим хеш подстроки .

Хеши совпали, значит проверяем этот участок посимвольно.

Расчет хеша

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

В общем виде расчет хеша будет выглядеть примерно вот так:

— хеш паттерна
— некоторое натуральное число, например мощность алфавита.

Теперь давайте посчитаем хеш реальной строки. Возьмем строку Pattern и для наглядности за x возьмем мощность семибитной таблицы ASCII — 128.

Результат: 355 207 998 962 030

Выглядит многовато. Чтобы записать такое число в двоичном виде понадобится 49 разрядов, а у нас из исходных данных всего лишь паттерн длинной 7 символов и урезанная кодировка ASCII. Если мы возьмем восьмибитную версию, то будет уже переполнение даже на 64-х битных системах. Так что решить этот вопрос нам помогут схема Горнера и модульная арифметика.

Схема Горнера

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

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

Модульная арифметика

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

Таким образом, наш конечный алгоритм должен выглядеть примерно вот так:

На всех промежуточных этапах мы получим значения не превышающие
.

Но тут есть один нюанс:

Когда тебе удается впихнуть невпихуемое, ты злишь бога коллизий

Побег от бога коллизий

Если начать забуриваться в изыскания на тему коллизий в кольцевых хеш-функциях, то натуральным образом можно оттуда не выбраться. Если кратко, то число q должно быть большим и простым. А если поподробнее то вот:

Поподробнее

У нас есть текст длиной . Если мы возьмем , где , то вероятность коллизии будет менее, чем

Если пробежаться по первой тысяче простых чисел и построить график , где это количество коллизий, то будет вот:

Здесь я провел проверку на отрывке про дуб из Войны и мира, где искал строку обломанн. Да паттерн не очень большой, числа тоже не самые огромные, но зато мы можем посмотреть динамику количества коллизий. И как это не тривиально — мы получили обычную асимптоту. Ну и как мы можем заметить после 7000 самое худшее, что мы получаем это 1 коллизию. Конечно не факт, что дальше не будет какого-нибудь всплеска. Но начиная с 2000 самое худшее, что у нас было это 4 коллизии на текст 1671 символа.

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

Код алгоритма

export function getSubstringRK(text: string, pattern: string): number[] {
    const result = [];

    const alphabetSize = 256;
    const mod = 9973;

    let patternHash = pattern.charCodeAt(0) % mod;
    let textHash = text.charCodeAt(0) % mod;

    let firstIndexHash = 1;

    for(let i = 1; i < pattern.length; i++)
    {
        patternHash *= alphabetSize;
        patternHash += pattern.charCodeAt(i);
        patternHash %= mod;

        textHash *= alphabetSize;
        textHash += text.charCodeAt(i);
        textHash %= mod;

        firstIndexHash *= alphabetSize;
        firstIndexHash %= mod;
    }

    for (let i = 0; i <= text.length - pattern.length; i++) {
        if (patternHash === textHash && compareText(text, i, pattern)) {
            result.push(i);
        }

        if (i === text.length - pattern.length) break;

        textHash -= (text.charCodeAt(i) * firstIndexHash) % mod;
        textHash += mod;
        textHash *= alphabetSize;
        textHash += text.charCodeAt(i + pattern.length);
        textHash %= mod;
    }

    return result;
}

function compareText(text: string, index: number, pattern: string): boolean {
    for (let i = 0; i < pattern.length; i++) {
        if (pattern[i] !== text[index + i]) {
            return false;
        }
    }

    return true;
}

Замеры производительности

Конкурсы все те же:

• Худший случай.
• Строка с маломощным алфавитом.
• Реальный текст.

Орущие строки

Замеры, где и текст и паттерн состоят только из буквы "а".

Текст: строка длинной 1024 символа
Образец: строка длинной 32 символа

Ops/sec

getSubstringNaive x 9,141
getSubstringKMP x 84,419
getSubstringNotSoNaive x 9,587
getSubstringBMBadCharacter x 9,103
getSubstringRK x 9,975

Количество сравнений

getSubstringNaive : 31,776
getSubstringKMP : 2,047
getSubstringNotSoNaive : 31,776    
getSubstringBMBadCharacter : 31,776
getSubstringRK : 32,769 

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

Псевдо ДНК

Строка состоящая из 1024 символов алфавита [TGAC].

Образец: GTAGTGTGTCTACGTCTTTCTTTGACAGTACCGCGTA. (37 символов)

Ops/sec

getSubstringNaive x 6,349
getSubstringKMP x 156,780
getSubstringNotSoNaive x 189,694
getSubstringBMBadCharacter x 199,476
getSubstringRK x 229,361

Количество сравнений

getSubstringNaive : 36,556
getSubstringKMP : 1,422
getSubstringNotSoNaive : 1,434    
getSubstringBMBadCharacter : 925
getSubstringRK : 1,136

Несмотря на то, что алгоритм Рабина-Карпа на втором месте, по количеству сравнений, он опережает Бойера-Мура. Ну в общем-то БМ с эвристикой плохого символа не так эффективен на сгенерированных строках.

Война и мир

Текст:

Паттерны:

1. дуб
2. Андрей
3. обломанн

Результаты

Ops/sec

Количество сравнений

На реальном тексте алгоритм держит планку по , его производительность примерно как у КМП алгоритма и ± такое же количество сравнений.

Выводы

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