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

Обновлено: 06.07.2024

Алгоритм Бойера — Мура поиска строки считается наиболее быстрым среди алгоритмов общего назначения, предназначенных для поиска подстроки в строке. Был разработан Робертом Бойером (англ. Robert S. Boyer ) и Джеем Муром (англ. J Strother Moore ) в 1977 году [1] . Преимущество этого алгоритма в том, что ценой некоторого количества предварительных вычислений над шаблоном (но не над строкой, в которой ведётся поиск) шаблон сравнивается с исходным текстом не во всех позициях — часть проверок пропускаются как заведомо не дающие результата.

Содержание

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Теперь рассмотрим второй цикл — он соответствует полному перекрытию 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 : из условия отсутствия третьего вхождения S не может быть pi1(i1)=pi1(i) . При i2>i: pi1(i2)=pi1(i) возможно, но в таком случае в ячейку будет записано |X|+i2−i , что больше |X| .

Реализация

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

Варианты

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

Этот алгоритм работает лучше Бойера-Мура на случайных текстах — для него оценка в среднем лучше.

АБМХ использует только эвристику стоп-символа, при этом за стоп-символ берётся символ haystack , который соответствует последнему символу needle , независимо от того, где случилось несовпадение.

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

Алгоритм Чжу — Такаоки

На коротких алфавитах (например, при сравнении участков ДНК алфавит состоит всего из 4 символов: A, Т, Г, Ц) эвристика стоп-символа отказывает уже на коротких суффиксах. Простейший способ улучшить работу АБМ в таких условиях — вместо одного стоп-символа строить таблицу для пары символов: несовпавшего и идущего перед ним [3] . Такой алгоритм получил собственное имя: алгоритм Чжу — Такаоки.

На предварительную обработку расходуется O(|needle|+|Σ|²) времени.

Турбо-алгоритм, разработанный группой учёных во главе с М. Крошмором, предлагает другой подход к коротким алфавитам и заодно решает вторую проблему — квадратичную сложность в худшем случае.

Помимо эвристики стоп-символа и эвристики совпавшего суффикса, применяется третья эвристика — эвристика турбосдвига. [4]

Пусть первый раз совпал суффикс UV (и сработала эвристика суффиксов, обеспечив полное перекрытие этого суффикса), второй раз — более короткий V (возможно, V=∅).

По рисунку видно, что минимальный возможный сдвиг — |U|. В противном случае два символа, обозначенные восклицательными знаками, в haystack разные, а в needle одинаковые. В этом и заключается эвристика турбосдвига.

Алгоритм выполняет свою работу за 2·|haystack| сравнений до первого совпадения в худшем случае.

Сравнение с другими алгоритмами

Достоинства

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

Недостатки

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

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

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

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

Содержание

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

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

Алфавит обозначим буквой [math]\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]u[/math] полностью встречается справа от символа [math]c[/math] , отличного от символа [math]a[/math] .

Если не существует таких подстрок, то смещение состоит в выравнивании самого длинного суффикса [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]u[/math] повторно встречается в [math]x[/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[/math] . Следовательно, получается оценка по времени [math]O(m^2)[/math] .

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

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

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

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

Изображение	[math](j, bmGs[y[j]])[/math]	Описание
	[math](7, 1)[/math]	Сравниванием последние символы, они неравны, поэтому сдвигаемся на [math] bmGs[y[j]][/math] , где [math]y[j][/math] — это не совпавший символ. В данном случае [math]y[j]=7[/math] , а [math] bmGs[7]= 1[/math] .
	[math](8, 4)[/math]	Последние символы совпали. Предпоследние совпали. Третьи символы с конца различны, сдвигаемся на [math] bmGs[5]= 4[/math] .
	[math](12, 7)[/math]	Последние символы совпали, сравниваем далее. Строчка найдена. Продолжаем работу и сдвигаемся на [math] bmGs[0]= 7[/math] .
	[math](19, 4)[/math]	Последние символы совпали. Предпоследние совпали. Третьи символы с конца различны, сдвигаемся на [math] bmGs[5]= 4[/math] .
	[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[/math] раз, эвристика хорошего суффикса будет пытаться сопоставить шаблон в каждой позиции (суммарно, [math]n[/math] раз), а эвристика плохого символа в каждой позиции будет двигать строку [math]\dfrac[/math] раз. Итого, [math]O(n \cdot m)[/math] .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пожалуй у каждого заядлого компьютерщика при перелистывании страниц книги в поисках нужного фрагмента, промелькивала мысль "Ох авторы книги. не могли встроить поиск?" :-) Действительно, программы приучили нас к такой удобной возможности, как поиск фрагментов, и если вы разрабатываете подобную программу, пользователь вправе ожидать, что вы предоставите в его распоряжение соответствующие команды, причем он вправе ожидать, что при использовании вашей функции, затратился минимум времени на поиск и этот процесс потратит минимум Ватт электроэнергии. Эту проблему нельзя эффективно решить при помощи стандартных функций С/С++, поскольку большинство средств разработки включает только малоэффективные реализации. Во-первых, в стандартных функциях не всегда используются самые эффективные алгоритмы, а во-вторых, вполне возможно, что вам понадобится изменить стандартное поведение этих функций.

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

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

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

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

Одномерный вариант алгоритма Бойера-Мура состоит из следующих шагов:

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

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

Величина сдвига в случае несовпадения последнего символа вычисляется исходя из следующих соображений:

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

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

Поясним все вышесказанное на простом примере. Пусть у нас есть набор символов из пяти символов: a, b, c, d, e и мы хотим найти вхождение образца "abbad" в строке "abeccacbadbabbad". Следующие схемы иллюстрируют все этапы выполнения алгоритма:

Последний символ образца не совпадает с наложенным символом строки.

Три символа образца совпали, а четвертый – нет.

Последний символ снова не совпадает с символом строки.

Как видно по примеру применение алгоритма Бойера-Мура очень существенно сокращает количество операций сравнения (всего ~18) в отличии от метода грубой силы (~78 операций сравнения) и разрыв только увеличивается при увеличении длины образца. Приведем результаты небольшого теста по сравнению реализации этого алгоритма и стандартных функций поиска подстроки в строке:

Строка содержит образец

Строка не содержит образец

Тест проводился на строке размером 128 Кбайт, и образца - 13 байт, машина Celeron 1000, 512 Mб, компилятор MSVC6 SP5, приведенные цифры - число тиков таймера при выполнении цикла (1000 итераций), усредненные по результатам 5 прогонов.

Двумерный вариант алгоритма Бойера-Мура

Хотя рассмотренный упрощенный алгоритм вполне пригоден с практической точки зрения (и часто применяется), нельзя не заметить, что результаты сравнений используются недостаточно эффективно. Действительно, на втором шаге, когда у нас совпали три символа, мы, зная, что последовательность "bad" встречается в образце только один раз, могли бы сразу сместить образец на всю его длину, а не на один символ. Теперь мы рассмотрим другой, немного более сложный вариант алгоритма Бойера-Мура, позволяющий учесть результаты предыдущих сравнений в случае частичного совпадения образца и подстроки. Прежде всего изменим принцип построения таблицы смещений. В этом варианте алгоритма таблица – двумерная, каждому символу образца соответствует один столбец таблицы, а каждой букве алфавита – одна строка. В ячейках таблицы содержатся значения смещений, на которые нужно сдвинуть образец, если при проверке данного символа образца обнаружено несоответствие. Например, таблица последовательности "abdab" для нашего пятибуквенного алфавита будет выглядеть следующим образом:

a	b	d	a	b
a	0	3	3	0	1
b	3	0	3	5	0
c	3	3	3	5	5
d	3	3	0	5	2
e	3	3	3	5	5

Заполнение таблицы начинается с последнего столбца. Самый правый столбец таблицы фактически соответствует массиву, который используется в одномерном варианте алгоритма. Следующие столбцы содержат значения сдвига для образца при условии, что предыдущие (при движении справа налево) символы совпали, т.е. "грубый" метод построения таблицы выглядит следующим образом:

Фиксируем текущий столбец (начинаем построение с крайнего правого столбца).
Формируем подстроку - берем первым символом подстроки очередной символ строки таблицы (начиная с первой строки) и дополняем его справа символами столбцов справа от текущего.
Конец подстроки совмещаем с концом образца.
Ищем, сдвигая влево подстроку, первое ее вхождение в образец.
Потребовавшееся число сдвигов записываем в пересечение текущего столбца и строки таблицы.

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

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

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

Модифицированные варианты алгоритма

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

Измененная последовательность проверки

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

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

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

Первый шаг остался неизмененным - совмещаем начало строки и образца, и проверяем последний символ образца.
Далее проверяем первый символ образца.
Проверяем середину образца.
И наконец проверяем все символы от середины до краев образца (вначале проверяем правый от центра символ, затем левый, затем правый от правого, левый от левого. ).

Более полное использование таблицы

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

Рассмотрим в нашем примере второй этап поиска, когда совпало 3 символа "bad". При проверке следующего символа обнаружилось несоответствие и мы сдвинули образец на один символ вправо. Хотя постойте, мы при проверке обнаружили, что второй символ образца "b" не соответствует 7-му символу строки, а это символ "c" и он не встречается в образце, тогда разумнее передвинуть образец на два символа, а не на один как раньше.

Теперь подумаем над тем, как из таблицы получить это число, для тех, кто забыл, что находится в таблице повторяю - в ней находятся "расстояние" от конца образца до первого (считая с конца) вхождения конкретного символа из алфавита в образец. Очевидно, что если сразу брать значение из таблицы соответствующее "c", то ничего хорошего не получится, т.к. значения в таблице просчитаны с конца образца, а мы уже давно находимся в другом месте. Логично предположить, что взяв из таблицы значение соответствующее "c" и вычесть номер (нумерация с 0, начиная с конца образца) проверяемого символа мы получим "расстояние" от текущего положения в образце до первого следующего вхождения символа "c", т.е. 5 - 3 = 2 и мы получили искомое число. Не обращайте внимания, на то, что говорится про следующее вхождение символа "c", хотя этот символ не входит в образец.

Хорошо? Неочень! Представим случай, когда номер текущей позиции равен 6, а значение, полученное из таблицы - 2, тогда результат получится отрицательным, что в свою очередь означает, что мы уже прошли позицию первого (с права) вхождения символа и мы уже не знаем "расстояние" до следующего вхождения символа или есть ли он дальше вообще. Так, что все, что мы можем сделать, это только передвинуть образец вправо на один символ.

Использование хэш-функции

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

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

Mix модификаций

Попробуем модифицировать первую модификацию второй модификацией :-). Цель - совместить быстрое определение несоответствия символов из первой модификации с возможностью сдвига на несколько позиций.

