Алгоритм бойера мура реферат

Обновлено: 05.07.2024

* Введение
* Строка, её длина, подстрока
* Понятие о сложности алгоритма
* Алгоритм последовательного (прямого) поиска
* Алгоритм Бойера – Мура
* Достоинства алгоритма БМ
* Недостатки алгоритма БМ
* Турбо БМ
* Заключение
* Список литературы

Строка, её длина, подстрока

Определение 1. Строка (слово) - это последовательность знаков (называемых буквами) из некоторого конечного множества, называемого алфавитом.

Определение 2. Длина строки –количество знаков в строке.
Слова обозначаем буквами латинского алфавита, например: X=x[1]x[2]…x[n] – слово длинной n, где x[i] (i-ая буква слова) принадлежит алфавиту. Lentgh(X)==n – обозначение длины строки.

Определение 3. Слово не содержащее ни одной буквы называется пустым.
Пустое слово обычно обозначают буквой L. Length(L)=0.

Определение 4. Слово X называется префиксом слова Y, если есть такое словоZ, что Y=XZ. Причем само слово является префиксом для самого себя (т.к. найдется нулевое слово L, что X=LX.
Пример: слово ab является префиксом слова abcfa.

Определение 5. Слово X называется суффиксом слова Y, если есть такое слово Z, что Y=ZX. Аналогично, слово является суффиксом самого себя.
Пример: слово bfg является суффиксом слова vsenfbfg.

Определение 6. Слово X называется подстрокойстроки Y, если найдутся такие строки Z1 и Z2, что Y=Z1XZ2. При этом Z1 называют левым, а Z2 - правым крылом подстроки. Подстрокой может быть и само слово. Иногда при этом слово X называют вхождением в слово Y. Среди всех вхождений слова X в слово Y, вхождение с наименьшей длиной своего левого крыла называют первым или главным вхождением. Для обозначения вхождения используют обозначение XY.Пример: слова hrf и fhr является подстроками слова abhrfhr, gfsfdgfhro.

Понятие о сложности алгоритма

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

Обзор алгоритмов поиска. Несостоятельность примитивного алгоритма. Алгоритмы: сравнение как "черном ящике", с начала и конца, в необычном порядке. Описание алгоритма Бойера-Мура: сканирование слева направо, сравнение справа налево, эвристика стоп-символа.

Рубрика	Программирование, компьютеры и кибернетика
Вид	курсовая работа
Язык	русский
Дата добавления	23.06.2011
Размер файла	32,0 K

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Содержание

1. Обзор алгоритмов поиска

1.1 несостоятельность примитивного алгоритма

1.4 Основанном на сравнении сначала

1.5 Основанном на сравнении с конца

1.6 Проводящие сравнения в необычном порядке

2. Описание алгоритма Бойера-Мура

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

2.2 Эвристика стоп-символа

2.3 Эвристика совпавшего суффикса

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

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

2.6 Доказательство корректности

2.7 Эвристика совпавшего суффикса

3. Практическая реализация

Список использованных источников

1. Обзор алгоритмов поиска

1.1 Несостоятельность примитивного алгоритма

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

for i=0. |haystack|-|needle|

output("Найдено: ", i+1) 1:

Показано, что примитивный алгоритм отрабатывает в среднем 2h сравнений.

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

3. Архитектура процессора. Некоторые процессоры имеют автоинкрементные или SIMD-операции, которые позволяют быстро сравнить два участка ОЗУ (например, rep cmpsd на х86). На таких процессорах заманчиво применить алгоритм, который просто бы сравнивал needle с haystack -- разумеется, не во всех позициях.

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

5. Возможность проиндексировать haystack. Если таковая есть, поиск серьёзно ускорится.

6. Требуется ли одновременный поиск нескольких строк? Некоторые алгоритмы (например, алгоритм Ахо-Корасик) позволяют это.

Как правило, в текстовом редакторе достаточно взять самый простой эвристический алгоритм наподобие Бойера-Мура-Хорспула -- даже очень медленный ПК справится с поиском за доли секунды. Если же объём текста измеряется гигабайтами, либо поиск запущен на сервере, который обрабатывает множество запросов -- приходится выбирать наиболее удачный алгоритм из доступных.

1.2 Алгоритмы

Для сокращения обозначим:

· |У|=у -- размер алфавита.

· |haystack|=h -- длина строки, в которой ведётся поиск.

· |needle|=n -- длина шаблона поиска.

Вычислительная сложность определяется до первого совпадения. Жирным шрифтом выделены важнейшие с практической точки зрения алгоритмы.

К этой категории относится и примитивный алгоритм поиска.

|S|. Поскольку YS=WT, то T=QS, и SX=QSV при непустых строках Q и V. Получаем третье вхождение строки S в SX, противоречие. Отсюда pi1(i)=|S|, значит, в позицию m?pi1(i)=m?|S| записывается число i?pi1(i)=|SX|?|S|=|X|.

Выясним, может ли на какой-то итерации в эту ячейку записаться меньшее число. При i1 i: pi1(i2)=pi1(i) возможно, но в таком случае в ячейку будет записано |X|+i2?i, что больше |X|.

3. Практическая реализация

В листинге occ -- таблица стоп-символов, skip -- таблица суффиксов. Для ясности листинга применён простейший, требующий O(|needle|І) операций, алгоритм расчёта таблицы суффиксов. Листинг алгоритма приведен в приложении 1.

На х86 существует красивая ассемблерная реализация АБМ, основанная на командах std; rep cmpsb. После неудачного сравнения в регистре ecx остаётся индекс несовпавшего символа; указатели esi и edi указывают на соответствующие символы строк needle и haystack.

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

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

Список использованных источников

1 С. Гудман, С. Хидетниеми, Введение в разработку и анализ алгоритмов, М.:"Мир", 1981.

2 А.В. Ахо, Д.Э. Хопкрофт, Д.Д. Ульман, Структуры данных и алгоритмы, М.,СПб.,Киев: "Вильямс", 2001.

3 Т. Кормен, Ч. Лейзерсон, Р. Ривест. Алгоритмы: построение и анализ. -- М.: МЦНМО, 2000. ISBN 5-900916-37-5. -- с. 801

4 Ахо А.В., Хопкрофт Д., Ульман Дж. Д. Структуры данных и алгоритмы.Вильямс.2000.

5 Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов.Мир.1979.

6 Макконелл Дж. Основы современных алгоритмов.Техносфера.2004

7 Шехтман В.Б. Курс лекций по логике и теории алгоритмов.Москва.2006

8 Игошин В.И. Математическая логика и теории алгоритмов.Академия.2008

9 Вирт Н. Алгоритмы и структуры данных.Мир.1989

Приложение 1

* offset - позиция конца суффикса; suffixlen - его длина

* Выход: 1, если есть совпадение суффикса (и нет совпадения более длинного суффикса)

static int suffix_match(const unsigned char *needle, size_t nlen, size_t offset, size_t suffixlen)

if (offset > suffixlen)

return needle[offset - suffixlen - 1] != needle[nlen - suffixlen - 1] &&

memcmp(needle + nlen - suffixlen, needle + offset - suffixlen, suffixlen) == 0;

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

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

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

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

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

Существуют попытки совместить присущую алгоритму Кнута, Морриса и Пратта эффективность в "плохих" случаях и скорость алгоритма Бойера и Мура в "хороших" – например, турбо- алгоритм , обратный алгоритм Колусси и другие.

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

Ключевые термины

Алгоритм Бойера и Мура – это алгоритм поиска подстроки в строке, при котором первоначально строится таблица смещений для искомой подстроки, проверка начинается с последнего символа подстроки после совмещения начала строки и подстроки.

Алгоритм Кнута, Морриса и Пратта – это алгоритм поиска подстроки в строке, при котором сдвиг подстроки выполняется на некоторое переменное количество символов.

Алгоритм прямого поиска – это алгоритм поиска подстроки в строке, при котором происходит посимвольное сравнение строки с подстрокой.

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

Длина строки – количество символов в строке

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

Префикс – это подстрока , начинающаяся с первого символа строки.

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

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

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

История создания Алгоритм поиска строки Бойера — Мура, считается наиболее быстрым среди алгоритмов общего назначения, предназначенных для поиска подстроки в строке. Был разработан Робертом Бойером (англ.)русск. и Джеем Муром в 1977 году.

Основные идеи алгоритма Сканирование слева направо, сравнение справа налево Поиск стоп - символа Поиск совпавшего суффикса

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

Стоп - символ Если с шаблоном не совпала первая сравниваемая буква, то сдвигаем шаблон вправо до последней такой же буквы Если в шаблоне нет стоп – символа, то сдвигаем шаблон за стоп – символ.

Таблица стоп - символов В таблице указывается последняя позиция элемента в шаблоне (за исключением последней буквы) Если в шаблоне нет такого элемента то в таблицу записывается ноль

Таблица суффиксов Для каждого возможного суффикса в таблицу записывается наименьшая величина, на которую надо сдвинуть шаблон чтобы он снова совпал с суффиксом

Достоинства алгоритма Оптимален при отсутствии возможности провести предварительную обработку текста Достаточно быстрый в большинстве случаев

Недостатки алгоритма На больших алфавитах таблица стоп – символов может занимать много памяти На некоторых “неудачных” текстах его скорость сильно снижается

Читайте также: