Меню

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

Таблица сдвигов бойера мура

Алгоритм Бойера-Мура, разработан двумя учеными – Бойером и Муром в 1977 году, считается наиболее быстрым среди алгоритмов поиска подстроки в строке. Особенностью алгоритма является пред обработка искомой строки, благодаря которой сравнение производится не во всех позициях, т.к. значительная часть сравнений отбрасываются — как заведомо не дающие положительного результата.
Оригинальный вариант алгоритма Бойера-Мура состоит из двух этапов. На первом этапе строится таблица смещений для искомой строки. Далее совмещается начало строки и образца и начинается проверка с последнего символа образца. Если последний символ образца и соответствующий ему символ строки не совпадают, то образец сдвигается относительно строки вправо на величину, полученную из таблицы смещений, и снова проводится сравнение, начиная с последнего символа образца. В противном случае, при совпадении символов, проводится сравнение предпоследнего символа образца и т. д. Если все символы образца совпали с соответствующими символами строки, то нужная подстрока найдена. Если же какой-то (не последний) символ образца не совпадает с соответствующим символом строки, то образец сдвигается на один символ вправо и снова начинается проверка с последнего символа.
Таблица смещений строится по следующим принципам:

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

Величина смещения для каждого символа искомой строки зависит только от порядка символов в ней самой, поэтому таблицу смещений вычисляют заранее и чаще всего хранят в виде одномерного массива, где каждому символу из искомой строки соответствует смещение относительно последнего символа.
Пример работы алгоритма:
Пусть существует алфавит из пяти символов: q, w, e, r, t и необходимо найти вхождение образца “qwwqr” в строке “qwteeqewqrwqwwqr”. Следующие схемы иллюстрируют все этапы выполнения алгоритма. Таблица смещений будет выглядеть так:

q w e r t
1 2 5 5
q w t e e q e w q r w q w w q r
q w w q r

Так как последний символ искомой строки не совпадает с соответствующим символом исходной строки, то образец смещается вправо на величину из таблицы смещений, соответствующую символу «e» т.е. на 5 позиций.

q w t e e q e w q r w q w w q r
q w w q r

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

q w t e e q e w q r w q w w q r
q w w q r

Снова не совпадает последний символ искомой строки, выполняется сдвиг на 2 позиции вправо.

q w t e e q e w q r w q w w q r
q w w q r

Ещё раз выполняется сдвиг вправо на 2 позиции.

q w t e e q e w q r w q w w q r
q w w q r

В соответствии со значением смещения для символа q выполняется сдвиг на 1 позицию.

q w t e e q e w q r w q w w q r
q w w q r

Алгоритм считается самым быстрым алгоритмом поиска, хотя его время работы в худшем случае будет квадратным O(n*m), но вероятность этого худшего варианта крайне мала. А в среднем же алгоритм показывает линейную зависимость от исходной строки.

Источник

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

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

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

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

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

Ключевые понятия:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

8. while and

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Читайте также:  Решение фрагмента таблицы истинности

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

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

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

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

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

1. for each character

3. for to

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4. for j=0..m

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

6. for i=1..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

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

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

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

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

a b c d e

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

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

Суффикс [пустой] 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

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

Источник



Объясните как строится таблица смещений в алгоритме Бойера-Мура?

Вот тут вот прочитал http://www.rsdn.ru/article/alg/textsearch.xml , но в таблице написаны одни данные, а смещение идёт совсем по другим. Совсем запутался. Помогите пожалуйста.

Добавлено через 34 минуты
Тему можно закрыть, я разобрался =)

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

Есть ли ошибки в алгоритме Бойера-Мура
Есть ли ошибки в этом варианте алгоритма и можно ли его улучшить? Procedure Seacrh; Var i, j.

Алгоритм Бойера — Мура
Доброго времени суток, нет ли у кого-нибудь примера реализации алгоритма Бойера — Мура. Искал в.

