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

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

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

Данный алгоритм был разработан двумя учеными — Робертом Бойером (англ. 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, чтобы сдобрить эту теорию. Любые замечания приветствуются.

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

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

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

Как и при работе КМП-алгоритма, перед началом поиска образу сопоставляется таблица .

Следующим шагом является присвоение каждому элементу таблицы

Далее происходит присваивание элементам массива d соответствующих значений, равных расстоянию от рассматриваемого символа до конца образа. При этом индекс элемента массива d, который получает новое значение, определяется кодом ASCII рассматриваемого символа. Так, код ASCII последнего символа образа Hooligan — п — равен 110. Поскольку данный символ является последним, то удаленность от конца образа равна нулю. Таким образом:

также на языке программирования Си можно записать:

Код ASCII предпоследнего символа образа Hooligan — а — равен 97. Удаленность данного символа от конца образа равна 1 и следовательно:

Аналогичным образом изменяются значения элементов таблицы 4 o’] равно пяти. Поэтому образ смещается вправо на пять символов. Если бы произошло совпадение этих двух символов, то далее рассматривался бы предпоследний символ образа и соответствующий ему символ строки и т. д.

При очередном сравнивании образа и строки происходит несовпадение символов п и g. Опять же, используя в качестве индекса элемента массива d код ASCII символа строки g, получаем значение два: d[‘g’] = 2. Образ сдвигается на два символа вправо. Таким образом, образ постепенно сдвигается по строке до тех пор, пока образ в строке не будет найден или не кончится строка.

Эффективность БМ-алгоритма. Замечательным свойством БМ-поиска является то, что почти всегда, кроме специально построенных примеров, он требует значительно меньше N сравнений. В самых же благоприятных обстоятельствах, когда последний символ образа всегда попадает на несовпадающий символ строки, число сравнений равно N / М.

Задания

• 1. Написать программу поиска образа в строке по методу Кнута, Морриса и Пратта. Предусмотреть возможность существования в образе пробела. Ввести опцию чувствительности / нечувствительности к регистру.
• 2. Написать программу поиска образа в строке по методу Бойера и Мура. Предусмотреть возможность существования в образе пробела. Ввести опцию чувствительности / нечувствительности к регистру.
• 3. Ниже приведен листинг программы, формирующей таблицу d по КМП-алгоритму. При каком образе таблица d будет сформирована неверно? При какой строке и каком образе положительный результат не будет получен?

• 4. Реализовать в программе алгоритм прямого поиска строки и КМП- алгоритм. Сравнить эффективность поиска образа в строке обоими алгоритмами по количеству итераций.
• 5. Реализовать в программе алгоритм прямого поиска строки и БМ-алгоритм. Сравнить эффективность поиска образа в строке обоими алгоритмами по количеству итераций.
• 6. Разработать и программно реализовать усовершенствованный алгоритм, объединяющий БМ-алгоритм с КМП-алгоритмом, который при сдвиге образа использует две таблицы, полученные согласно данным алгоритмам.