Строковые алгоритмы на практике. Часть 3 — Алгоритм Рабина — Карпа

Моя цель - предложение широкого ассортимента товаров и услуг на постоянно высоком качестве обслуживания по самым выгодным ценам.

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


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


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


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


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



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


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


У нас есть двоичный алфавит, где $a = 0, b = 1$.


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


$H(P) = 1 * 2^4 + 0 * 2^3 + 1 * 2^2 + 0 * 2^1 + 1 * 2^0 = 21$


Вычислим хеш подстроки $T[0, 4]$.


$H(T[0, 4]) = 0 * 2^4 + 0 * 2^3 + 1 * 2^2 + 0 * 2^1 + 1 * 2^0 = 5$


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


Вычислим хеш подстроки $T[1, 5]$.


$H(T[1, 5]) = (H(T[0, 4]) - 0 * 2^4) * 2 + 0 * 2^0 = 10$


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


Вычислим хеш подстроки $T[2, 6]$.


$H(T[2, 6]) = (H(T[1, 5]) - 0 * 2^4) * 2 + 1 * 2^0 = 21$


Хеши совпали, значит проверяем символы построчно.


Расчет хеша


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


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


$H(P) = p[0] * x^{m-1} + p[1] * x^{m-2} + ... + p[m-1] * x^0$


$H(P)$ — хеш паттерна
$x$ — некоторое натуральное число, например мощность алфавита.


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


$H(Pattern) = 80 * 128^6 + 97 * 128^5 + 116 * 128^4 + 116 * 128^3 \\ + 101 * 128^2 + 114 * 128^1 + 110 * 128^0$


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


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


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


$H(P) = p[m-1] * x^{m-1} + p[m-2] * x^{m-2} + ... + p[0] * x^0 = \\ (...(p[m-1] * x + p[m-2]) * x + ... + p[1]) * x + p[0]$


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


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


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


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


$H(P) = (((...((p[m-1] * x + p[m-2])\mod q) * x \\ + ... + p[1]) \mod q) * x + p[0]) \mod q$


На всех промежуточных этапах мы получим значения не превышающие
$p_{max} * (x + 1)$.


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


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

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


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


Поподробнее


У нас есть текст $t[0...n]$ длиной $len = n + 1$. Если мы возьмем $q > len^c$, где $c > 2$, то вероятность коллизии будет менее, чем $1/n^{c - 2}$


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


вот


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


Все логично, чем больше простое число, тем меньше мы скукоживаем хеш, тем меньше коллизий. Ведь когда мы берем диапазон чисел $[0; 2^{1024}]$, (а примерно такой хеш мы можем получить без модульной арифметики), и пытаемся его ужать в диапазон $[0, 2^{32}-1]$, то очевидно, что мы должны за это чем-то заплатить. И цена этому коллизии.


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


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

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


Псевдо ДНК


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


Строка ДНК

GTAGTGTGTCTACGTCTTTCTTTGACAGTACCGCGTAATTTGCAGTGCTATAAATCATCTCTAACGCTGGCTGTGCACCGCCACCGTAGTGTGTCTACGTCTTTCTTTGACAGTACCGCGTAATTTGCAGTGCTATAAATCATCTCTAACGCTGGCTGTGCACCGCCACCCCAGCGGGAAGCCCATTTTTCCACTACCTCTGTTCCTGGTATAGTGCACTATATCGCCCGTAACCGATGTCTCGCCAAGATTTTGGCAACTTCCCGAGCAATCAGGTGGAGTCAGACCGATAGCTCTAATGGTTTACGTGAATGCATGGCGCCTATAGCTATGGGCAGAAACCAGCGGGAAGCCCATTTTTCCACTACCTCTGTTCCTGGTATAGTGCACTATATCGCCCGGTAGTGTGTCTACGTCTTTCTTTGACAGTACCGCGTAATTTGCAGTGCTATAAATCATCTCTAACGCTGGCTGTGCACCGCCACCCCAGCGGGAAGCCCATTTTTCCACTACCTCTGTTCCTGGTATAGTGCACTATATCGCCCGTAACCGATGTCTCGCCAAGATTTTGGCAACTTCCCGAGCAATCAGGTGGAGTCAGACCGATAGCTCTAATGGTTTACGTGAATGCATGGCGCCTATAGCTATGGGCAGAAATAACCGATGTCTCGCCAAGATTTTGGCAACGTAGTGTGTCTACGTCTTTCTTTGACAGTACCGCGTAATTTGCAGTGCTATAAATCATCTCTAACGCTGGCTGTGCACCGCCACCCCAGCGGGAAGCCCATTTTTCCACTACCTCTGTTCCTGGTATAGTGCACTATATCGCCCGTAACCGATGTCTCGCCAAGATTTTGGCAACTTCCCGAGCAATCAGGTGGAGTCAGACCGATAGCTCTAATGGTTTACGTGAATGCATGGCGCCTATAGCTATGGGCAGAAATTCCCGAGCAATCAGGTGGAGTCAGACCGATAGCTCTAATGGTTTACGTGAATGCATGGCGCCTATAGCTATGGGCAGAAA


Образец: 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


Алгоритм дуб Андрей обломанн
getSubstringNaive 57,320 29,506 21,596
getSubstringKMP 149,516 163,727 129,087
getSubstringNotSoNaive 161,560 176,117 136,640
getSubstringBMBadCharacter 246,769 376,072 409,002
getSubstringRK 153,172 155,100 152,668

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


Алгоритм дуб Андрей обломанн
getSubstringNaive 5,013 10,008 13,328
getSubstringKMP 1,741 1,688 1,832
getSubstringNotSoNaive 1,739 1,683 1,828
getSubstringBMBadCharacter 601 327 283
getSubstringBMGoodSuffix 1,692 1,680 1,690

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


Выводы


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

Источник: https://habr.com/ru/post/662678/

Вернуться к списку

Интересные статьи

Интересные статьи

Я написал более быстрый алгоритм сортировки
Я написал более быстрый алгоритм сортировки
Может показаться откровенной наглостью в наши дни утверждать, что Вы изобрели алгоритм сортировки, который на 30% быстрее, чем лучший существующий. Увы, я должен сделать гораздо более наглое заявлени...
Чистая архитектура. Часть III — Принципы дизайна
Принципы SOLID говорят нам, как нам соединять наши функции и данные в классы, и как эти классы должны быть взаимосвязаны. Т.е. эти принципы относятся к уровню модулей (mid-level). Однако ...
Инфоблоки в 1С-битрикс
Инфоблоки в 1С-битрикс
В 1С Битрикс есть специальные сущности под названием “Информационные блоки, сокращенно (инфоблоки)“, я думаю каждый с ними знаком, но не каждый понимает, что это такое и для чего они нужны
Подготовка приложения к Android Q. Часть 2
Подготовка приложения к Android Q. Часть 2
Перевод статьи подготовлен специально для студентов курса «Android-разработчик. Базовый курс». Также напоминаем о том, что мы продолжаем набор на расширенный курс «Специализация Android-разработч...
Адаптация программ для ZX Spectrum к TR-DOS современными средствами. Часть 2
Адаптация программ для ZX Spectrum к TR-DOS современными средствами. Часть 2
В первой части статьи мы разобрали загрузчик оригинальной версии и выяснили, куда загружается код игры и как он запускается. Теперь нужно перенести файлы на диск. Обычно это делается простым к...