Строковые алгоритмы на практике. Часть 2 — Алгоритм Бойера — Мура

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

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

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

Первая эвристика

Она же моя любимая.

Если символа на позиции в образце нет, то можем смело сдвигать образец за этот символ.

m – длинна образца.

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

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

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

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

Код составления таблицы плохих символов

В оригинальном алгоритме создается массив длиной равной длине кодировки, но в JS используется UTF-16, а в нее влазит до 1 112 064 символов, выходит накладненько. Важно понимать, что сам алгоритм появился в 1977 году, на 14 лет раньше того, когда люди решили взять все буквы на свете и запихнуть в одну табличку кодировки, так что ни у Бойера, ни у Мура не было сомнений, что создавать массив под всю кодировку это отличная идея. Все таки ASCII в зависимости от версии могла содержать от 128 до 256, так что это было оправданно.

Но если его использовать в изначальной трактовке в наше время, то даже если у нас в паттерне будут все символы русского и английского алфавитов, то полезная заполненность такого массива для того же юникода будет символов. А это примерно 0,01%, если учитывать весь потенциал юникода, если мы возьмем только заполненную его часть, то грубо говоря 0.12%. Это конечно в 12 раз лучше, но душу греет слабо.

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

export function badCharacterHeuristic(pattern: string): Map<string, number> {     const result = new Map<string, number>();      for(let i = 0; i < pattern.length; i++) {        result.set(pattern[i], i);     }      return result; } 

Ход поиска

Сначала мы сравниваем символы и (именно 8, 7, 6, ведь сравнение идет в обратном порядке), далее видя на позиции вхождение символа «f», которого нет в образце, переносим образец на позицию 7. После этого сравниваем и — они не совпадают и поэтому ищем самое правое вхождение символа b в образец и сдвигаем наш образец на (длина образца — позиция символа — 1), далее история повторяется. Что примечательно, на данном примере совпадение нашлось за 4 прикладывания, красиво же звучит?

export function getSubstringBMBadCharacter(text: string, pattern: string): number[] {     const symbolIndexes = badCharacterHeuristic(pattern);      const result = [];      let shift = 0;      while (shift <= (text.length - pattern.length)) {         let currentIndex = pattern.length - 1;          while (currentIndex >= 0 && pattern[currentIndex] === text[shift + currentIndex]) {             currentIndex--;         }          if (currentIndex == -1) {             result.push(shift);              const indent = (shift + pattern.length < text.length)                  ? pattern.length - symbolIndexes.get(text[shift + pattern.length])!                  : 1;              shift += indent;         } else {             const indent = symbolIndexes.get(text[shift + currentIndex]) ?? -1;              shift += Math.max(1, currentIndex - indent);         }     }      return result; }

Вторая эвристика

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

При сравнении паттерна у нас может произойти три ситуации:

Случай №1. Вхождение совпавшей части t в середине образца.

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

Мы сравнили и и при этом совпали только символы 4 и 3 (ab). Следующее вхождение ab у нас идет с позиции 1, значит сдвигаем паттерн на 2 символа вправо.

Случай №2. Префикс образца совпадает с суффиксом.

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

Мы сравнили подстроки T[4 — 1] и P[4 — 1] и совпала подстрока bab. В паттерне больше такой комбинации символов нет, но мы можем приладить префикс ab, так как он является суффиксом совпавшей подстроки, поэтому сдвигаем паттерн на 3 символа вправо.

Случай №3. Ничего не совпадает — едем дальше.

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

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

