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

[Dolios]

КМП в "реальных условиях" было бы интересно сравнить с алгоритмами Рабина-Карпа и Ахо-Корасик. Теоретически, алгоритм Рабина-Карпа квадрат даёт в худшем случае, но на практике вряд ли у хеш-функции будет столько коллизий.

[Hrodvitnir]

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

[fallenworld]

Ваш не очень наивный алгоритм на самом деле наивный, и имеет сложность O(m*n) с оговоркой, что оно стремится к m(длина текста) если в тексте мало префиксов паттерны. У вас в тексте мало префиксов пвттерна, поэтому наивный алгоритм оптимален.

Попробуйте провести замеры на паттерны типа: aaaaab

И тексте типа: aaaaaaaaaaaaaaaaaaaa...

[Hrodvitnir]

Наивный он идет допоследнего в любом случае, а неочень наивный при первом различии бросает сравнение.
Я прекрасно понимаю, что в худшем случае сложность будет O(n * m), но на естественных текстах такой сложности вряд ли можно добиться, потому и "общая" сложность у него O(n) :)

[wataru]

А потом какой-то злыдень посылает на сервер именно такой "неестественный" текст и все виснет.

[fallenworld]

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

П.С. Вы не подумайте, статья хорошая, + поставил

[wataru]

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

Во-вторых, КМП у вас реализован дико неэффективно.

FindBorders пишется вот так (код практически идентичный коду в поиске), а не жадной функцией.

правильный код findBorders

export function findBorders(text: string): number[] {
    let compareIndex = 0;
    const borders = [-1];
    for (let i = 1; i < text.length; i++) {
        while (compareIndex >= 0 && text[i] !== text[compareIndex]) {
            compareIndex = borders[compareIndex - 1];
        }
       compareIndex++;
       borders.push(compareIndex);
    }
    return borders;
}

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

И последнее: есть простой трюк, который сокращает лишние проверки:
borders[0] надо сделать равным -1.

Тогда в цикле проверки будет:

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

Сокращается лишняя проверка после while. Ибо while может или закончится при совпадении символов и тогда инкримент надо делать, или при становлении индекса -1, тогда совпадений вообще не было и индекс после цикла должен быть равен нулю, а значит инкримент как раз работает. Этот же трюк я уже использовую в findBorders.

[Hrodvitnir]

Понял, проведу замеры и поправлю статью, если результаты изменятся в лучшую сторону

[BellaLugoshi]

Уже три недели набегами изучаю и тестирую, вот что получилось у меня (я правда слишком слаб в программировании чтобы понимать как считаются операции в секунду или количество сравнений, поэтому я считаю время работы и число шагов/итераций алгоритма), получается вот что:

"Наивный" / 1341 мс / шагов 873 200 019 / сравнений 914 858 298

"Наивный назад" / 1405 мс / шагов 873 200 019 / сравнений 931 847 463

"Наивный туда-сюда" / 1388 мс / шагов 873 199 760 / сравнений 916 906 047

КМП / 2028 мс / шагов 799 709 013 / сравнений 857 275 497

Моё / 3045 мс / шагов 128 518 565 / сравнений 138 097 420

Поиск делаю по файлу размером в 833 мегабайта, собственной наивный алгоритм как раз шагает ровно столько байт сколько в файле.

"Наивный назад" это всего лишь вариант с декрементной итерацией поиска подстроки, он всегда стабильно медленнее, хоть и немного, инкрементного варианта. "Туда-сюда" это эвристика на более быстрое исключение подстрок которые различаются ближе к концу, например расчёты сделаны при поиске слова "schemata", в тексте есть несколько слов с начальным набором "schema", но разным суффиксом. Но так как слов не фатально много и при этом скорее всего достаточно слов наоборот имеющих суффиксы "ta" например, то получается число сравнений даже выросло. КМП взят с geekforgeeks по вашей же ссылке с версией для C# (я на нем и пишу).

Моя реализация с пока не обозначенными эвристиками справляется хорошо по числу как итераций, так и по числу самих сравнений (я в начале написал что не понимаю как вы делаете подсчёт сравнений, поэтому в моём варианте это просто вставленные инкременты для переменной в цикле, где происходит сравнение элементов подстроки и строки).

Так вот у меня собственно вопрос - это проблема сугубо C# что при почти в 5,5 раз меньшем числе итераций и сравнений у меня в больше чем в 2 раза дольше исполнение кода? Я конечно пользуюсь Dictionary (для вас это Map) но я не замечал чтобы он работал медленно. И кстати реализацию КМП эвристики у себя я еще не встраивал, это даст еще снижение числа итераций, но, получается, только еще более замедлит выполнение. В общем я пока в раздумьях.

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