Изменения

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

==АсимптотикиАлгоритм==* Фаза предварительных вычислений требует Алгоритм сравнивает символы шаблона <tex>Ox</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>O(x[i+1 \dots m -1]=y[i+j+1 \cdot n)dots j+m-1]=u</tex> сравнений.* В лучшем случае требует и <tex>O(n x[i] \neq y[i+j]</ tex>, и <tex>m)- i - 1</tex> сравненийсимволов шаблона уже совпало.

В 1991 году Р.Коул доказал следующую теорему:{{Теорема|author=Richard Cole==Правило сдвига хорошего суффикса===|statement=В худшем случае требуется <tex>O(3 \cdot n)</tex> сравнений Если при сравнении текста и шаблона совпало один или больше символов, шаблон сдвигается в случае шаблона с периодом равным длине самого шаблоназависимости от того, какой суффикс совпал.|proof=Доказательство [http://www.cs.nyu.edu/cs/faculty/cole/papers/CHPZ95.ps]}}

==Алгоритм==Алгоритм сравнивает символы ''шаблона'' (Если существуют такие подстроки равные <tex>u</tex>, что они полностью входят в <tex>yx</tex>) и идут справа налевоот символов, отличных от <tex>x[i]</tex>, то сдвиг происходит к самой правой из них, отличной от <tex> u </tex>. Понятно, начиная с самого правогочто таким образом мы не пропустим никакую строку, один за другим с символами ''исходной строки'' (так как сдвиг просходит на следующую слева подстроку <tex>xu </tex>)от суффикса. В случае несовпадения какого-либо После выравнивания шаблона по этой подстроке сравнение шаблона опять начнется с его последнего символа (или полного совпадения всего шаблона) он использует две предварительно вычисляемых функций. На новом шаге алгоритма можно строку <tex> u </tex>, по которой был произведён cдвиг, чтобы сдвинуть позицию не сравнивать с текстом {{---}} возможность для начала сравнения вправомодификации и дальнейшего ускорения алгоритма.

Пусть [[Файл:boyer-moore-algorithm-1.png|450px|thumb|center|'''Сдвиг хорошего суффикса''', вся подстрока <tex>u</tex> полностью встречается справа от символа <tex>|y|=nc</tex> и , отличного от символа <tex>|x|=ma</tex>.]]

ПредположимЕсли не существует таких подстрок, что то смещение состоит в процессе сравнения возникает несовпадение между символом выравнивании самого длинного суффикса <tex>x[i]=av</tex> шаблона и символом подстроки <tex>y[i+j+1 \dots j+m-1]=b</tex> исходного текста при проверке в позиции с соответствующим префиксом <tex>jx</tex>. Тогда Из-за того, что мы не смогли найти такую подстроку, то, очевидно, что ни один суффикс шаблона <tex>x[i+1 .. m-1]=y[i+j+1 .. j+m-1]=u</tex> и уже не будет лежать в подстроке <tex>x[i] \neq y[i+j]</tex>, т.е. <tex>+1 \dots j+m - i - 1]</tex> символов паттерна уже совпало, поэтому единственный вариант, что в эту подстроку попадет префикс.

Операция [[Файл:boyer-moore-algorithm-2.png|450px|thumb|center|'''сдвига Сдвиг хорошего суффикса''' состоит в выравнивании , только суффикс подстроки <tex>u</tex> с её самым правым вхождением повторно встречается в <tex>x</tex>, идущим справа от символа, отличного от <tex>x[i.]]</tex>.

[[Файл:boyer-moore-algorithm-1===Правило сдвига плохого символа===В таблице плохих символов указывается последняя позиция в шаблоне (исключая последнюю букву) каждого из символов алфавита.gif|450px|thumb|center|'''Сдвиг хорошего суффикса'''Для всех символов, не вошедших в шаблон, вся подстрока пишем <tex>um</tex> полностью встречается справа от символа . Предположим, что у нас не совпал символ <tex>c</tex>из текста на очередном шаге с символом из шаблона. Очевидно, отличного от что в таком случае мы можем сдвинуть шаблон до первого вхождения этого символа <tex>ac</tex>в шаблоне, потому что совпадений других символов точно не может быть. Если в шаблоне такого символа нет, то можно сдвинуть весь шаблон полностью.]]

Если не существует такого сегмента, то смещение состоит в выравнивании самого длинного суффикса символ исходного текста <tex>vy[i + j]</tex> подстроки встречается в шаблоне <tex>y[i+j+1 .. j+m-1]x</tex> , то происходит его выравнивание с соответствующим префиксом его самым правым появлением в подстроке <tex>x[0 \dots m-2]</tex>.

[[Файл:boyer-moore-algorithm-23.gifpng|450px|thumb|center|'''Сдвиг хорошего суффиксаплохого символа''', только суффикс подстроки символ <tex>ua</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>xy[0 .. m-2i+j+1]</tex>.

[[Файл:boyer-moore-algorithm-34.gifpng|450px|thumb|center|'''Сдвиг плохого символа''', символ <tex>ab</tex> не входит в <tex>x</tex>.]]

Если <tex>y[i+j]</tex> не встречается в шаблоне xОбратите внимание, то ни одно вхождение x в y не что сдвиг плохого символа может включать в себя <tex>y[i+j]</tex>быть отрицательным, поэтому исходя из ранее приведенных свойств этих функций берется значение равное максимуму между сдвигом хорошего суффикса и левый конец окна сравнения совмещен с символом непосредственно идущим после <tex>y[i+j]</tex>, т.е. <tex>y[i+j+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)\ 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>suff\mathrm{suffixLength}</tex>, определенный определенную так:для всех <tex>i</tex> таких, что <tex>1 \leqslant i < m</tex> выполняется <tex>suff[\mathrm{suffixLength}(i])=\max\{k : x[i-k+1 .. \dots i]=x[m-k .. \dots m-1]\}</tex>

\min\{i : 1 \leqslant i < m-1\ and\wedge\ x[m-1-i]=c\}, & \mbox{if } c \in x\\

Массивы <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>|\Sigma|=\sigma=ASIZEO(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>O(m+\sigma)p</tex> int[] '''preBmBc'''(string xдлину максимальной подстроки, int m): int bmBc[ASIZE]; <font color=green>// Значение по умолчанию = m</font> for i = 0 .. ASIZE-1 bmBc[i] = m; for i = 0 .. m - 2 bmBc[x[i]] = m - i - 1; return bmBc; Функция для вычисления таблицы суффиксов. Она находит для каждой позиции в шаблоне которая является суффиксом шаблона <tex>x</tex> максимальную длину суффикса . Требует <tex>xO(m - p)</tex>, который повторяется в строке и заканчивается в данной позициивремени. Например//здесь неправильно, для строки "нет смысла сравнивать элементы ШАБЛОНА С САМИМ СОБОЙ '''abcabcabcint'''" таблица будет suffixLength('''0,0,3,0,0,6,0,0,9char'''[m] x, а для строки "'''abcabccint'''" - p): '''0,0,1,0,0,1,7int'''. Также, очевидно, что значение функции для последнего элемента будет равно длине всей строки.len = 0 int[] '''suffixesint'''(string x, int m): int f; int suff[m]; suff[m - 1] i = m;p '''int g ''' j = m - 1; for i = m - 2 .. 0 if ('''while''' i <tex> g and suff[i + m - 1 - f] \geqslant< i - g) suff[i] = suff[i + m - 1 - f]; else if (i < g) g = i; f = i; while (g /tex>= 0 '''and ''' x[gi] == x[g j] ++ m - 1 - f])len --g;i suff[i] = f - g;-j '''return suff;''' 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>. void '''int'''[] preBmGs('''char'''(string [m] x, int m): '''int i, j, suff''' table[XSIZEm]; '''int bmGs[] suff ''' lastPrefixPosition = suffixes(x, m); '''for (''' i = m - 1 .. 0; i < m; ++i) bmGs<font color=green>// Если подстрока x[i] = m; j = 0; for i = +1..m - 1 .. 0] является префиксом, то запомним её начало</font> '''if ''' isPrefix(suff[x, i] =+ 1) lastPrefixPosition = i + 1) while (j < table[m - 1 - i) if (bmGs[j] == m) bmGs[j] = lastPrefixPosition - i + m - 1 - i; ++j <font color=green>// Вычисление функции по определению</font> '''for ''' i = 0 .. m - 2 bmGs[m - 1 - suff'''int''' slen = suffixLength(x, i) table[i]slen] = m - 1 - i;+ slen '''return''' table

void '''function'''BM('''char'''(string x[n] y, int '''char'''[m, string y, int n] x):'''vector <int>''' '''vector <int bmGs[>''' answer <font color=green>// вектор, содержащий все вхождения подстроки в строку</font> '''if''' m];== 0 answer.pushBack(-1) <font color=green>// Искомая подстрока является пустой</font> '''return''' answer int bmBc[ASIZE]; <font color=green>//Предварительные вычисления</font> bmGs '''int'''<tex>[</tex> <tex>|\Sigma|</tex> <tex>]</tex> bmBc = preBmGspreBmBc(x, m); bmBc '''int'''[m] bmGs = preBmBcpreBmGs(x, m); <font color=green>//Поиск подстроки</font> int j = 0; while (j <'''for''' i = m - 1 .. n - m)1 '''int i ''' j = m - 1; '''while (i >= 0 and ''' x[ij] == y[i + ] '''if''' j]== 0 answer.pushBack(i)<font color=green>// Найдена подстрока в позиции i</font>

--j i += max(bmGs[m - 1 - j], bmBc[y[i]]) '''if ''' (i answer == <tex> \varnothing < 0/tex>) OUTPUT answer.pushBack(j-1); <font color=green>// Найдена Искомая подстрока в позиции jне найдена</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[0y[j]]; )<font color/tex> !! Описание|-align=green"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)</fonttex> else|Последние символы совпали. Предпоследние совпали. Третьи символы с конца различны, сдвигаемся на <tex> bmGs[5]= 4</tex>. j +|-align= MAX"center"|[[Файл:BMexample3.png|550px]]|<tex>(12, 7)</tex>|Последние символы совпали, сравниваем далее. Строчка найдена. Продолжаем работу и сдвигаемся на <tex> bmGs[i0]= 7</tex>.|-align="center"|[[Файл:BMexample4.png|550px]]|<tex>(19, 4)</tex>|Последние символы совпали. Предпоследние совпали. Третьи символы с конца различны, bmBcсдвигаемся на <tex> bmGs[5]= 4</tex>.|-align="center"|[y[i + jФайл:BMexample5.png|550px]] |<tex>(23, 7)</tex>|Последние символы совпали, предпоследние различны. Алгоритм закончил работу.|- align="center"|} В итоге, чтобы найти одно вхождение образца длиной <tex>m = 8</tex> в образце длиной <tex>n = 24</tex>, нам понадобилось <tex>17</tex> сравнений символов. ==Асимптотики==* Фаза предварительных вычислений требует <tex>O(m ^2 + 1 \sigma)</tex> времени и памяти.* В худшем случае поиск требует <tex>O(m \cdot n)</tex> сравнений.* В лучшем случае требует <tex > \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> {{---}} размер алфавита. ==Варианты=====Алгоритм Бойера — Мура — Хорспула===Этот алгоритм работает лучше Бойера-Мура на случайных текстах — для него оценка в среднем лучше.Алгоритм использует только сдвиги плохих символов, при этом за такой символ берётся символ из исходного текста, который соответствует последнему символу шаблона, независимо от того, где случилось несовпадение.Поскольку реальные поисковые образцы редко имеют равномерное распределение, алгоритм Бойера-Мура-Хорспула может дать как выигрыш, так и проигрыш по сравнению с стандартной реализацией.===Алгоритм Чжу — Такаоки===На коротких алфавитах сдвиги плохих символов не помогают уже на коротких суффиксах. Простейший способ улучшить работу алгоритма в таких условиях — вместо одного плохого символа строить таблицу для пары символов: несовпавшего и идущего перед ним. Такой алгоритм получил собственное имя: алгоритм Чжу — Такаоки.На предварительную обработку расходуется <tex>O(m+ i\sigma^2);</tex> времени.

* На больших алфавитах (относительно длины шаблона) алгоритм чрезвычайно быстрый и требует намного меньше памяти относительно , чем [[Алгоритм Ахо-Корасик|алгоритма алгоритм Ахо-Корасик]].* Алгоритм проще большинства алгоритмов поиска (при некоторых реализациях объем кода сравним с наивным поиском)* Позволяет добавить множество модификаций, таких как поиск подстроки, включающей ''любой символ (?)'' (но для реализации ''множества символов (*)'' не походитподходит, т.к. так как длина шаблона должна быть известна заранее). 

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

==СсылкиИсточники информации==* [http[wikipedia://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[wikipedia://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[wikipedia://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm Boyer–Moore_string_search_algorithm|Wikipedia:{{---}} Boyer–Moore string search algorithm]]