1632
правки
Изменения
м
OUTPUTanswer.pushBack(i) <font color=green>// Найдена подстрока в позиции i</font> '''return'''
rollbackEdits.php mass rollback
'''Алгоритм Бойера-Мура''', разработанный двумя учеными {{---}} Бойером (Robert S. Boyer) и Муром (J. Strother Moore), считается наиболее быстрым среди алгоритмов общего назначения, предназначенных для поиска подстроки в строке. Важной особенностью алгоритма является то, что он выполняет сравнения в шаблоне справа налево в отличии отличие от многих других алгоритмов.
Алгоритм Бойера-Мура считается наиболее эффективным алгоритмом поиска шаблонов в стандартных приложениях и командах, таких как Ctrl+F в браузерах и текстовых редакторах.
==Алгоритм==
Алгоритм сравнивает символы шаблона <tex>yx</tex> справа налево, начиная с самого правого, один за другим с символами исходной строки <tex>xy</tex>. Если символы совпадают, производится сравнение предпоследнего символа шаблона и так до конца. Если все символы шаблона совпали с наложенными символами строки, значит, подстрока найдена, и поиск окончен. В случае несовпадения какого-либо символа (или полного совпадения всего шаблона) он использует две предварительно вычисляемых эвристических функций, чтобы сдвинуть позицию для начала сравнения вправо.
Таким образом для сдвига позиции начала сравнения алгоритм Бойера-Мура выбирает между двумя функциями, называемыми эвристиками хорошего суффикса и плохого символа (иногда они называются эвристиками совпавшего суффикса и стоп-символа). Так как функции эвристические, то выбор между ними простой {{---}} ищется такое итоговое значение, чтобы мы не проверяли максимальное число позиций и при этом нашли все подстроки равные шаблону.
Алфавит обозначим буквой <tex>\Sigma</tex>.
Пусть <tex>|y|=n</tex>, <tex>|x|=m</tex> и <tex>|\Sigma|=\sigma</tex>.
Предположим, что в процессе сравнения возникает несовпадение между символом <tex>x[i]=a</tex> шаблона и символом <tex>y[i+j]=b</tex> исходного текста при проверке в позиции <tex>j</tex>. Тогда <tex>x[i+1 \dots m-1]=y[i+j+1 \dots j+m-1]=u</tex> и <tex>x[i] \neq y[i+j]</tex>, и <tex>m - i - 1</tex> символов шаблона уже совпало.
Если при сравнении текста и шаблона совпало один или больше символов, шаблон сдвигается в зависимости от того, какой суффикс совпал.
Если существуют такие подстроки равные <tex>u</tex>, что они полностью входят в <tex>x</tex> и идут справа от символов, отличных от <tex>x[i]</tex>, то сдвиг происходит к самой правой из них, отличной от <tex> u </tex>. ЯсноПонятно, что в таком случае имеет смысл начинать сравнение таким образом мы не с очередного символа от конца пропустим никакую строку, так как сдвиг просходит на следующую слева подстроку <tex>xu </tex>, а перейти к следующей от суффикса. После выравнивания шаблона по порядку этой подстроке равной суффиксу сравнение шаблона опять начнется с его последнего символа. На новом шаге алгоритма можно строку <tex>xu </tex> из-за того, что другие подстроки явно уже по которой был произведён cдвиг, не подойдут, сравнивать с текстом {{---}} возможность для модификации и продолжить сравнение уже с той позициидальнейшего ускорения алгоритма.
[[Файл:boyer-moore-algorithm-1.png|450px|thumb|center|'''Сдвиг хорошего суффикса''', вся подстрока <tex>u</tex> полностью встречается справа от символа <tex>c</tex>, отличного от символа <tex>a</tex>.]]
Определим два условия:
* <tex>\mathrm{Cs}(i, s)</tex>: для каждого <tex>k</tex> такого, что <tex>i < k < m</tex> выполняется <tex>s \geqslant k</tex> или <tex>x[k-s]=x[k]</tex>* <tex>\mathrm{Co}(i, s)</tex>: если <tex>s < i</tex>, то выполняется <tex>x[i-s] \neq x[i]</tex>
Тогда для всех <tex>i</tex> таких, что <tex>0 \leqslant i < m</tex> выполняется <tex>bmGs[i+1]=\min\{s > 0 : \mathrm{Cs}(i, s)\ and\ wedge\ \mathrm{Co}(i, s)\}</tex>. А значение <tex>bmGs[0]</tex> определим, как длину периода шаблона <tex>x</tex>.
А значение <tex>bmGs[0]</tex> определим, как длину периода шаблона <tex>x</tex>. Для вычисления <tex> bmGs </tex> будем использовать функцию <tex>\mathrm{suffixLength}</tex>, определенную так:для всех <tex>i</tex> таких, что <tex>1 \leqslant i < m</tex> выполняется <tex>\mathrm{suffixLength[}(i])=\max\{k : x[i-k+1 \dots i]=x[m-k \dots m-1]\}</tex>
Сдвиги плохих символов будем хранить в массиве <tex>bmBc</tex> размером <tex>\sigma</tex>.
Для каждого символа <tex>c</tex> из <tex>\Sigma</tex>: <tex>bmBc[c] = \begin{cases}
\min\{i : 1 \leqslant i < m-1\ and\wedge\ x[m-1-i]=c\}, & \mbox{if } c \in x\\
m, & \mbox{otherwise}
\end{cases}</tex>
==Псевдокод==
Константой <tex>|\Sigma|=\sigma=ASIZE</tex> обозначим размер нашего алфавита.
Функция для вычисления таблицы сдвигов плохих символов. Она будет равна длине шаблона для всех символов, которые не встречаются в шаблоне, и порядковому номеру с конца для остальных (кроме последнего, для него тоже берется длина шаблона). Вычисляется прямо по определению за <tex>O(m+\sigma)</tex>. '''int'''[] preBmBc('''char'''[m] x, '''int''' m): '''int''' table<tex>[ASIZE</tex> <tex>|\Sigma|</tex> <tex>]</tex>
<font color=green>// Заполняем значением по умолчанию, равным длине шаблона</font>
'''for''' i = 0 .. ASIZE <tex>|\Sigma|</tex> - 1
table[i] = m
<font color=green>// Вычисление функции по определению</font>
Функция, проверяющая, что подстрока <tex>x[p \dots m - 1]</tex> является префиксом шаблона <tex>x</tex>. Требует <tex>O(m - p)</tex> времени.
'''boolean''' isPrefix('''char'''[m] x, '''int''' m, '''int''' p):
'''int''' j = 0
'''for''' i = p .. m - 1
'''return''' true
Функция, возвращающая для позиции <tex>p</tex> длину максимальной подстроки, которая является суффиксом шаблона <tex>x</tex>. Требует <tex>O(m - p)</tex> времени.//здесь неправильно, нет смысла сравнивать элементы ШАБЛОНА С САМИМ СОБОЙ '''int''' suffixLength('''char'''[m] x, '''int''' m, '''int''' p):
'''int''' len = 0
'''int''' i = p
'''int''' j = m - 1
'''while''' i <tex>\geqslant</tex>= 0 '''and''' x[i] == x[j] ++len += 1
--i
--j
Функция для вычисления сдвигов хороших суффиксов. Требует <tex>O(m)</tex> времени, несмотря на циклы в вызываемых функциях, из-за того, что каждый внутренний цикл в худшем случае будет выполняться на каждой позиции <tex>i</tex> не больше, чем <tex>i</tex> раз. Получается натуральный ряд, сумма <tex>m</tex> первых членов которого <tex dpi="150">\frac{m \cdot (m - 1)}{2}</tex>. Следовательно, получается оценка по времени <tex>O(m^2)</tex>.
'''int'''[] preBmGs('''char'''[m] x, '''int''' m):
'''int''' table[m]
'''int''' lastPrefixPosition = m
'''for''' i = m - 1 .. 0
<font color=green>// Если подстрока x[i+1..m-1] является префиксом, то запомним её начало</font>
'''if''' isPrefix(x, m, i + 1)
lastPrefixPosition = i + 1
table[m - 1 - i] = lastPrefixPosition - i + m - 1
<font color=green>// Вычисление функции по определению</font>
'''for''' i = 0 .. m - 2
'''int''' slen = suffixLength(x, m, i)
table[slen] = m - 1 - i + slen
'''return''' table
Основная функция алгоритма Бойера-Мура
'''voidfunction''' BM('''char'''[n] y, '''char'''[m] x): '''vector <int>''' n = length(y) '''vector <int>''' m answer <font color= length(x)green>// вектор, содержащий все вхождения подстроки в строку</font>
'''if''' m == 0
answer.pushBack(-1) <font color=green>// Искомая подстрока является пустой</font> '''return'''answer
<font color=green>//Предварительные вычисления</font> '''int''' bmBc<tex>[</tex> <tex>|\Sigma|</tex> <tex>] </tex> bmBc = preBmBc(x, m) '''int''' bmGs[m] bmGs = preBmGs(x, m)
<font color=green>//Поиск подстроки</font>
'''for''' i = m - 1 .. n - 1
'''int''' j = m - 1
'''while''' x[j] == y[i]
'''if''' j == 0
--i
--j
i += MAXmax(bmGs[m - 1 - j], bmBc[y[i]]) '''if''' (answer == <tex> \varnothing </tex>) answer.pushBack(-1) <font color=green>// Искомая подстрока не найдена</font> '''return''' answer ==Пример==Пусть нам дана строка <tex>y = GCATCGCAGAGAGTATACAGTACG</tex> и образец <tex>x=GCAGAGAG</tex>. Построим массивы <tex>bmBc</tex> и <tex>bmGs</tex> : [[Файл:RaitaPre.png|250px]] [[Файл:Crochemore.png|300px]] Рассмотрим шаги алгоритма: {| class = "wikitable"! Изображение !! <tex>(j, bmGs[y[j]])</tex> !! Описание|-align="center"|[[Файл:BMexample1.png|550px]]|<tex>(7, 1)</tex>|Сравниванием последние символы, они неравны, поэтому сдвигаемся на <tex> bmGs[y[j]]</tex>, где <tex>y[j]</tex> {{---}} это не совпавший символ. В данном случае <tex>y[j]=7</tex>, а <tex> bmGs[7]= 1</tex>.|-align="center"|[[Файл:BMexample2.png|550px]]|<tex>(8, 4)</tex>|Последние символы совпали. Предпоследние совпали. Третьи символы с конца различны, сдвигаемся на <tex> bmGs[5]= 4</tex>.|-align="center"|[[Файл:BMexample3.png|550px]]|<tex>(12, 7)</tex>|Последние символы совпали, сравниваем далее. Строчка найдена. Продолжаем работу и сдвигаемся на <tex> bmGs[0]= 7</tex>.|-align="center"|[[Файл:BMexample4.png|550px]]|<tex>(19, 4)</tex>|Последние символы совпали. Предпоследние совпали. Третьи символы с конца различны, сдвигаемся на <tex> bmGs[5]= 4</tex>.|-align="center"|[[Файл:BMexample5.png|550px]]|<tex>(23, 7)</tex>|Последние символы совпали, предпоследние различны. Алгоритм закончил работу.|-align="center"|} В итоге, чтобы найти одно вхождение образца длиной <tex>m = 8</tex> в образце длиной <tex>n = 24</tex>, нам понадобилось <tex>17</tex> сравнений символов.
==Асимптотики==
* Фаза предварительных вычислений требует <tex>O(m^2 + \sigma)</tex> времени и памяти.
* В худшем случае поиск требует <tex>O(m \cdot n)</tex> сравнений.
* В лучшем случае требует <tex>O\Omega \left(\dfrac{n / }{m} \right)</tex> сравнений.
'''Пример:'''
Исходный текст <tex>bb \dots bb</tex> и шаблон <tex>abab \dots abab</tex>. Из-за того, что все символы <tex>b</tex> из текста повторяются в шаблоне <tex>\dfrac{m / }{2}</tex> раз, эвристика хорошего суффикса будет пытаться сопоставить шаблон в каждой позиции (суммарно, <tex>n</tex> раз), а эвристика плохого символа в каждой позиции будет двигать строку <tex>\dfrac{m / }{2}</tex> раз. Итого, <tex>O(n \cdot m)</tex>.
где <tex>n</tex> {{---}} длина исходного текста, <tex>m</tex> {{---}} длина шаблона, <tex>\sigma</tex> {{---}} размер алфавита.
===Достоинства===
* Алгоритм Бойера-Мура на хороших данных очень быстр, а вероятность появления плохих данных крайне мала. Поэтому он оптимален в большинстве случаев, когда нет возможности провести предварительную обработку текста, в котором проводится поиск.
* На больших алфавитах (относительно длины шаблона) алгоритм чрезвычайно быстрый и требует намного меньше памяти относительно , чем [[Алгоритм Ахо-Корасик|алгоритма алгоритм Ахо-Корасик]].* Алгоритм проще большинства алгоритмов поиска (при некоторых реализациях объем кода сравним с [[Наивный_алгоритм_поиска_подстроки_в_строке|наивным поиском]])* Позволяет добавить множество модификаций, таких как поиск подстроки, включающей ''любой символ (?)'' (но для реализации ''множества символов (*)'' не походитподходит, так как длина шаблона должна быть известна заранее).
===Недостатки===
* Алгоритмы семейства Бойера-Мура не расширяются до приблизительного поиска, поиска любой строки из нескольких.
* На больших алфавитах (например, Юникод) может занимать много памяти. В таких случаях либо обходятся хэш-таблицами, либо дробят алфавит, рассматривая, например, 4-байтовый символ как пару двухбайтовых.
* На искусственно подобранных неудачных текстах (например, шаблон <tex>abcabcabcabcabc</tex>) скорость алгоритма Бойера-Мура серьёзно снижается.
==СсылкиИсточники информации==
* [[wikipedia:ru:Алгоритм_Бойера_—_Мура|Википедия {{---}} Алгоритм Бойера-Мура]]
* [[wikipedia:ru:Алгоритм_Бойера_—_Мура_—_Хорспула|Википедия {{---}} Алгоритм Бойера-Мура-Хорспула]]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Поиск подстроки в строке]]
[[Категория: Точный поиск]]
