Исследование работы алгоритма Бойера-Мура

Размещено на http://www.allbest.ru/

Содержание

Введение

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

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

1.2 Алгоритмы

1.3 Основанном на сравнении как «черном ящике»

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 Несостоятельность примитивного алгоритма

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

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

for j=1...|needle|

if haystack[i+j]<>needle[j]

then goto 1

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

Простейший алгоритм поиска даже в лучшем случае проводит |haystack|?|needle|+1 сравнение; если же есть много частичных совпадений, скорость снижается до O(|haystack|·|needle|).

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

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

1. «Враждебность» пользователя. Другими словами: будет ли пользователь намеренно задавать данные, на которых алгоритм будет медленно работать? Существуют очень простые алгоритмы, оценка которых O(|haystack|·|needle|) в худшем случае, но на «обычных» данных количество сравнений намного меньше |haystack|. Только в 1990-е годы были созданы алгоритмы, дающие сложность O(|haystack|) в худшем случае и меньше |haystack| в среднем.

2. Грамматика языка может быть недружественной к тем или иным эвристикам, которые ускоряют поиск «в среднем».

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

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

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

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

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

1.2 Алгоритмы

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

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

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

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

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

1.3 Основанные на сравнении как «чёрном ящике»

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

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

Таблица 1.1 - алгоритмы основанные на сравнении как «чёрном ящике»

Название	Предв. обработка	Сложность	Примечания
		типичная	макс.
Примитивный алгоритм	Нет	2h	O(hn)
Алгоритм Бойера-Мура-Хорспула	O(n+у)	<h	O(hn)	Упрощённый до предела алгоритм Бойера-Мура; использует только видоизменённую эвристику стоп-символа -- за стоп-символ всегда берётся символ haystack, расположенный напротив последнего символа needle.
Алгоритм быстрого поиска =Алгоритм Санди	O(n+у)	<h	O(hn)	Также использует исключительно эвристику стоп-символа -- но за стоп-символ берётся символ haystack, идущий за последним символом needle.

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

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

Таблица 1.2 - алгоритмы основанные на сравнении с начала

Название	Предв. обработка	Сложность	Примечания
		типичная	макс.
Алгоритм Рбина-Карпа	O(n)	<h+n	O(hn)	Хэширование позволяет серьёзно снизить сложность в среднем
Алгоритм Кнута-Морриса-Пратта	O(n)		?2h+1	Один из первых алгоритмов с линейной оценкой в худшем случае
Автоматный алгоритм	O(nу)	=h	=h	Строит конечный автомат, который распознаёт язык, состоящий из одной единственной строки.
Алгоритм Апостолика-Крошмора	O(n)		?1,5h
Алгоритм Shift-Or = Bitap-алгоритм=Двоичный алгоритм	O(n+у)		O(h)	Эффективен, если размер needle (в символах) не больше размера машинного слова (в
Название	Предв. обработка	Сложность	Примечания
		типичная	макс.
Алгоритм Shift-Or = Bitap-алгоритм=Двоичный алгоритм				битах). Легко переделывается на приблизительный поиск.

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

В этом семействе алгоритмов needle движется по haystack слева направо, но сравнение этих строк друг с другом проводится справа налево. Сравнение справа налево позволяет в случае несовпадения сдвинуть needle не на одну позицию, а на несколько.

Таблица 1.1 - алгоритмы основанные на сравнении с конца

Название	Предв. обработка	Сложность	Примечания
		типичная	макс.
Алгоритм Бойера-Мура	O(n+у)	<h	O(hn)	Стандартный алгоритм поиска подстроки в строке
Алгоритм Чжу-Такаоке	O(n+уІ)	<h	O(hn)	Алгоритм Бойера-Мура, оптимизированный под короткие алфавиты
Алгоритм Апостолика-Джонкарло	O(n+у)	<h	?1,5h	Одна из первых попыток получить <h в типичном случае и O(h) в худшем. Очень сложен в реализации.
Турбо алгоритм БМ	O(n+у)	<h	?2h	Не даёт регрессии на «плохих» данных

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

Таблица 1.1 - алгоритмы проводящие сравнение в необычном порядке

Название	Предв. обработка	Сложность	Примечания
		типичная	макс.
