1632
правки
Изменения
м
В 1991 году Р.Коул доказал следующую теорему'''Пример:'''Исходный текст <tex>bb \dots bb</tex> и шаблон <tex>abab \dots abab</tex>. Из-за того, что все символы <tex>b</tex> из текста повторяются в шаблоне <tex>\dfrac{m}{Теорема|author=Richard Cole|statement=В худшем случае требуется 2}</tex>Oраз, эвристика хорошего суффикса будет пытаться сопоставить шаблон в каждой позиции (3 \cdot суммарно, <tex>n)</tex> сравнений раз), а эвристика плохого символа в случае шаблона с периодом равным длине самого шаблона.|proof=Доказательство [http:каждой позиции будет двигать строку <tex>\dfrac{m}{2}<//wwwtex> раз.cs.nyu.eduИтого, <tex>O(n \cdot m)</cs/faculty/cole/papers/CHPZ95tex>.ps]}}
==Алгоритм==Алгоритм сравнивает символы шаблона (где <tex>yn</tex>) справа налево{{---}} длина исходного текста, начиная с самого правого<tex>m</tex> {{---}} длина шаблона, один за другим с символами исходной строки (<tex>x\sigma</tex>){{---}} размер алфавита. ==Варианты=====Алгоритм Бойера — Мура — Хорспула===Этот алгоритм работает лучше Бойера-Мура на случайных текстах — для него оценка в среднем лучше.Алгоритм использует только сдвиги плохих символов, при этом за такой символ берётся символ из исходного текста, который соответствует последнему символу шаблона, независимо от того, где случилось несовпадение. В случае несовпадения какогоПоскольку реальные поисковые образцы редко имеют равномерное распределение, алгоритм Бойера-либо Мура-Хорспула может дать как выигрыш, так и проигрыш по сравнению с стандартной реализацией.===Алгоритм Чжу — Такаоки===На коротких алфавитах сдвиги плохих символов не помогают уже на коротких суффиксах. Простейший способ улучшить работу алгоритма в таких условиях — вместо одного плохого символа строить таблицу для пары символов: несовпавшего и идущего перед ним. Такой алгоритм получил собственное имя: алгоритм Чжу — Такаоки.На предварительную обработку расходуется <tex>O(или полного совпадения всего шаблонаm+\sigma^2) он использует две предварительно вычисляемых функций, чтобы сдвинуть позицию для начала сравнения вправо</tex> времени.
Пусть <tex>|y|=n</tex> =Сравнение с другими алгоритмами=====Достоинства===* Алгоритм Бойера-Мура на хороших данных очень быстр, а вероятность появления плохих данных крайне мала. Поэтому он оптимален в большинстве случаев, когда нет возможности провести предварительную обработку текста, в котором проводится поиск.* На больших алфавитах (относительно длины шаблона) алгоритм чрезвычайно быстрый и <tex>требует намного меньше памяти, чем [[Алгоритм Ахо-Корасик|x|=m</tex>алгоритм Ахо-Корасик]].* Позволяет добавить множество модификаций, таких как поиск подстроки, включающей ''любой символ (?)'' (но для реализации ''множества символов (*)'' не подходит, так как длина шаблона должна быть известна заранее).
Предположим, что в процессе сравнения возникает несовпадение между символом <tex>x[i]=a</tex> шаблона и символом <tex>y[i+j]=b</tex> исходного текста при проверке в позиции <tex>j</tex>=Недостатки===* Алгоритмы семейства Бойера-Мура не расширяются до приблизительного поиска, поиска любой строки из нескольких. Тогда <tex>x[i+1 * На больших алфавитах (например, Юникод) может занимать много памяти.В таких случаях либо обходятся хэш-таблицами, либо дробят алфавит, рассматривая, например, 4-байтовый символ как пару двухбайтовых. m* На искусственно подобранных неудачных текстах скорость алгоритма Бойера-1]=y[i+j+1 .Мура серьёзно снижается. j+m-1]=u</tex> и <tex>x[i] \neq y[i+j]</tex>
==Ссылки==* [http[Категория://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%91%D0%BE%D0%B9%D0%B5%D1%80%D0%B0_%E2%80%94_%D0%9C%D1%83%D1%80%D0%B0 Википедия:Алгоритм Бойера-МураДискретная математика и алгоритмы]]* [http[Категория://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%91%D0%BE%D0%B9%D0%B5%D1%80%D0%B0_%E2%80%94_%D0%9C%D1%83%D1%80%D0%B0_%E2%80%94_%D0%A5%D0%BE%D1%80%D1%81%D0%BF%D1%83%D0%BB%D0%B0 Википедия:Алгоритм Бойера-Мура-ХорспулаПоиск подстроки в строке]]* [http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm Wikipedia[Категория:Boyer–Moore string search algorithmТочный поиск]* [http://www-igm.univ-mlv.fr/~lecroq/string/node14.html#SECTION00140]
rollbackEdits.php mass rollback
'''Алгоритм Бойера-Мура''', разработанный двумя учеными – {{---}} Бойером (Robert S. Boyer) и Муром (J. Strother Moore), считается наиболее быстрым среди алгоритмов общего назначения, предназначенных для поиска подстроки в строке. Важной особенностью алгоритма является то, что он выполняет сравнения в шаблоне справа налево в отличии отличие от многих других алгоритмов.
Алгоритм Бойера-Мура считается наиболее эффективным алгоритмом поиска шаблонов в стандартных приложениях и командах, таких как Ctrl+F в браузерах и текстовых редакторах.
==Алгоритм==
Алгоритм сравнивает символы шаблона <tex>x</tex> справа налево, начиная с самого правого, один за другим с символами исходной строки <tex>y</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> u </tex> от суффикса. После выравнивания шаблона по этой подстроке сравнение шаблона опять начнется с его последнего символа. На новом шаге алгоритма можно строку <tex> u </tex>, по которой был произведён cдвиг, не сравнивать с текстом {{---}} возможность для модификации и дальнейшего ускорения алгоритма.
[[Файл:boyer-moore-algorithm-1.png|450px|thumb|center|'''Сдвиг хорошего суффикса''', вся подстрока <tex>u</tex> полностью встречается справа от символа <tex>c</tex>, отличного от символа <tex>a</tex>.]]
Если не существует таких подстрок, то смещение состоит в выравнивании самого длинного суффикса <tex>v</tex> подстроки <tex>y[i+j+1 \dots j+m-1]</tex> с соответствующим префиксом <tex>x</tex>. Из-за того, что мы не смогли найти такую подстроку, то, очевидно, что ни один суффикс шаблона <tex>x</tex> уже не будет лежать в подстроке <tex>y[i+j+1 \dots j+m-1]</tex>, поэтому единственный вариант, что в эту подстроку попадет префикс.
[[Файл:boyer-moore-algorithm-2.png|450px|thumb|center|'''Сдвиг хорошего суффикса''', только суффикс подстроки <tex>u</tex> повторно встречается в <tex>x</tex>.]]
===Правило сдвига плохого символа===
В таблице плохих символов указывается последняя позиция в шаблоне (исключая последнюю букву) каждого из символов алфавита. Для всех символов, не вошедших в шаблон, пишем <tex>m</tex>. Предположим, что у нас не совпал символ <tex>c</tex> из текста на очередном шаге с символом из шаблона. Очевидно, что в таком случае мы можем сдвинуть шаблон до первого вхождения этого символа <tex>c</tex> в шаблоне, потому что совпадений других символов точно не может быть. Если в шаблоне такого символа нет, то можно сдвинуть весь шаблон полностью.
Если символ исходного текста <tex>y[i + j]</tex> встречается в шаблоне <tex>x</tex>, то происходит его выравнивание с его самым правым появлением в подстроке <tex>x[0 \dots m-2]</tex>.
[[Файл:boyer-moore-algorithm-3.png|450px|thumb|center|'''Сдвиг плохого символа''', символ <tex>a</tex> входит в <tex>x</tex>.]]
Если <tex>y[i+j]</tex> не встречается в шаблоне <tex>x</tex>, то ни одно вхождение <tex>x</tex> в <tex>y</tex> не может включать в себя <tex>y[i+j]</tex>, и левый конец окна сравнения совмещен с символом непосредственно идущим после <tex>y[i+j]</tex>, то есть символ <tex>y[i+j+1]</tex>.
[[Файл:boyer-moore-algorithm-4.png|450px|thumb|center|'''Сдвиг плохого символа''', символ <tex>b</tex> не входит в <tex>x</tex>.]]
Обратите внимание, что сдвиг плохого символа может быть отрицательным, поэтому исходя из ранее приведенных свойств этих функций берется значение равное максимуму между сдвигом хорошего суффикса и сдвигом плохого символа.
===Формальное определение===
Теперь определим две функции сдвигов более формально следующим образом:
Пусть значения функции сдвига хорошего суффикса хранятся в массиве <tex>bmGs</tex> размером <tex>m+1</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)\ \wedge\ \mathrm{Co}(i, s)\}</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\ \wedge\ x[m-1-i]=c\}, & \mbox{if } c \in x\\
m, & \mbox{otherwise}
\end{cases}</tex>
Массивы <tex>bmBc</tex> и <tex>bmGs</tex> вычисляются за <tex>O(m^2+\sigma)</tex> времени до основной фазы поиска и требуют, очевидно, <tex>O(m+\sigma)</tex> памяти.
==Псевдокод==
Константой <tex>|\Sigma|=\sigma</tex> обозначим размер нашего алфавита.
Функция для вычисления таблицы сдвигов плохих символов. Она будет равна длине шаблона для всех символов, которые не встречаются в шаблоне, и порядковому номеру с конца для остальных (кроме последнего, для него тоже берется длина шаблона). Вычисляется прямо по определению за <tex>O(m+\sigma)</tex>.
'''int'''[] preBmBc('''char'''[m] x):
'''int''' table<tex>[</tex> <tex>|\Sigma|</tex> <tex>]</tex>
<font color=green>// Заполняем значением по умолчанию, равным длине шаблона</font>
'''for''' i = 0 .. <tex>|\Sigma|</tex> - 1
table[i] = m
<font color=green>// Вычисление функции по определению</font>
'''for''' i = 0 .. m - 2
table[x[i]] = m - 1 - i
'''return''' table
Функция, проверяющая, что подстрока <tex>x[p \dots m - 1]</tex> является префиксом шаблона <tex>x</tex>. Требует <tex>O(m - p)</tex> времени.
'''boolean''' isPrefix('''char'''[m] x, '''int''' p):
'''int''' j = 0
'''for''' i = p .. m - 1
'''if''' x[i] != x[j]
'''return''' false
++j
'''return''' true
Функция, возвращающая для позиции <tex>p</tex> длину максимальной подстроки, которая является суффиксом шаблона <tex>x</tex>. Требует <tex>O(m - p)</tex> времени. //здесь неправильно, нет смысла сравнивать элементы ШАБЛОНА С САМИМ СОБОЙ
'''int''' suffixLength('''char'''[m] x, '''int''' p):
'''int''' len = 0
'''int''' i = p
'''int''' j = m - 1
'''while''' i <tex>\geqslant</tex> 0 '''and''' x[i] == x[j]
++len
--i
--j
'''return''' len
Функция для вычисления сдвигов хороших суффиксов. Требует <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''' table[m]
'''int''' lastPrefixPosition = m
'''for''' i = m - 1 .. 0
<font color=green>// Если подстрока x[i+1..m-1] является префиксом, то запомним её начало</font>
'''if''' isPrefix(x, 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, i)
table[slen] = m - 1 - i + slen
'''return''' table
Основная функция алгоритма Бойера-Мура
'''function''' BM('''char'''[n] y, '''char'''[m] x): '''vector <int>'''
'''vector <int>''' answer <font color=green>// вектор, содержащий все вхождения подстроки в строку</font>
'''if''' m == 0
answer.pushBack(-1) <font color=green>// Искомая подстрока является пустой</font>
'''return''' answer
<font color=green>// Предварительные вычисления</font>
'''int'''<tex>[</tex> <tex>|\Sigma|</tex> <tex>]</tex> bmBc = preBmBc(x)
'''int'''[m] bmGs = preBmGs(x)
<font color=green>// Поиск подстроки</font>
'''for''' i = m - 1 .. n - 1
'''int''' j = m - 1
'''while''' x[j] == y[i]
'''if''' j == 0
answer.pushBack(i) <font color=green>// Найдена подстрока в позиции i</font>
--i
--j
i += max(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> сравнений.
==Псевдо-кодИсточники информации==* [[wikipedia:ru:Алгоритм_Бойера_—_Мура|Википедия {{---}} Алгоритм Бойера-Мура]]* [[wikipedia:ru:Алгоритм_Бойера_—_Мура_—_Хорспула|Википедия {{---}} Алгоритм Бойера-Мура-Хорспула]]* [[wikipedia:Boyer–Moore_string_search_algorithm|Wikipedia {{---}} Boyer–Moore string search algorithm]]* [http://www-igm.univ-mlv.fr/~lecroq/string/node14.html#SECTION00140 Boyer-Moore algorithm]* [http://algolist.manual.ru/search/esearch/bm.php Алгоритм Боуера-Мура]