export function goodSuffixHeuristic(pattern: string): number[] {     const shifts = new Array(pattern.length + 1).fill(0);     const borderPositions = new Array(pattern.length + 1);      findShiftsAndBorders(shifts, borderPositions, pattern);      setShiftsForPrefix(shifts, borderPositions, pattern);      return shifts; }  function findShiftsAndBorders(shifts: number[], borderPositions: number[], pattern: string): void {     let i = pattern.length;     let j = pattern.length + 1;      borderPositions[i] = j;      while (i > 0) {         while (j <= pattern.length && pattern[i - 1]!== pattern[j - 1]) {             if (shifts[j] === 0) {                 shifts[j] = j - i;             }              j = borderPositions[j];         }          i--;         j--;          borderPositions[i] = j;     } }  function setShiftsForPrefix(shifts: number[], borderPositions: number[], pattern: string): void {     let prefixBorder = borderPositions[0];      for (let i = 0; i <= pattern.length; i++) {         if (shifts[i] === 0) {             shifts[i] = prefixBorder;         }          if (i === prefixBorder) {             prefixBorder = borderPositions[prefixBorder];         }     } } 

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

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

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

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

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

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

Ops/sec

getSubstringNaive: 8,785  getSubstringKMP: 84,089 getSubstringNotSoNaive: 9,504 getSubstringBMBadCharacter: 9,100 getSubstringBMGoodSuffix: 10,884 

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

getSubstringNaive : 31,776 getSubstringKMP : 2,047 getSubstringNotSoNaive : 31,776     getSubstringBMBadCharacter : 31,776 getSubstringBMGoodSuffix : 31,776

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

Псевдо ДНК

Срока с алфавитом из [TGCA], иными словами со скудным набором символов.

Образец: GTAGTGTGTCTACGTCTTTCTTTGACAGTACCGCGTA

Ops/sec

getSubstringNaive: 6,284 getSubstringKMP: 161,315 getSubstringNotSoNaive: 180,887 getSubstringBMBadCharacter: 75,085 getSubstringBMGoodSuffix: 508,159 

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

getSubstringNaive : 36,556 getSubstringKMP : 1,422 getSubstringNotSoNaive : 1,434     getSubstringBMBadCharacter : 925 getSubstringBMGoodSuffix : 363

Ожидаемо БМ с эвристикой плохого символа оказался похуже на данном замере, так как исходя из своей идеи он гораздо лучше работает на естественных текстах. Даже если в образце будут все символы из текста, то он сможет двигать паттерн на большее число шагов за раз, так как в естественном тексте все таки не случайное распределение символов.
Зато БМ со второй эвристикой чувствует себя как рыба в воде, потому что тексты со скудным набором символов это его специализация и он как раз таки используется в биоинформатике.
Несмотря на то, что в его основе лежит так же идея сравнения суффиксов, как и в КМП, он его обходит по скорости в три раза.
И это неспроста. КМП сначала сравнивает участок строки с паттерном и при разрыве совпадения переносит паттерн исходя из тех суффиксов, что он уже проверил. А БМ за счет большего анализа паттерна и сравнения справа налево при разрыве может перенести паттерн на большее число шагов, отчего у него и сравнений символа меньше в 5 раз и скорость выше в 3 раза.

Война и мир

Текст:

Паттерны:

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

Результаты

Ops/sec

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

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

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

Но давайте разберемся в причинах этого провала:

Несмотря на наименьшее количество сравнений, БМ с плохим символом оказался таким медленным в наших замерах. А все потому что в нем используется мапка, а не массив. Дело в том, что мапка это дополнительный слой абстракции который съел весь возможный профит от работы алгоритма, потому что запрос элемента у массива и запись в него это абсолютно не то же самое, что и в мапку. Так что тут вина на мне.

Но давайте попробуем его реабилитировать.

Проведем сравнительные замеры реализации алгоритма на массиве и на мапке.

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

export function badCharacterHeuristic(pattern: string, arraySize: number): number[] {     const result = new Array(arraySize);      for(let i = 0; i < pattern.length; i++) {        result[pattern.charCodeAt(i) % arraySize] = i;     }      return result; }

У функции добавлен параметр arraySize, чтобы не дублировать ее кучу раз, так как замеры я проводил на 9 разных длинах массива. Запись в массив идет через остаток от деления, так что у данного решения будут коллизии и ложные срабатывания, но куда подеваться, у нас строка в юникоде, а мы пытаемся запихивать это дело все в массив так, чтобы работало, причем быстро и не сильно поджирало память понапрасну.

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

