Строковые алгоритмы на практике. Часть 1 — Алгоритм Кнута — Морриса — Пратта

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

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

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

Код, примеры и термины будут местами из ранее упомянутой книги С. Окулова "Алгоритмы обработки строк", так что, если какой-то термин будет упомянут не правильно, то милости прошу, поправляйте и я внесу коррективы.

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

Грани строки

Начать стоит с того, что у строки есть грани. Гранью строки называется любой префикс строки, который равен ее суффиксу.

Например, у строки qwertyqwe есть грань qwe, потому что строка и начинается, и заканчивается на qwe. Важно заметить, что грань не может быть равна самой строке.

Таким образом для строки aaaaa, грани будут a, aa, aaa, aaaa, но aaaaa гранью не будет.
К чему собственно разгон: с помощью вычисления массива граней (он же таблица префиксов и суффиксов) реализуется главная фишка алгоритма — таблица сдвигов паттерна поиска.

Таблица сдвигов паттерна поиска

Есть например у нас паттерн поиска abaaba.

1. Берем первый символ строки (а) и ищем для него грань. Так как для него грани быть не может (потому что грань не может быть равна строке) то грань — 0.
2. Берем теперь два первых символа (ab) и ищем грань для них. Так как нет суффикса, который равен префиксу, то грань снова 0.
3. Берем подстроку aba и ищем максимальную грань для нее. Так как из префиксов и суффиксов совпадают только буквы «а», то максимальная грань — 1.

Повторять до конца.

export function findBorders(pattern: string): number[] {
    const borders = new Array(pattern.length);
    borders[0] = 0;

    let currentIndex = 0;

    for (var i = 1; i < pattern.length; i++) {
        while (currentIndex > 0 && pattern[currentIndex] !== pattern[i]) {
            currentIndex = borders[currentIndex - 1];
        }

        if (pattern[currentIndex] === pattern[i]) {
            currentIndex++;
        }

        borders[i] = currentIndex;
    }

    return borders;
}

UPD: спасибо wataru, за то что указал более оптимальный метод поиска граней.

Результат должен быть вот такой:

Для чего были нужны все эти манипуляции? Сейчас поясню.

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

Ход поиска

Что здесь происходит:
Мы сравниваем наш текст T с паттерном P. Первые два символа текста совпали с паттерном, но третий символ T и P не совпали (T[2] != P[2]). Значит смотрим в наш массив граней br. Ага, грань br[2] имеет длину 0. Значит сдвигаем P на 2 символа вправо (длина совпавшего участка за вычетом длины грани плюс сдвиг на единичку: 2 - 1 + 1).

Передвинули, проверяем символ еще раз:T[2] != P[0], хорошо, тогда сдвигаем паттерн еще на 0 - 0 + 1.

Дальше совпадает еще три символа и так далее.

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

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

    let compareIndex = 0;

    for (let i = 0; i < text.length; i++) {
        while (compareIndex > 0 && text[i] !== pattern[compareIndex]) {
            compareIndex = borders[compareIndex - 1];
        }

        if (text[i] === pattern[compareIndex]) {
            compareIndex++;
        }

        if (compareIndex === pattern.length) {
            result.push(i - compareIndex + 1);
            compareIndex = borders[pattern.length - 1];
        }
    }

    return result;
}

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

Сравним производительность наивного алгоритма и нашей реализации КМП.

Текст:

Паттерн:
GTAGTGTGTCTACGTCTTTCTTTGACAGTACCGCGTA

Замер происходит для всех четырех вхождений.

getSubstringNaive x 2,961 ops/sec ±1.57% (88 runs sampled)
getSubstringKMP x 83,890 ops/sec ±0.48% (93 runs sampled)

Выходит так, что КМП быстрее почти в 27 раз.

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

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

    for (let i = 0; i <= text.length - pattern.length; i++) {
        let flag = true;
        // Ну о-о-о-очень наивный алгоритм
        for (let j = 0; j < pattern.length; j++) {
            if (text[i + j] !== pattern[j]) {
                flag = false;
            }

            if (j === pattern.length - 1 && flag) {
                result.push(i);
            }
        }
    }

    return result;
}

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

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

    for (let i = 0; i <= text.length - pattern.length; i++) {
        for (let j = 0; j < pattern.length; j++) {
            if (text[i + j] !== pattern[j]) {
                break;
            }

            if (j === pattern.length - 1) {
                result.push(i);
            }
        }
    }

    return result;
}

