Алгоритм бойера мура таблица суффиксов

Сканирование слева направо, сравнение справа налево.

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

Данный алгоритм был разработан двумя учеными — Робертом Бойером (англ. Robert Stephen Boyer) и Джеем Муром (англ. J Strother Moore) в 1977 году. Он считается наиболее быстрым среди алгоритмов общего назначения, предназначенных для поиска подстроки в строке.

Вопрос: что значит алгоритмы «общего назначения»?

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

Алфавит — конечное множество символов.

Подстрока — это последовательность подряд идущих символов в строке.

Строка — последовательность символов текста.

Суффикс — это подстрока, заканчивающаяся на последний символ строки.

В определении строки речь не обязательно должна идти именно о тексте.

В общем случае строка — это любая последовательность байтов.

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

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

Алгоритма Бойера — Мура можно представить в виде двух простых шагов.

Для искомого образца строим две таблицы — таблицу стоп-символов и таблицу суффиксов.

Процесс построения таблиц будет описан ниже.

Совмещаем начало строки и образца и начинаем проверку с последнего символа образца.

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

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

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

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

1) Значение, полученное с помощью таблицы стоп-символов по простому правилу:

Если несовпадение произошло на позиции , а стоп-символ « », то значение величины сдвига будет равно .

— позиция символа в образце (нумерация с 1);

— значение, записанное в таблице стоп-символов, для символа «c».

2) Значение, полученное из таблицы суффиксов.

Подробное описание работы алгоритма

Псевдокод: алгоритм Бойера — Мура

Boyer-Moore-Matcher( )

1.

2. m

3. Compute-Last-Occurrence-Function( )

4. Compute-Good-Suffix-Function( )

5.

6. while

7. do

8. while and

9. do

10. if

11. then print «Образец входит со сдвигом» s

12.

13. else

Алгоритм основан на трёх идеях.

Сканирование слева направо, сравнение справа налево.

Совмещается начало текста (строки) и шаблона, проверка начинается с последнего символа шаблона.

Если символы совпадают, производится сравнение предпоследнего символа шаблона и т. д.

Если все символы шаблона совпали с наложенными символами строки, значит, подстрока найдена, и поиск окончен.

Если же какой-то символ шаблона не совпадает с соответствующим символом строки, шаблон сдвигается на несколько символов вправо, и проверка снова начинается с последнего символа.

Эти «несколько», упомянутые в предыдущем абзаце, вычисляются по двум эвристикам.

Вопрос: что такое эвристика?

Ответ: эвристика — это не полностью математически обоснованный (или даже «не совсем корректный»), но при этом практически полезный алгоритм.

2. Эвристика стоп-символа(англ. bad-character heuristic).

Стоп-символ — это первый справа символ в строке, отличный от соответствующего символа в образце.

Эвристика стоп-символа предлагает попробовать новое значение сдвига, исходя из того, где в образце встречается стоп-символ (если вообще встречается).

В наиболее удачном случае стоп-символ выявляется при первом же сравнении и не встречается нигде в образце.

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

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

В общем случае эвристика стоп-символа работает так. Предположим, что при сравнении права налево мы наткнулись на первое несовпадение: , где . Пусть — номер самого правого вхождения символа в образец (если этот символ вообще не появляется в образце, считаем равным ). Мы утверждаем, что можно увеличить на , не упустив ни одного допустимого сдвига.

В самом деле, если , то стоп-символ вообще не встречается в образце , так что можно сразу сдвинуть образец на позиций вправо.

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

Наконец, если , то эвристика предлагает сдвигать образец не вправо, а влево; алгоритм Бойера — Мура эту рекомендацию игнорирует, поскольку эвристика безопасного суффикса всегда предлагает ненулевой сдвиг вправо.