Пример текста приводить не буду, статья, итак уже большая, но с параметрами ознакомимся.

Длинна текста: 10520
Алфавит: !'(),-.0123456789:;?ABCDEFGJLMNOQRS Vabcdefghijklmnopqrstuvxyz«»àèéêîôû́АБВГДЕЗИКМНО ПРСТУФЧШЭЯабвгдежзийклмнопрстуфхцчшщъыьэюя—
Размер алфавита: 128
Длины массивов для замера: 16, 32, 64, 128, 256, 1 024, 8 192, 23 770, 128 237
Длины паттернов: 1, 4, 8, 12, 24, 44, 80, 202

Поясню про длины массивов: экстремально малые я взял для того, чтобы проверить влияние коллизий, а последние два размера это размер китайской кодировки GBK и размер заполненной части юникода (ну с запасом, конечно).

Результаты замеров:

Для реализации на мапке (контрольный образец):

Серым помечена ячейка с выбросом.

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

Для реализации на массиве (опытный образец):

Красным выделены ячейки, где прослеживается тенденция к понижению производительности.

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

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

Производительность

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

Угол коллизий

Как можно увидеть, коллизии это все таки проблема, но проявились они на экстремально малых массивах, а именно на массивах которые меньше алфавита в 8 раз и 4 раза. Даже массив размером в 2 раза меньше алфавита и тот не сильно просаживается в производительности. Но как мы можем заметить коллизии оказывают влияние не только исходя из размера массива, но и из размера паттерна, так как при возрастании длинны паттерна возрастает вероятность заработать больше коллизий, которые будут мешать делать полные переносы паттерна.

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

Пояс смерти

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

Выводы

Если мы с вами добавим к сравнению реализацию на массивах к предыдущим замерам, то получим вот такой результат:

Псевдо ДНК:

getSubstringNaive: 6,284 getSubstringKMP: 161,315 getSubstringNotSoNaive: 180,887 getSubstringBMBadCharacter: 75,085 getSubstringBMGoodSuffix: 508,159 

Война и мир:

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

Изначально я искренне заблуждаясь решил: «А почему бы собственно не использовать и мапку, ведь вроде как все равно быстро должно выйти, чего там?», хотя я понимал, что это привнесет накладные расходу, но по наивности их недооценил, потом я начал играться с массивами и получил вот такой вот результат.

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

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

Сложность алгоритма

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

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

Для начала посчитаем количество вхождений всех символов:

 : 288    о: 136    н: 110    е: 101    и: 91      а: 89     с: 66     т: 66     д: 57     в: 56      р: 55     л: 51     м: 51     ,: 48     ы: 41      у: 36     б: 35     я: 34     к: 32     з: 28     ь: 24     п: 23     ж: 22     г: 15     ч: 14     .: 13     й: 13     ю: 13     ш: 9      х: 8     —: 7      э: 6      В: 5      !: 4      ц: 4     А: 3      -: 2      «: 2      »: 2      К: 2    Н: 2      Ц: 2      щ: 2      Д: 1      И: 1     С: 1      Т: 1      Э: 1

Всего символов в строке у нас 1673.

Частота — суммарная частота появления уникальных символов из паттерна
Вероятность — вероятность того, что символ текста при сравнении присутствует в паттерне
Мат. Ожидание полного переноса — это ожидание того, что при отсутствии сравниваемого символа в паттерне мы сделаем полный перенос паттерна, рассчитывается как .

Но следует помнить, что если вероятность будет равна единице, то мы все равно переместимся на один символ:)

То есть условно при каждой проверке для слова дуб мы будем перемещаться в среднем на 2.8 символа за раз. Что радует эти данные коррелируют как и с замерами производительности, так и с замерами подсчетов.

Ну и легко посчитать, что при , мы пролетим наш текст за , а при P = 1 за .

Для эвристики хорошего суффикса я такое рассчитать не возьмусь:)

Но вообще, считается, что для естественных текстов ее сложность в среднем стремится к .

Выводы

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

P.S.

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