Алгоритм поиска строки Бойера — Мура — алгоритм общего назначения, предназначенный для поиска подстроки в строке. Разработан и в 1977 году. Преимущество этого алгоритма в том, что ценой некоторого количества предварительных вычислений над шаблоном (но не над строкой, в которой ведётся поиск), шаблон сравнивается с исходным текстом не во всех позициях — часть проверок пропускается как заведомо не дающая результата.
Общая оценка вычислительной сложности современного варианта алгоритма Бойера — Мура — , если не используется таблица стоп-символов (смотрите ниже), и , если используется таблица стоп-символов, где — длина строки, в которой выполняется поиск, — длина шаблона поиска, — алфавит, на котором проводится сравнение.
Описание алгоритма Алгоритм основан на трёх идеях.
1. Сканирование слева направо, сравнение справа налево. Совмещается начало текста (строки) и шаблона, проверка начинается с последнего символа шаблона. Если символы совпадают, производится сравнение предпоследнего символа шаблона и т. д. Если все символы шаблона совпали с наложенными символами строки, значит, подстрока найдена, и выполняется поиск следующего вхождения подстроки.
Если же какой-то символ шаблона не совпадает с соответствующим символом строки, шаблон сдвигается на несколько символов вправо, и проверка снова начинается с последнего символа.
Эти «несколько», упомянутые в предыдущем абзаце, вычисляются по двум эвристикам.
2. Эвристика стоп-символа. (Замечание: эвристика стоп-символа присутствует в большинстве описаний алгоритма Бойера — Мура, включая оригинальную статью Бойера и Мура, но не является необходимой для достижения оценки времени работы; более того, данная эвристика для своей работы требует дополнительной памяти и дополнительного времени на этапе подготовки шаблона.)
Предположим, что мы производим поиск слова «колокол». Первая же буква не совпала — «к» (назовём эту букву стоп-символом). Тогда можно сдвинуть шаблон вправо до последней его буквы «к».
Строка: * * * * * * к * * * * * * Шаблон: к о л о к о л Следующий шаг: к о л о к о л
Если стоп-символа в шаблоне нет, шаблон смещается за этот стоп-символ.
Строка: * * * * * а л * * * * * * * * Шаблон: к о л о к о л Следующий шаг: к о л о к о л
В данном случае стоп-символ — «а», и шаблон сдвигается так, чтобы он оказался прямо за этой буквой. В алгоритме Бойера — Мура эвристика стоп-символа вообще не смотрит на совпавший суффикс (см. ниже), так что первая буква шаблона («к») окажется под «л», и будет проведена одна заведомо холостая проверка.
Если стоп-символ «к» оказался за другой буквой «к», эвристика стоп-символа не работает.
Строка: * * * * к к о л * * * * * Шаблон: к о л о к о л Следующий шаг: к о л о к о л
В таких ситуациях выручает третья идея алгоритма Бойера — Мура — эвристика совпавшего суффикса.
3. Эвристика совпавшего суффикса. Неформально, если при чтении шаблона справа налево совпал суффикс S, а символ b, стоящий перед S в шаблоне (то есть шаблон имеет вид PbS), не совпал, то эвристика совпавшего суффикса сдвигает шаблон на наименьшее число позиций вправо так, чтобы строка S совпала с шаблоном, а символ, предшествующий в шаблоне данному совпадению S, отличался бы от b (если такой символ вообще есть). Формально, для данного шаблона считается целочисленный массив suffshift[0..m], в котором suffshift[i] равно минимальному числу , такому что (если и ) и для любого , для которого выполняется и (для пояснения смотрите примеры ниже). Затем, если при чтении шаблона справа налево совпало символов , а символ не совпал, то шаблон сдвигается на suffshift[m-k] символов вправо. Например:
Строка: * * * * * * р к а * * * * * Шаблон: с к а л к а л к а Следующий шаг: с к а л к а л к а
В данном случае совпал суффикс «ка», и шаблон сдвигается вправо до ближайшего «ка», перед которым нет буквы «л».
Строка: * * т о к о л * * * * * Шаблон: к о л о к о л Следующий шаг: к о л о к о л
В данном случае совпал суффикс «окол», и шаблон сдвигается вправо до ближайшего «окол», перед которым нет буквы «л». Если подстроки «окол» в шаблоне больше нет, но он начинается на «кол», сдвигается до «кол», и т. д.
Внимание: несовпадение буквы перед ближайшим вхождением совпавшего суффикса является необходимым условием. Если ограничиться только сдвигом до ближайшего вхождения совпавшего суффикса, то алгоритм может работать неприемлемо медленно. Например, при поиске шаблона длины в строке , содержащей символов «a», за которыми следует строка длины , алгоритм, использующий сдвиги без учёта несовпадения символа, выполняет операций даже при использовании эвристики стоп-символов. С другой стороны доказано, что время работы алгоритма БМ, учитывающего несовпадение символов (то есть использующего массив suffshift, определённый выше), равно даже без использования эвристики стоп-символов (данное в книге М. Крошмора и В. Риттера доказательство этого факта является модификацией доказательства Коула 1994 года, рассмотревшего только случай непериодических шаблонов).
Обе эвристики требуют предварительных вычислений — в зависимости от шаблона поиска заполняются две таблицы. Таблица стоп-символов по размеру соответствует алфавиту — (например, если алфавит состоит из 256 символов, то её длина 256); таблица суффиксов — искомому шаблону, то есть .
Опишем подробнее обе таблицы.
Таблица стоп-символов В таблице стоп-символов указывается последняя позиция в шаблоне (исключая последнюю букву) каждого из символов алфавита. Для всех символов, не вошедших в , пишем 0, если нумерация символов начинается с 1 (или −1, если нумерация начинается с 0). Например, если , таблица стоп-символов StopTable будет выглядеть так (таблица приведена для случая строки, нумеруемой с нуля; при нумерации символов с единицы нужно прибавить ко всем числам единицу):
Символ a b c d [все остальные] Последняя позиция 4 1 6 5 -1
Обратите внимание, для стоп-символа «d» последняя позиция будет 5, а не 7 — последняя буква не учитывается. Это известная ошибка, приводящая к неоптимальности. Для алгоритма БМ она не фатальна (спасает положение эвристика суффикса), но фатальна для упрощённой версии алгоритма БМ — алгоритма Хорспула.
Если при сравнении справа налево шаблона со строкой несовпадение произошло в позиции , а стоп-символ — , то шаблон необходимо сдвинуть на символов.
Таблица суффиксов Для каждого возможного суффикса данного шаблона указываем наименьшую величину, на которую нужно сдвинуть вправо шаблон, чтобы он снова совпал с и при этом символ, предшествующий этому вхождению , не совпадал бы с символом, предшествующим суффиксу . Если такой сдвиг невозможен, ставится (в обеих системах нумерации). Например, для будет:
Суффикс [пустой] c cc bcc ... aaccbccbcc Сдвиг 2 1 6 10 ... 10 Иллюстрация было ? ?c ?cc ?bcc ... aaccbccbcc стало aaccbccbcc aaccbccbcc aaccbccbcc aaccbccbcc ... aaccbccbcc
Для «колокол»:
Суффикс [пустой] л ол кол ... олокол колокол Сдвиг 1 7 7 4 ... 4 4 Иллюстрация было ? ?л ?ол ?кол ... ?олокол колокол стало колокол колокол колокол колокол ... колокол колокол
Существует алгоритм вычисления таблицы суффиксов suffshift[0..m] с временем работы . Этот алгоритм основан на тех же идеях, что и алгоритмы вычисления префикс-функции и Z-функции строки. Реализация данного алгоритма на 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-функции , но для перевёрнутой строки . А именно, для любого , такого что , элемент содержит длину длиннейшего суффикса строки , который также является суффиксом всей строки . С помощью массива далее вычисляется искомый массив suffshift[0..m] (смотрите описание ниже). На каждой итерации последнего цикла уменьшается на 1, а на каждой итерации вложенного в него цикла уменьшается на 1. Поэтому, так как , , и алгоритм вычисления Z-функции работает за (смотрите, например, соответствующую статью, а также статью), общее время работы данного алгоритма — .
Для доказательства корректности представленного кода удобно представлять себе, что анализируется строка , которая равна перевёрнутой строке . По определению suffshift, имеем suffshift[], где — это наименьшее положительное число, такое что либо 1) строка является префиксом строки , либо 2) строка равна , а символы и отличаются. В случае 2), по определению , обязательно выполняется . Таким образом, пробегая по от до 1, цикл № 1 находит все значения suffshift, полученные по правилу 2). Для вычисления значений suffshift, полученных по правилу 1), заметим, что, во-первых, если — префикс , то обязательно выполняется , а во-вторых, если suffshift[] = для какого-то , то обязательно . Опираясь на эти два наблюдения, цикл № 2 вычисляет оставшиеся неинициализированными значения suffshift (то есть такие что suffshift[k] = m).
Реализация алгоритма
Пусть массив сдвигов suffshift[0..m] для данного шаблона посчитан. Тогда реализация на C++ алгоритма Бойера — Мура для поиска первого вхождения в тексте за времени без применения эвристики стоп-символов выглядит следующим образом:
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);
Такой алгоритм непригоден для поиска всех вхождений шаблона в текст за времени. Если убрать условие «j >= 0» из внешнего цикла, то алгоритм найдёт все вхождения, но в худшем случае, возможно, выполнит операций, в чём легко убедиться, рассмотрев строку, состоящую из одних букв «a». Для поиска всех вхождений используют следующую модификацию, которая работает времени за счёт так называемого правила Галиля:
int j, bound = 0; //всегда либо bound = 0, либо bound = m - suffshift 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; j = -1; //установить j так, как будто мы прочитали весь шаблон s, а не только до границы bound } else { bound = 0;
Правило Галиля основано на следующем несложном наблюдении. Если вхождение найдено в позиции , то следующий поиск будет пытаться найти вхождение шаблона в позиции suffshift и, по определению suffshift, уже известно, что символы совпадают с символами suffshift. Значит, при выполнении поиска справа налево для определения того, есть ли вхождение шаблона в позиции , нет смысла проверять символы suffshift. Именно для этого и служит переменная «bound». Доказано, что такая эвристика помогает получить времени для поиска всех вхождений шаблона в строку.
Для включения эвристики стоп-символов достаточно строку «i += suffshift[j+1]» заменить на следующее выражение в конце основного цикла: if (j < bound) i += suffshift[j+1]; else i += max(suffshift[j+1], j - StopTable[text[i + j]]);
Пример работы алгоритма Искомый шаблон — «abbad». Таблица стоп-символов будет выглядеть как (в данном примере будет удобнее пользоваться нумерацией с единицы)
Символ a b d [остальные] Позиция 1 2 5 0
Таблица суффиксов для всех возможных суффиксов (кроме пустого) даёт максимальный сдвиг — 5.
abeccaabadbabbad abbad
Накладываем образец на строку. Совпадения суффикса нет — таблица суффиксов даёт сдвиг на одну позицию. Для несовпавшего символа исходной строки «с» (5-я позиция) в таблице стоп-символов записан 0. Сдвигаем образец вправо на 5-0=5 позиций.
abeccaabadbabbad abbad