Чтобы применять эвристику стоп-символа полезно для каждого возможного стоп-символа вычислить значение . Это делается простой процедурой Compute-Last-Occurrence-Function («найти последнее вхождение»), которая для каждого вычисляет — номер крайнего правого вхождения в , или нуль, если в не входит. В этих обозначениях приращение сдвига, диктуемое эвристикой стоп-символа, есть , как и написано в строке 13 алгоритма Boyer-Moore-Matcher.

Псевдокод: найти последнее вхождение стоп-символа в подстроку

Compute-Last-Occurrence-Function( )

1. for each character

2. do

3. for to

4. do

5. return

Время работы процедуры Compute-Last-Occurrence-Function есть

Пример использования эвристики стоп-символа:

Предположим, что мы производим поиск слова «колокол».

Первая же буква не совпала — «к» (назовём эту букву стоп-символом).

Тогда можно сдвинуть шаблон вправо до последней буквы «к».

Шаблон: к о л о к о л

Следующий шаг: к о л о к о л

Если стоп-символа в шаблоне вообще нет, шаблон смещается за этот стоп-символ.

Строка: * * * * * а л * * * * * * * *

Шаблон: к о л о к о л

Следующий шаг: к о л о к о л

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

Если стоп-символ «к» оказался за другой буквой «к», эвристика стоп-символа не работает.

Строка: * * * * к к о л * * * * *

Шаблон: к о л о к о л

Следующий шаг: к о л о к о л .

В таких ситуациях выручает третья идея алгоритма — эвристика совпавшего суффикса.

3. Эвристика безопасного (совпавшего) суффикса(англ. good-suffix heuristic).

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

Эвристика безопасного суффикса состоит в следующем: если , где (и число — наибольшее с таким свойством), то мы можем безбоязненно увеличить сдвиг на

Иными словами, — наименьшее расстояние, на которое мы можем сдвинуть образец без того, чтобы какой- то из символов, входящих в «безопасный суффикс» оказался напротив несовпадающего с ним символа из образца. Поскольку строка заведомо сравнима с пустой строкой , число корректно определено для всех . Стоит также заметить, что для всех , так что на каждом шаге алгоритма Бойера — Мура образец будет сдвигаться вправо хотя бы на одну позицию. Мы будем называть функцией безопасного суффикса (англ. good-suffix function), ассоциированной со строкой .

Псевдокод: вычисление функции безопасных суффиксов

Compute-Good-Suffix-Function( )

2. pi[] = префикс-функция(P)

3. pi1[] = префикс-функция(обращение(P))

5. suffshift[j] = m — pi[m]

8. suffshift[j] = min(suffshift[j], i — pi1[i])

Время работы процедуры Compute-Good-Suffix-Function есть .

Пример использования эвристики безопасного (совпавшего) суффикса:

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

Строка: * * т о к о л * * * * *

Шаблон: к о л о к о л

Следующий шаг: к о л о к о л

В данном случае совпал суффикс «окол», и шаблон сдвигается вправо до ближайшего «окол». Если подстроки «окол» в шаблоне больше нет, но он начинается на «кол», сдвигается до «кол», и т. д.

Обе эвристики требуют предварительных вычислений — в зависимости от шаблона поиска заполняются две таблицы. Таблица стоп-символов по размеру соответствует алфавиту (например, если алфавит состоит из 256 символов, то её длина 256); таблица суффиксов — искомому шаблону. Именно из-за этого алгоритм Бойера — Мура не учитывает совпавший суффикс и несовпавший символ одновременно — это потребовало бы слишком много предварительных вычислений.

Опишем подробнее обе таблицы.

Таблица стоп-символов

Считается, что символы строк нумеруются с 1 (как в Паскале).

В таблице стоп-символов указывается последняя позиция в образце (исключая последнюю букву) каждого из символов алфавита. Для всех символов, не вошедших в образец , пишем 0 (для нумерации с 0 — соответственно, −1).

Например, если , таблица стоп-символов будет выглядеть так.

Символ a b c d [все остальные]

Последняя позиция 5 2 7 6 0

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