Повторим наши замеры:

getSubstringNaive x 2,984 ops/sec ±0.75% (97 runs sampled)
getSubstringKMP x 89,802 ops/sec ±0.20% (94 runs sampled)
getSubstringNotSoNaive x 109,839 ops/sec ±0.52% (96 runs sampled)

И вот мы в 1.2 раза обогнали КМП алгоритм.

Сравнение продуктивности

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

Код для всего этого безобразия будет выглядеть

export class Counter {
    public get count(): number {
        return this._count;
    }

    public readonly name: string;
    private _count: number = 0;

    public constructor(name: string) {
        this.name = name;
    }

    public increase(): void {
        this._count++;
    }
}

const counterMap = new Map<string, Counter>();

export function createCounter(name: string): Counter {
    const counter = new Counter(name);

    counterMap.set(name, counter);

    return counter;
}

export function getAllCounters(): [string, Counter][] {
    return Array.from(counterMap.entries());
}

export function compare<T>(first: T, second: T, counter: Counter): boolean {
    counter.increase();

    return first === second;
}

Засунем везде функцию compare и будем считать каждое фактическое сравнение символов.

Результат:

getSubstringNaive: 36,556
getSubstringKMP: 1,422
getSubstringNotSoNaive: 1,434

У КМП результат по количеству сравнений наименьший, ему в спину дышит не очень наивный алгоритм с разницей всего в 12 сравнений, а полный аутсайдер — наивный алгоритм.

Хорошо, мы сравнили скорость алгоритмов на одной конкретной строке, сравнили их продуктивность по сравнениям, а теперь давайте сравним это все на реальном тексте. Внимательный читатель, должен был заметить, что строка из предыдущего примера подозрительно похожа на последовательность ДНК, так вот, это потому что КМП алгоритм вообще ценился, а может быть и до сих пор ценится в биоинформатике, в плане поиска нуклеотидных последовательностей (Я даже нашел пару научных публикаций на этот счет).

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

Проверять будем на отрывке из Войны и мира про злосчастный дуб.

Найдем все упоминания слов:

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

Результаты

Ops/sec

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

Очевидные и не очень выводы

Первый вывод и он же очевидный: чем больше сравнений, тем меньше скорость алгоритма.

Второй: КМП и не очень наивный алгоритм имеют практически одинаковое количество сравнений, но при этом разница в скорости примерно 35%.

Давайте поподробнее

Длина текста — 1673 символа. Мы фактически подтвердили сложность алгоритмов (хотя это от нас и не требовалось и не то чтобы кто-то в ней сомневался, но мне все равно приятно), потому что у наивного алгоритма количество сравнений изменяется примерно как n * m, а у остальных алгоритмов оно с определенной погрешностью держится около n, как и задумано.

Разница между КМП и не очень наивным алгоритмом такая большая оттого, что у КМП есть препроцессинг строки, а у его оппонента его нет. Кроме того, у КМП есть еще и накладные расходы на проверки массива граней, на входы и выходы из различных циклов и if'ов, но так как почти во всех случаях массив граней пустой, то получается, что порядок сравнений у обоих алгоритмов практически идентичный.

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

Это значит, что если у нас есть огромный файл генома и условно старый компьютер с ограниченным размером оперативной памяти (а КМП был опубликован в 1977 году, когда компьютер стоил как ракета, а оперативной памяти в них было с гулькин нос), то мы можем постепенно считывать этот файл (или перфоленту) и в реальном времени сравнивать поступающие данные и нужной последовательностью.

Вывод

Алгоритм очень занятный, но в прикладном значении он скорее всего бесполезен для 95% программистов, только если они не разрабатывают систему реального времени на каких-либо слабеньких устройствах.

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

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