Нипримитивный алгоритм	const	<h	O(hn)	Простой алгоритм, сравнивающий второй символ, затем начиная с третьего в режиме «чёрного ящика», и, наконец, первый. При n[1]?n[2] и несовпадении на второй-третьей стадии -- сдвиг на 2 вправо.
Алгоритм Райты =Алгоритм Бойера-Мура-Хорспула-Райты	O(n+у)	<h	O(hn)	Эмпирический алгоримт, оптимизированный под английские тексты. Сравнивает последний символ, потом первый, потом средний, потом все остальные; при несовпадении -- сдвиг по Хорспулу.

алгоритм поиск сравнение сканирование

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

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

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

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

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

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

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

Предположим, что мы производим поиск слова «колокол». Первая же буква не совпала -- «к» (назовём эту букву стоп-символом). Тогда можно сдвинуть шаблон вправо до последней буквы «к».

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

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

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

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

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

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

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

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

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

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

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

В таких ситуациях выручает третья идея АБМ -- эвристика совпавшего суффикса.

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

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

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

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

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

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

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

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

В таблице стоп-символов указывается последняя позиция в needle (исключая последнюю букву) каждого из символов алфавита. Считается, что символы строк нумеруются с 1 (как в Паскале). Для всех символов, не вошедших в needle, пишем 0 (для нумерации с 0 -- соответственно, ?1). Например, если needle=«abcdadcd», таблица стоп-символов будет выглядеть так.

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

Символ	a	b	c	d	[все остальные]
Последняя позиция	5	2	7	6	0

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

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

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

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

Суффикс	[пустой]	d	cd	dcd	…	abcdadcd
Сдвиг	1	2	4	8	…	8

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

было	?	?d	?cd	?dcd	…	abcdadcd
стало	abcdadcd	abcdadcd	abcdadcd	abcdadcd	…	abcdadcd

Если шаблон начинается и заканчивается одной и той же комбинацией букв, |needle| вообще не появится в таблице. Например, для needle=«колокол» для всех суффиксов (кроме, естественно, пустого) сдвиг будет равен 4.

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

Суффикс	[пустой]	л	ол	…	олокол	колокол
Сдвиг	1	4	4	…	4	4

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

было	?	?л	?ол	...	?олокол	колокол
стало	колокол	колокол	колокол	...	колокол	колокол

Существует быстрый алгоритм вычисления таблицы суффиксов. Этот алгоритм использует префикс-функцию строки.

m = length(needle)

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

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

for j=0..m

suffshift[j] = m - pi[m]

for i=1..m

j = m - pi1[i]

suffshift[j] = min(suffshift[j], i - pi1[i])

Здесь suffshift[0] соответствует всей совпавшей строке; suffshift[m] -- пустому суффиксу. Поскольку префикс-функция вычисляется за O(|needle|) операций, вычислительная сложность этого шага также равняется O(|needle|).

Пример работы алгоритма

Искомый шаблон -- «abbad». Таблица стоп-символов будет выглядеть как

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

Символ	a	b	[остальные]
Позиция	4	3	0

Таблица суффиксов для всех возможных суффиксов (кроме пустого) даёт максимальный сдвиг -- 5.

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

abeccaabadbabbad
abbad

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

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

abeccaabadbabbad
abbad

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

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

abeccaabadbabbad
abbad

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

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

abeccaabadbabbad
abbad

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

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

Итак, пусть совпал суффикс S, needle=PbS, стоп-символ -- a (в дальнейшем малые буквы -- символы, большие -- строки).

Строка: * * * * * * * a [-- S --] * * * *

Шаблон: [--- P ---] b [-- S --]

Эвристика стоп-символа. Работает, когда в строке S символ а отсутствует. Если P=WaV и в строке V нет символа а, то эвристика стоп-символа предлагает сдвиг на |V|+1 позицию.

Строка: * * * * * * * * * * * * a [-- S --] * * * * * * * *

Шаблон: [- W -] a [--- V ---] b [-- S --]

Пропустить: [- W -] a [--- V ---] b [-- S --]

Новый шаг: [- W -] a [--- V ---] b [-- S --]

Действительно, если в строке V нет буквы a, нечего пробовать пропущенные |V| позиций.

Если же в needle вообще нет символа а, то эвристика стоп-символа предлагает сдвиг на |P|+1 позицию -- и также нет смысла пробовать пропущенные |P|.