Если несовпадение произошло на позиции , а стоп-символ , то сдвиг будет .

Таблица суффиксов

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

Суффикс [пустой] d cd dcd . abcdadcd

Сдвиг 1 2 4 8 . 8

было ? ?d ?cd ?dcd . abcdadcd

стало abcdadcd abcdadcd abcdadcd abcdadcd . abcdadcd

Если шаблон начинается и заканчивается одной и той же комбинацией букв, вообще не появится в таблице.

Например, для для всех суффиксов (кроме, естественно, пустого) сдвиг будет равен 4.

Суффикс [пустой] л ол . олокол колокол

Сдвиг 1 4 4 . 4 4

было ? ?л ?ол . ?олокол колокол

стало колокол колокол колокол . колокол колокол

Пусть у нас есть набор символов (алфавит) из пяти символов: и мы хотим найти вхождение образца “ ” в строке “ ”. Следующие схемы иллюстрируют все этапы выполнения алгоритма:

Если несовпадение произошло на позиции , а стоп-символ , то сдвиг будет .

Таблица суффиксов для образца “ ”.

Суффикс [пустой] d ad bad bbad abbad

Сдвиг 1 5 5 5 5 5

было ? ?d ?ad ?bad ?bbad abbad

стало abbad abbad abbad abbad abbad abbad

a b e c c a a b a d b a b b a d

Накладываем образец на строку. Совпадения суффикса нет — таблица суффиксов даёт сдвиг на одну позицию. Для несовпавшего символа исходной строки «с» (5-я позиция) в таблице стоп-символов записан 0. Сдвигаем образец вправо на 5-0=5 позиций:

a b e c c a a b a d b a b b a d

Символы 3—5 совпали, а второй — нет. Эвристика стоп-символа для «а» не работает (2-4=-2). Но поскольку часть символов совпала, в дело включается эвристика совпавшего суффикса, сдвигающая образец сразу на пять позиций!

a b e c c a a b a d b a b b a d

И снова совпадения суффикса нет. В соответствии с таблицей стоп-символов сдвигаем образец на 1 позицию и получаем искомое вхождение образца:

a b e c c a a b a d b a b b a d

Вычислительная сложность

Общая оценка вычислительной сложности алгоритма — на непериодических шаблонах и на периодических, где n — строка, в которой выполняется поиск, m — шаблон поиска, Σ — алфавит, на котором проводится сравнение. В 1991 году Коул показал, что на непериодических шаблонах за полный проход по строке алгоритм совершит не более сравнений.

Время исполнения алгоритма Бойера — Мура в наихудшем случае есть , поскольку на исполнение Compute-Last-Occurrence-Function уходит время , на Compute-Good-Suffix-Function уходит , и в худшем случае алгоритм Бойера — Мура (как и алгоритм Рабина — Карпа) потратит время на проверку каждого априори возможного сдвига. На практике, однако, именно алгоритм Бойера — Мура часто оказывается наиболее эффективным.

Выводы

Достоинства

Алгоритм Бойера-Мура на «хороших» данных очень быстр, а вероятность появления «плохих» данных крайне мала. Поэтому он оптимален в большинстве случаев, когда нет возможности провести предварительную обработку текста, в котором проводится поиск (haystack). Разве что на коротких текстах выигрыш не оправдает предварительных вычислений.

haystack — строка, в которой выполняется поиск.

В переводе на русский haystack дословно означает «стог сена».

Недостатки

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

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

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

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

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

Итог

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

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

Кормен Т., Лейзерсон Ч., Ривест Р. «Алгоритмы: построение и анализ».-М.:МЦНМО,1999, с.801 – 806

Упрощенный алгоритм Бойера-Мура

Алгоритм

