Алгоритм Бойера — Мура

В таблице стоп-символов указывается последняя позиция в шаблоне ${\displaystyle s}$ (исключая последнюю букву) каждого из символов алфавита. Для всех символов, не вошедших в ${\displaystyle s}$, пишем 0, если нумерация символов начинается с 1 (или −1, если нумерация начинается с 0). Например, если ${\displaystyle s=abcdadcd}$, таблица стоп-символов StopTable будет выглядеть так (таблица приведена для случая строки, нумеруемой с нуля; при нумерации символов с единицы нужно прибавить ко всем числам единицу):

Символ              a  b  c  d  [все остальные]
Последняя позиция   4  1  6  5  -1

Обратите внимание, для стоп-символа «d» последняя позиция будет 5, а не 7 — последняя буква не учитывается. Это известная ошибка, приводящая к неоптимальности. Для алгоритма БМ она не фатальна (спасает положение эвристика суффикса), но фатальна для упрощённой версии алгоритма БМ — алгоритма Хорспула.

Если при сравнении справа налево шаблона ${\displaystyle s[0..m{-}1]}$ со строкой ${\displaystyle text[i..i{+}m{-}1]}$ несовпадение произошло в позиции ${\displaystyle j}$, а стоп-символ — ${\displaystyle c=text[j]}$, то шаблон необходимо сдвинуть на ${\displaystyle i'=j-StopTable[c]}$ символов.

Для каждого возможного суффикса ${\displaystyle t}$ данного шаблона ${\displaystyle s}$ указываем наименьшую величину, на которую нужно сдвинуть вправо шаблон, чтобы он снова совпал с ${\displaystyle t}$ и при этом символ, предшествующий этому вхождению ${\displaystyle t}$, не совпадал бы с символом, предшествующим суффиксу ${\displaystyle t}$. Если такой сдвиг невозможен, ставится ${\displaystyle |s|=m}$ (в обеих системах нумерации). Например, для ${\displaystyle s=aaccbccbcc}$ будет:

Суффикс        [пустой]         c       cc        bcc            ...   aaccbccbcc
Сдвиг               2           1        6         10            ...           10
Иллюстрация
    было            ?          ?c      ?cc       ?bcc            ...   aaccbccbcc
    стало    aaccbccbcc aaccbccbcc    aaccbccbcc     aaccbccbcc  ...             aaccbccbcc

Для ${\displaystyle s=}$«колокол»:

Суффикс      [пустой]        л         ол        кол       ...  олокол        колокол
Сдвиг              1         7          7        4         ...       4              4
Иллюстрация
    было           ?        ?л        ?ол        ?кол      ... ?олокол        колокол
    стало     колокол         колокол    колокол  колокол  ...     колокол        колокол

Существует алгоритм вычисления таблицы суффиксов suffshift[0..m] с временем работы ${\displaystyle O(m)}$.[2] Этот алгоритм основан на тех же идеях, что и алгоритмы вычисления префикс-функции и Z-функции строки[4][5]. Реализация данного алгоритма на C++ выглядит следующим образом:

 std::vector<int> suffshift(m + 1, m);
 std::vector<int> z(m, 0);
 for (int j = 1, maxZidx = 0, maxZ = 0; j < m; ++j) {
   if (j <= maxZ) z[j] = std::min(maxZ - j + 1, z[j - maxZidx]);
   while (j + z[j] < m && s[m - 1 - z[j]] == s[m - 1 - (j + z[j])]) z[j]++;
   if (j + z[j] - 1 > maxZ) {
     maxZidx = j;
     maxZ = j + z[j] - 1;
   }
 }
 for (int j = m - 1; j > 0; j--) suffshift[m - z[j]] = j; //цикл №1
 for (int j = 1, r = 0; j <= m - 1; j++) //цикл №2
   if (j + z[j] == m)
     for (; r <= j; r++)
       if (suffshift[r] == m) suffshift[r] = j;

В первом цикле в коде воспроизведён код вычисления так называемой Z-функции ${\displaystyle z[1..m{-}1]}$, но для перевёрнутой строки ${\displaystyle s[0..m-1]}$.[5] А именно, для любого ${\displaystyle j}$, такого что ${\displaystyle 0\leq j<m-1}$, элемент ${\displaystyle z[m-1-j]}$ содержит длину длиннейшего суффикса строки ${\displaystyle s[0..j]}$, который также является суффиксом всей строки ${\displaystyle s}$. С помощью массива ${\displaystyle z}$ далее вычисляется искомый массив suffshift[0..m] (смотрите описание ниже). На каждой итерации последнего цикла ${\displaystyle j}$ уменьшается на 1, а на каждой итерации вложенного в него цикла ${\displaystyle k}$ уменьшается на 1. Поэтому, так как ${\displaystyle j\geq 0}$, ${\displaystyle k\geq 0}$, и алгоритм вычисления Z-функции работает за ${\displaystyle O(m)}$ (смотрите, например, соответствующую статью, а также статью[5]), общее время работы данного алгоритма — ${\displaystyle O(m)}$.

Для доказательства корректности представленного кода удобно представлять себе, что анализируется строка ${\displaystyle s'[0..m{-}1]}$, которая равна перевёрнутой строке ${\displaystyle s}$. По определению suffshift, имеем suffshift[${\displaystyle m-k}$]${\displaystyle =j}$, где ${\displaystyle j}$ — это наименьшее положительное число, такое что либо 1) строка ${\displaystyle s'[j..m{-}1]}$ является префиксом строки ${\displaystyle s'[0..k{-}1]}$, либо 2) строка ${\displaystyle s'[j..j{+}k{-}1]}$ равна ${\displaystyle s'[0..k{-}1]}$, а символы ${\displaystyle s'[j{+}k]}$ и ${\displaystyle s'[k]}$ отличаются. В случае 2), по определению ${\displaystyle z}$, обязательно выполняется ${\displaystyle z[j]=k}$. Таким образом, пробегая по ${\displaystyle j}$ от ${\displaystyle m-1}$ до 1, цикл № 1 находит все значения suffshift, полученные по правилу 2). Для вычисления значений suffshift, полученных по правилу 1), заметим, что, во-первых, если ${\displaystyle s'[j..m{-}1]}$ — префикс ${\displaystyle s'[0..k{-}1]}$, то обязательно выполняется ${\displaystyle j+z[j]=m}$, а во-вторых, если suffshift[${\displaystyle r}$] = ${\displaystyle j}$ для какого-то ${\displaystyle r}$, то обязательно ${\displaystyle r\leq j}$. Опираясь на эти два наблюдения, цикл № 2 вычисляет оставшиеся неинициализированными значения suffshift (то есть такие что suffshift[k] = m).

Пусть массив сдвигов suffshift[0..m] для данного шаблона ${\displaystyle s[0..m{-}1]}$ посчитан. Тогда реализация на C++ алгоритма Бойера — Мура для поиска первого вхождения ${\displaystyle s}$ в тексте ${\displaystyle text[0..n{-}1]}$ за ${\displaystyle O(n+m)}$ времени без применения эвристики стоп-символов выглядит следующим образом[2]:

 for (int i = 0, j = 0; i <= n - m && j >= 0; i += suffshift[j+1]) {
   for (j = m - 1; j >= 0 && s[j] == text[i + j]; j--);
   if (j < 0) report_occurrence(i);
 }

Такой алгоритм непригоден для поиска всех вхождений шаблона в текст за ${\displaystyle O(m+n)}$ времени. Если убрать условие «j >= 0» из внешнего цикла, то алгоритм найдёт все вхождения, но в худшем случае, возможно, выполнит ${\displaystyle O(mn)}$ операций, в чём легко убедиться, рассмотрев строку, состоящую из одних букв «a». Для поиска всех вхождений используют следующую модификацию, которая работает ${\displaystyle O(n+m)}$ времени за счёт так называемого правила Галиля[6]:

 int j, bound = 0; //всегда либо bound = 0, либо bound = m - suffshift[0]
 for (int i = 0; i <= n - m; i += suffshift[j+1]) {
   for (j = m - 1; j >= bound && s[j] == text[i + j]; j--);
   if (j < bound) {
     report_occurrence(i);
     bound = m - suffshift[0];
     j = -1; //установить j так, как будто мы прочитали весь шаблон s, а не только до границы bound
   } else {
     bound = 0;
   }
 }

Правило Галиля основано на следующем несложном наблюдении. Если вхождение ${\displaystyle s}$ найдено в позиции ${\displaystyle i}$, то следующий поиск будет пытаться найти вхождение шаблона в позиции ${\displaystyle i'=i+}$suffshift[0] и, по определению suffshift, уже известно, что символы ${\displaystyle s[i'],s[i'{+}1],\ldots ,s[i{+}m{-}1]}$ совпадают с символами ${\displaystyle s[0],s[1],\ldots ,s[m{-}}$suffshift[0]${\displaystyle {-}1]}$. Значит, при выполнении поиска справа налево для определения того, есть ли вхождение шаблона в позиции ${\displaystyle i'}$, нет смысла проверять символы ${\displaystyle s[0],s[1],\ldots ,s[m{-}}$suffshift[0]${\displaystyle {-}1]}$. Именно для этого и служит переменная «bound». Доказано, что такая эвристика помогает получить ${\displaystyle O(n+m)}$ времени для поиска всех вхождений шаблона в строку[6].

Для включения эвристики стоп-символов достаточно строку «i += suffshift[j+1]» заменить на следующее выражение в конце основного цикла:

  if (j < bound) i += suffshift[j+1]; 
  else i += max(suffshift[j+1], j - StopTable[text[i + j]]);

Алгоритм Бойера — Мура — Хорспула (АБМХ) работает лучше алгоритма Бойера — Мура (АБМ) на случайных текстах — для него оценка в среднем лучше.

АБМХ использует только эвристику стоп-символа; при этом за стоп-символ берётся символ входной строки, который соответствует последнему символу шаблона, независимо от того, где случилось несовпадение.

Поскольку реальные поисковые образцы редко имеют равномерное распределение, АБМХ может дать как выигрыш, так и проигрыш по сравнению с АБМ.

На коротких алфавитах (например, при сравнении участков ДНК алфавит состоит всего из четырёх символов: A, Т, Г, Ц) эвристика стоп-символа отказывает уже на коротких суффиксах. Простейший способ улучшить работу АБМ в таких условиях — вместо одного стоп-символа строить таблицу для пары символов: несовпавшего и идущего перед ним[7]. Такой алгоритм был назван алгоритмом Чжу — Такаоки.

На предварительную обработку расходуется ${\displaystyle O(m+|\Sigma |^{2})}$ времени.

Алгоритм «турбо-Бойера — Мура» разработан группой учёных во главе с М. Крошмором, предлагает другой подход к коротким алфавитам и заодно решает вторую проблему — квадратичную сложность в худшем случае.

Помимо эвристики стоп-символа и эвристики совпавшего суффикса, применяется третья эвристика — эвристика турбосдвига[8].

Пусть первый раз совпал суффикс UV (и сработала эвристика суффиксов, обеспечив полное перекрытие этого суффикса), второй раз — более короткий V (возможно, V=∅).

                                               !                     !
входная строка:      * * * * * * * * * * # [-U-] [V] * * * * * * * * # [V] * * * * * *
1. Совпало UV:         * [-U-] [V] * * * * [-U-] [V]
2. Затем совпало V:                      * [-U-] [V] * * * * * * [-U-] [V]
Сдвиг по эвристике суффиксов:                * [-U-] [V] * * * * * * [-U-] [V]
Турбосдвиг:                                    * [-U-] [V] * * * * * * [-U-] [V]

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

Алгоритм выполняет свою работу за ${\displaystyle 2n}$ сравнений до первого совпадения в худшем случае.

Алгоритм Бойера — Мура на «хороших» данных очень быстр^{[уточнить]}, а вероятность появления «плохих» данных крайне мала. Поэтому он оптимален в большинстве случаев, когда нет возможности провести предварительную обработку текста, в котором проводится поиск[9]. Разве что на коротких текстах выигрыш не оправдает предварительных вычислений.

Алгоритмы семейства Бойера — Мура не расширяются до приблизительного поиска, поиска любой строки из нескольких.

Сравнение не является «чёрным ящиком» (только если применяется эвристика стоп-символа), поэтому при реализации наиболее быстрого поиска приходится либо рассчитывать на удачную работу оптимизатора, либо вручную оптимизировать поиск на языке ассемблера.

Если текст изменяется редко, а поиск проводится часто (например, поисковой машиной), можно провести индексацию текста. Алгоритм поиска по индексу быстрее^{[уточнить]} алгоритма Бойера — Мура.

На больших алфавитах (например, Юникод) таблица стоп-символов может занимать много памяти. В таких случаях либо обходятся хеш-таблицами, либо дробят алфавит, рассматривая, например, 4-байтовый символ как пару двухбайтовых, либо (что проще всего) пользуются вариантом алгоритма Бойера — Мура без эвристики стоп-символов.

Существует ряд модификаций алгоритма Бойера — Мура, нацеленных на ещё большее ускорение — например, турбо-алгоритм, обратный алгоритм Колусси[10] и другие.