Строка: * * * * * * * * a [-- S --] * * * * * * * *

Шаблон: [--- P ---] b [-- S --]

Пропустить: [--- P ---] b [-- S --]

Новый шаг: [--- P ---] b [-- S --]

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

Сама неформальная фраза -- «минимальный сдвиг needle, при котором needle совпадёт с S во всех возможных позициях» -- говорит, что меньшие сдвиги бесполезны. Поэтому взамен покажем корректность ускоренного алгоритма вычисления таблицы суффиксов -- то есть, продемонстрируем, что он вычисляет именно этот «минимальный сдвиг».

Сначала рассмотрим первый цикл. pi(m) -- это длина максимального суффикса needle, который является префиксом. Поэтому m?pi(m) -- максимальный сдвиг, который обусловливается тем, что S и needle могут перекрываться и частично; дальше сдвигать недопустимо.

Например: даже если весь шаблон «колокол» совпал, дальше 4 символов сдвиг невозможен -- например, в строке «колоколокол» шаблон «колокол» встречается дважды, на 1-й и на 5-й позиции.

haystack: колоколокол

Проба 1: колокол

Проба 2: колокол

Теперь рассмотрим второй цикл -- он соответствует полному перекрытию S и needle. Покажем такой факт: если needle=P?SX=P?YS и других вхождений S в SX=YS нет, то в позиции, которая соответствует суффиксу S (то есть, m?|S|), будет записано ровно |X|=|Y| (при условии, что предыдущая оценка, связанная с частичным перекрытием, больше).

Рассмотрим итерацию i=|SX|=|YS|. Очевидно, что pi1(i) -- это длина максимального префикса-суффикса строки SX=YS. Покажем, что эта величина равна именно |S|. Действительно, если эта величина больше |S|, то строку SX=YS можно разложить как TV=WT, причём |T|>|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: из условия отсутствия третьего вхождения S не может быть pi1(i1)=pi1(i). При i2>i: pi1(i2)=pi1(i) возможно, но в таком случае в ячейку будет записано |X|+i2?i, что больше |X|.

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

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

Заключение

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

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

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

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

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

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

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

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

#include <string.h>

#include <limits.h>

/* Вход: needle+nlen - что искать

* 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;

else

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

}

static size_t max(size_t a, size_t b)

{

return a > b ? a : b;

}

/* Вход: haystack - где искать, needle - что искать.

* hlen - длина haystack, nlen - длина needle

* Выход: указатель на первое вхождение needle в haystack, либо NULL

*/

const unsigned char* memmem_boyermoore

(const unsigned char* haystack, size_t hlen,

const unsigned char* needle, size_t nlen)

{

size_t skip[nlen]; /* Таблица суффиксов */

ssize_t occ[UCHAR_MAX + 1]; /* Таблица стоп-символов */

if(nlen > hlen || nlen <= 0 || !haystack || !needle)

return NULL;

/* ПОСТРОЕНИЕ ТАБЛИЦЫ СТОП-СИМВОЛОВ */

/* Заполняем -1 (в Си нумерация символов с 0!!) */

for(size_t a=0; a<UCHAR_MAX+1; ++a)

occ[a] = -1;

/* В таблицу occ записывается последнее вхождение в needle */

/* (исключая последний символ) */

for(size_t a = 0; a < nlen - 1; ++a)

occ[needle[a]] = a;

/* ПОСТРОЕНИЕ ТАБЛИЦЫ СУФФИКСОВ */

/* Упрощённый вариант. Можно реализовать быстрее. */

for(size_t a = 0; a < nlen; ++a)

{

size_t offs = nlen;

while(offs && !suffix_match(needle, nlen, offs, a))

--offs;

skip[nlen - a - 1] = nlen - offs;

}

/* ПОИСК */

for(size_t hpos = 0; hpos <= hlen - nlen; )

{

size_t npos = nlen - 1;

/* Сверка needle и haystack с конца */

while(needle[npos] == haystack[npos + hpos])

{

if(npos == 0)

return haystack + hpos;

--npos;

}

/* Не совпало! */

hpos += max(skip[npos], npos - occ[haystack[npos + hpos]]);

/* ^^^ ^^^^ */

/* суффикс стоп-символ */

}

return NULL;

}

Размещено на Allbest.ru