Данный алгоритм также известен под названием алгоритм Бойера-Мура-Хорспула. Процедура алгоритма очень простая. Сначала строится таблица смещений для каждого символа. Затем исходная строка и шаблон совмещаются по началу, сравнение ведется по последнему символу. Если последние символы совпадают, то сравнение идет по предпоследнему символу и так далее. Если же символы не совпали, то шаблон смещается вправо, на число позиций взятое из таблицы смещений для символа из исходной строки, и тогда снова сравниваются последние символы исходной строки и шаблона. И так далее, пока не шаблон полностью не совпадет с подстрокой исходной строки, или не будет достигнут конец строки.

Таблица смещений

Таблица смещений строится по принципу «пропускать столько символов, сколько возможно, но не более этого». Например, если на каком-то шаге алгоритма последние символы не совпали, и символ, находящийся в исходной строке не присутствует в шаблоне вообще, то понятно, что можно сдвинуться вправо на полную длину шаблона, без каких-либо опасений. В общем случае, каждому символу ставится в соответствие величина, равная разности длины шаблона и порядкового номера символа (если символ повторяется, то берется самое правое вхождение). Ясно, что эта величина будет в точности равна порядковому номеру символа, если считать от конца строки, что и дает возможность смещаться вправо на максимально возможное число позиций.

Иллюстрация

Чтобы стало совсем понятно рассмотрим работу алгоритма на примере:
Пусть исходная строка равна «somestring» и шаблон равен «string». Теперь строим таблицу смещений, она будет равна длине шаблона для всех символов, которые не встречаются в шаблоне, и порядковому номеру с конца для остальных (кроме последнего, для него тоже берется длина шаблона):

s->5
t->4
r->3
i->2
n->1
g->6

Теперь совмещаем наши строки:
&nbsp somestring
&nbsp string

Сравниваем последние символы: видим, что «t» не равен «g». Берем значение смещения для символа «t», оно равно 4. Сдвигаем строку вправо на 4 позиции, и вуаля:

&nbsp somestring
&nbsp&nbsp&nbsp&nbsp&nbsp string

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

Написал немного кода на Java, чтобы сдобрить эту теорию. Любые замечания приветствуются.

Алгоритм бойера мура таблица суффиксов

В отличие от других алгоритмов сравнения строк («Стандартный алгоритм сравнения строк», «Алгоритм Кнута-Морриса-Пратта») алгоритм Бойера-Мура осуществляет сравнение с образцом справа налево, а не слева направо. Исследуя искомый образец, можно осуществить более эффективные прыжки в тексте при обнаружении несовпадения.
В примере ниже мы сначала сравниваем y с r и обнаруживаем несовпадение. Поскольку мы знаем, что буква r вообще не входит в образец, мы можем сдвинуться в тексте на целых четыре буквы (то есть на длину образца) вправо. Затем мы сравниваем букву y с h и вновь обнаруживаем несовпадение. Однако поскольку на этот раз h входит в образец, мы можем сдвинуться вправо только на две буквы так, чтобы буквы h совпали. Затем мы начинаем сравнение справа и обнаруживаем полное совпадение кусочка текста с образцом. В алгоритме Бойера-Мура делается 6 сравнений вместо 13 сравнений в стандартном алгоритме.

Подобное улучшение порождает одну проблему. При сравнении на в примере ниже происходит совпадение по буквам k, n, i, однако буква h в слове tinkle не совпадает с буквой t в слове think. Если мы ограничимся предложенным улучшением, то придется сдвинуться вправо по тексту всего на один символ, несмотря на то, что совпадение подстрок ink означает, что мы немедленно после сдвига наткнемся на несовпадение, и это несовпадение можно предугадать.

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

Алгоритм сравнения
Мы дали общее описание того, как будут использоваться массивы сдвигов и прыжков. Массив сдвигов содержит величины, на которые может быть сдвинут образец при несовпадении очередного символа. В массиве прыжков содержатся величины, на которые можно сдвинуть образец, чтобы совместить ранее совпавшие символы с вновь совпадающими символами строки. При несовпадении очередного символа образца с очередным символом текста может осуществиться несколько возможностей. Сдвиг в массиве сдвигов может превышать сдвиг в массиве прыжков, а может быть и наоборот. (Совпадение этих величин — простейшая возможная ситуация.) О чем говорят эти возможности? Если элемент массива сдвигов больше, то это означает, что несовпадающий символ оказывается «ближе» к началу, чем повторно появляющиеся завершающие символы строки. Если элемент массива прыжков больше, то повторное появление завершающих символов строки начинается ближе к началу образца, чем несовпадающий символ. В обоих случаях нам следует пользоваться большим из двух сдвигов, поскольку меньший сдвиг неизбежно опять приводит к несовпадению из-за того, что мы знаем о втором значении. Так, например, если значение сдвига равно 2, а значение прыжка 4, то сдвиг на два символа не позволит найти соответствие образцу: несовпадающий символ все равно окажется невыровненным. Однако, если сдвинуть на четыре символа, то под ранее несовпадающим символом окажется подходящий символ образца, и при этом сохраняется возможность того, что завершающие символы образца будут совпадать с новыми соответствующими символами текста.
Поскольку речь идет только о большем из двух значений, алгоритм имеет следующий вид:
Массив сдвигов
Обратимся теперь к массиву сдвигов. В примере ниже мы начинаем сравнение при textLoc = 6 и patternLoc = 6. Поскольку проверяемые символы совпадают, значения обеих переменных textLoc и patternLoc уменьшаются; следующие два символа тоже совпадают, поэтому уменьшение происходит еще один раз, и значения обеих переменных будут равны 4. В следующем символе происходит несовпадение.

Мы хотим сдвинуть образец таким образом, чтобы очередной символ b в тексте совпал с символом b образца, как показано в примере ниже. Затем мы заново начинаем процесс сравнения с правого конца образца. Для этого переменной patternLoc следует вновь присвоить значение длины образца, а переменную textLoc следует увеличить на 4 — действительную величину сдвига образца.

Для реализации этих действий определим увеличение переменной textLoc при несовпадении очередных символов. Воспользуемся массивом slide длины, равной числу символов, которые могут появиться в тексте. Начальные значения всех сдвигов полагаем равными длине образца, поскольку обнаружение в тексте символа, отсутствующего в образце, должно привести к сдвигу указателя в тексте на всю длину образца. Затем происходит замена значения для всех символов образца. Если символ появляется в образце неоднократно, то величина сдвига должна быть такой, чтобы совместить с символом в тексте последнее вхождение символа в образце. Совмещение с предыдущими вхождениями будет осуществляться с помощью прыжков, которые мы обсудим ниже. Вот как вычисляются значения сдвига: Выполнив этот алгоритм на образце datadata, Вы получите slide[d] = 3, slide[a] = 0 и slide[t] = 1; для всех остальных букв алфавита значение сдвига будет равно 8.

Массив прыжков
Массив jump, размер которого совпадает с длиной образца, описывает взаимоотношение частей образца. Этот массив позволяет, например, при несовпадении символа h образца с символом t текста в примере 2 сдвинуть образец целиком за сравниваемый символ. Этот новый массив также отслеживает повторение символов в конце образца, которые могут заменять сравниваемые символы. Пусть, например, образец имеет вид abcdbc, и в процессе сравнения два последних символа образца совпали с символами текста, а в третьем символе обнаружилось расхождение. Тогда массив jump говори, насколько следует сдвинуть образец, чтобы символы bc в позициях 5 и 6 совпали с символами bc в позициях 2 и 2. Таким образом, массив jump содержит информацию о наименьшем возможном сдвиге образца, который совмещает уже совпавшие символы с их следующим появлением в образце.
Предположим, что мы имеем дело с образцом, в котором несовпадение очередного символа означает, что образец следует сдвинуть целиком за место начало сравнения. В примере 4 изображены отрезок текста и образец. Символы X в образце могут быть произвольными; они призваны проиллюстрировать процедуру.