алгоритм Бойера-Мура
Всем привет! Помогите исправить ошибку пожалуйста! unit Unit1; interface uses .

Алгоритм Бойера-Мура
Скиньте пожалуйста алгоритм Бойера-Мура

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

Алгоритм Бойера и Мура
Добрый день! Помогите пожалуйста написать на С++ алгоритм Бойера и Мура Добавлено через 7.

метод бойера-мура
Помогите найти ошибку. (в дельфи новичок).вот код.выдает ошибку(даже не ошибку,а выделяет.

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

Алгоритм Бойера — Мура
Люди добрые помогите с задачей! Необходимо Алгоритмом Бойера — Мура найди вхождения строки в.

Источник

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

Алгоритм Бойера-Мура, разработанный двумя учеными — Бойером (Robert S. Boyer) и Муром (J. Strother Moore), считается наиболее быстрым среди алгоритмов общего назначения, предназначенных для поиска подстроки в строке. Важной особенностью алгоритма является то, что он выполняет сравнения в шаблоне справа налево в отличие от многих других алгоритмов.

Алгоритм Бойера-Мура считается наиболее эффективным алгоритмом поиска шаблонов в стандартных приложениях и командах, таких как Ctrl+F в браузерах и текстовых редакторах.

Содержание

  • 1 Алгоритм
    • 1.1 Правило сдвига хорошего суффикса
    • 1.2 Правило сдвига плохого символа
    • 1.3 Формальное определение
  • 2 Псевдокод
  • 3 Пример
  • 4 Асимптотики
  • 5 Варианты
    • 5.1 Алгоритм Бойера — Мура — Хорспула
    • 5.2 Алгоритм Чжу — Такаоки
  • 6 Сравнение с другими алгоритмами
    • 6.1 Достоинства
    • 6.2 Недостатки
  • 7 Источники информации

Алгоритм [ править ]

Алгоритм сравнивает символы шаблона [math]x[/math] справа налево, начиная с самого правого, один за другим с символами исходной строки [math]y[/math] . Если символы совпадают, производится сравнение предпоследнего символа шаблона и так до конца. Если все символы шаблона совпали с наложенными символами строки, значит, подстрока найдена, и поиск окончен. В случае несовпадения какого-либо символа (или полного совпадения всего шаблона) он использует две предварительно вычисляемых эвристических функций, чтобы сдвинуть позицию для начала сравнения вправо.

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

Алфавит обозначим буквой [math]\Sigma[/math] .

Пусть [math]|y|=n[/math] , [math]|x|=m[/math] и [math]|\Sigma|=\sigma[/math] .

Предположим, что в процессе сравнения возникает несовпадение между символом [math]x[i]=a[/math] шаблона и символом [math]y[i+j]=b[/math] исходного текста при проверке в позиции [math]j[/math] . Тогда [math]x[i+1 \dots m-1]=y[i+j+1 \dots j+m-1]=u[/math] и [math]x[i] \neq y[i+j][/math] , и [math]m — i — 1[/math] символов шаблона уже совпало.

Правило сдвига хорошего суффикса [ править ]

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

Если существуют такие подстроки равные [math]u[/math] , что они полностью входят в [math]x[/math] и идут справа от символов, отличных от [math]x[i][/math] , то сдвиг происходит к самой правой из них, отличной от [math] u [/math] . Понятно, что таким образом мы не пропустим никакую строку, так как сдвиг просходит на следующую слева подстроку [math] u [/math] от суффикса. После выравнивания шаблона по этой подстроке сравнение шаблона опять начнется с его последнего символа. На новом шаге алгоритма можно строку [math] u [/math] , по которой был произведён cдвиг, не сравнивать с текстом — возможность для модификации и дальнейшего ускорения алгоритма.

Читайте также:  СанПиН Нормы шума на производстве

Если не существует таких подстрок, то смещение состоит в выравнивании самого длинного суффикса [math]v[/math] подстроки [math]y[i+j+1 \dots j+m-1][/math] с соответствующим префиксом [math]x[/math] . Из-за того, что мы не смогли найти такую подстроку, то, очевидно, что ни один суффикс шаблона [math]x[/math] уже не будет лежать в подстроке [math]y[i+j+1 \dots j+m-1][/math] , поэтому единственный вариант, что в эту подстроку попадет префикс.

Правило сдвига плохого символа [ править ]

В таблице плохих символов указывается последняя позиция в шаблоне (исключая последнюю букву) каждого из символов алфавита. Для всех символов, не вошедших в шаблон, пишем [math]m[/math] . Предположим, что у нас не совпал символ [math]c[/math] из текста на очередном шаге с символом из шаблона. Очевидно, что в таком случае мы можем сдвинуть шаблон до первого вхождения этого символа [math]c[/math] в шаблоне, потому что совпадений других символов точно не может быть. Если в шаблоне такого символа нет, то можно сдвинуть весь шаблон полностью.

Если символ исходного текста [math]y[i + j][/math] встречается в шаблоне [math]x[/math] , то происходит его выравнивание с его самым правым появлением в подстроке [math]x[0 \dots m-2][/math] .

Если [math]y[i+j][/math] не встречается в шаблоне [math]x[/math] , то ни одно вхождение [math]x[/math] в [math]y[/math] не может включать в себя [math]y[i+j][/math] , и левый конец окна сравнения совмещен с символом непосредственно идущим после [math]y[i+j][/math] , то есть символ [math]y[i+j+1][/math] .

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

Формальное определение [ править ]

Теперь определим две функции сдвигов более формально следующим образом:

Пусть значения функции сдвига хорошего суффикса хранятся в массиве [math]bmGs[/math] размером [math]m+1[/math] .

Определим два условия:

  • [math]\mathrm(i, s)[/math] : для каждого [math]k[/math] такого, что [math]i \lt k \lt m[/math] выполняется [math]s \geqslant k[/math] или [math]x[k-s]=x[k][/math]
  • [math]\mathrm(i, s)[/math] : если [math]s \lt i[/math] , то выполняется [math]x[i-s] \neq x[i][/math]

Тогда для всех [math]i[/math] таких, что [math]0 \leqslant i \lt m[/math] выполняется [math]bmGs[i+1]=\min\(i, s)\ \wedge\ \mathrm(i, s)\>[/math] .

А значение [math]bmGs[0][/math] определим, как длину периода шаблона [math]x[/math] .

Для вычисления [math] bmGs [/math] будем использовать функцию [math]\mathrm[/math] , определенную так: для всех [math]i[/math] таких, что [math]1 \leqslant i \lt m[/math] выполняется [math]\mathrm(i)=\max\[/math]

Сдвиги плохих символов будем хранить в массиве [math]bmBc[/math] размером [math]\sigma[/math] . Для каждого символа [math]c[/math] из [math]\Sigma[/math] : [math]bmBc[c] = \begin \min\, & \mbox c \in x\\ m, & \mbox \end[/math]

Массивы [math]bmBc[/math] и [math]bmGs[/math] вычисляются за [math]O(m^2+\sigma)[/math] времени до основной фазы поиска и требуют, очевидно, [math]O(m+\sigma)[/math] памяти.

Псевдокод [ править ]

Константой [math]|\Sigma|=\sigma[/math] обозначим размер нашего алфавита.

Функция для вычисления таблицы сдвигов плохих символов. Она будет равна длине шаблона для всех символов, которые не встречаются в шаблоне, и порядковому номеру с конца для остальных (кроме последнего, для него тоже берется длина шаблона). Вычисляется прямо по определению за [math]O(m+\sigma)[/math] .

Функция, проверяющая, что подстрока [math]x[p \dots m — 1][/math] является префиксом шаблона [math]x[/math] . Требует [math]O(m — p)[/math] времени.

Функция, возвращающая для позиции [math]p[/math] длину максимальной подстроки, которая является суффиксом шаблона [math]x[/math] . Требует [math]O(m — p)[/math] времени. //здесь неправильно, нет смысла сравнивать элементы ШАБЛОНА С САМИМ СОБОЙ

Функция для вычисления сдвигов хороших суффиксов. Требует [math]O(m)[/math] времени, несмотря на циклы в вызываемых функциях, из-за того, что каждый внутренний цикл в худшем случае будет выполняться на каждой позиции [math]i[/math] не больше, чем [math]i[/math] раз. Получается натуральный ряд, сумма [math]m[/math] первых членов которого [math]\frac<2>[/math] . Следовательно, получается оценка по времени [math]O(m^2)[/math] .

Основная функция алгоритма Бойера-Мура

Пример [ править ]

Пусть нам дана строка [math]y = GCATCGCAGAGAGTATACAGTACG[/math] и образец [math]x=GCAGAGAG[/math] .

Построим массивы [math]bmBc[/math] и [math]bmGs[/math] :

RaitaPre.png

Crochemore.png

Рассмотрим шаги алгоритма:

Изображение [math](j, bmGs[y[j]])[/math] Описание
BMexample1.png [math](7, 1)[/math] Сравниванием последние символы, они неравны, поэтому сдвигаемся на [math] bmGs[y[j]][/math] , где [math]y[j][/math] — это не совпавший символ. В данном случае [math]y[j]=7[/math] , а [math] bmGs[7]= 1[/math] .
BMexample2.png [math](8, 4)[/math] Последние символы совпали. Предпоследние совпали. Третьи символы с конца различны, сдвигаемся на [math] bmGs[5]= 4[/math] .
BMexample3.png [math](12, 7)[/math] Последние символы совпали, сравниваем далее. Строчка найдена. Продолжаем работу и сдвигаемся на [math] bmGs[0]= 7[/math] .
BMexample4.png [math](19, 4)[/math] Последние символы совпали. Предпоследние совпали. Третьи символы с конца различны, сдвигаемся на [math] bmGs[5]= 4[/math] .
BMexample5.png [math](23, 7)[/math] Последние символы совпали, предпоследние различны. Алгоритм закончил работу.

В итоге, чтобы найти одно вхождение образца длиной [math]m = 8[/math] в образце длиной [math]n = 24[/math] , нам понадобилось [math]17[/math] сравнений символов.

Асимптотики [ править ]

  • Фаза предварительных вычислений требует [math]O(m^2 + \sigma)[/math] времени и памяти.
  • В худшем случае поиск требует [math]O(m \cdot n)[/math] сравнений.
  • В лучшем случае требует [math] \Omega \left( \dfrac\right)[/math] сравнений.

Пример: Исходный текст [math]bb \dots bb[/math] и шаблон [math]abab \dots abab[/math] . Из-за того, что все символы [math]b[/math] из текста повторяются в шаблоне [math]\dfrac<2>[/math] раз, эвристика хорошего суффикса будет пытаться сопоставить шаблон в каждой позиции (суммарно, [math]n[/math] раз), а эвристика плохого символа в каждой позиции будет двигать строку [math]\dfrac<2>[/math] раз. Итого, [math]O(n \cdot m)[/math] .

где [math]n[/math] — длина исходного текста, [math]m[/math] — длина шаблона, [math]\sigma[/math] — размер алфавита.

Варианты [ править ]

Алгоритм Бойера — Мура — Хорспула [ править ]

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

Алгоритм Чжу — Такаоки [ править ]

На коротких алфавитах сдвиги плохих символов не помогают уже на коротких суффиксах. Простейший способ улучшить работу алгоритма в таких условиях — вместо одного плохого символа строить таблицу для пары символов: несовпавшего и идущего перед ним. Такой алгоритм получил собственное имя: алгоритм Чжу — Такаоки. На предварительную обработку расходуется [math]O(m+\sigma^2)[/math] времени.

Источник