Для этого разделим образец на 2 зоны:

Левая будет проверятся первой модификацией.
Соответственно правая - второй.

Основная проблема - выбрать эту границу зон. При выборе размера правой зоны лучше следовать следующим правилам:

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

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

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

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

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

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

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

Поиск разряженного образца

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

Одномерный вариант алгоритма

Для начала попробуем на этапе поиска при встрече подстановочного символа "?" в образце просто пропустить его и идти дальше. А теперь вопрос: будет ли это работать? Ответ: неочень. Очевидно, что нужно еще и изменить таблицу, мы ведь не символ "?" ищем, а любой символ. Причем, т.к. таблица содержит значения до первых вхождений символов, а "?" - любой символ, то длина образца автоматически уменьшается до позиции первого с права вхождения символа "?". Например таблица для образца "?abbad" эквивалентна таблице "abbad".

Заменим в нашем примере "abbad" на "ca?ba" и попробуем что-нибудь найти:

Последний символ образца не совпадает с наложенным символом строки.

Последний символ снова не совпадает с символом строки.

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

Двумерный вариант алгоритма

Таблица (точнее только ее крайний правый столбец) для двумерного варианта строится с теми же соображениями, что и для одномерного. Например для предыдущего образца "ca?ba" таблица смещений будит выглядеть следующим образом:

c	a	?	b	a
a	5	0	0	2	0
b	5	5	0	0	1
c	0	5	0	3	2
d	5	5	0	5	2
e	5	5	0	5	2

Отличительная черта таблицы в том, что в столбце подстановочного символа все значения - нули, что впрочем очевидно ("?" - любой символ).

Алгоритм

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

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

Иллюстрация

somestring
string

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

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

Заключение

Говорят, что такая модификация алгоритма Бойера-Мура справляется со случайными текстами лучше, чем сам исходный алгоритм. Однако, оценка сложности в худшем случае у него всё-таки похуже. Но в отличии от исходного алгоритма, здесь не требуется никаких сложных вычислений — строится только таблица смещений, что не так сложно для реализации.

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