Изменения

'''Алгоритм Бойера-Мура''', разработанный двумя учеными – {{---}} Бойером (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>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) and \ \wedge\ \mathrm{Co}(i, s)\}</tex>. А значение <tex>bmGs[0]</tex> определим, как длину периода шаблона <tex>x</tex>.

Для вычисления bmGs будем использовать таблицу А значение <tex>suffbmGs[0]</tex>определим, определенную так:для всех как длину периода шаблона <tex>i</tex> таких, что <tex>1 \leqslant i < mx</tex> выполняется <tex>suff[i]=\max\{k : x[i-k+1 .. i]=x[m-k .. m-1]\}</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>. void '''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 bmBc''' suffixLength('''char'''[m]x, '''int''' p) {: '''int''' len = 0 '''int ''' i;= p for ('''int''' j = m - 1 '''while''' i = <tex>\geqslant</tex> 0; '''and''' x[i < ASIZE; ] == 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): bmBc '''int''' table[im] '''int''' lastPrefixPosition = m; '''for (''' i = m - 1 .. 0; <font color=green>// Если подстрока x[i < +1..m - 1; ] является префиксом, то запомним её начало</font> '''if''' isPrefix(x, i +1) lastPrefixPosition = i +i)1 bmBc[xtable[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

Основная функция алгоритма Бойера-Мура void suffixes'''function''' BM('''char *x'''[n] y, int '''char'''[m, ] x): '''vector <int *suff) {>''' '''vector <int f>''' answer <font color=green>// вектор, g, i;содержащий все вхождения подстроки в строку</font> suff['''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) g <font color= m - 1;green>// Поиск подстроки</font> '''for (''' i = m - 2; i >1 .. n - 1 '''int''' j = 0; -m -1 '''while''' x[j] == y[i) {] '''if ''' j == 0 answer.pushBack(i ) <font color=green> g && suff[// Найдена подстрока в позиции i + m </font> - 1 - f] < i -- g)j suff[ i] += suffmax(bmGs[i + m - 1 - fj], bmBc[y[i];]) else { '''if ''' (i answer == <tex> \varnothing < g/tex>) g answer.pushBack(-1) <font color= i;green>// Искомая подстрока не найдена</font> '''return''' answer  f = i;=Пример== while (g Пусть нам дана строка <tex>y = 0 && GCATCGCAGAGAGTATACAGTACG</tex> и образец <tex>x=GCAGAGAG</tex>. Построим массивы <tex>bmBc</tex> и <tex>bmGs</tex> : [g[Файл:RaitaPre.png|250px] == x[g + m - 1 - f]) --g; suff[i[Файл:Crochemore.png|300px]] = f - g; } }Рассмотрим шаги алгоритма: } {| class = "wikitable" void preBmGs! Изображение !! <tex>(char *xj, int m, int bmGs[y[j]]) {</tex> !! Описание|-align="center" int i, j, suff|[[XSIZEФайл:BMexample1.png|550px]]; suffixes|<tex>(x7, m, suff1);</tex> for (i = 0; i |Сравниванием последние символы, они неравны, поэтому сдвигаемся на < m; ++i) tex> bmGs[iy[j]]</tex>, где <tex>y[j] = m; </tex> {{---}} это не совпавший символ. В данном случае <tex>y[j ]= 0; for (i 7</tex>, а <tex> bmGs[7]= m - 1; i </tex>.|-align= 0; --i)"center" if (suff|[[iФайл:BMexample2.png|550px]] == i + 1) for |<tex>(; j 8, 4)< m - 1 - i; ++j)/tex> if (|Последние символы совпали. Предпоследние совпали. Третьи символы с конца различны, сдвигаемся на <tex> bmGs[j5] =4</tex>.|-align= m"center"|[[Файл:BMexample3.png|550px]]|<tex>(12, 7)</tex> |Последние символы совпали, сравниваем далее. Строчка найдена. Продолжаем работу и сдвигаемся на <tex> bmGs[j0] = m 7</tex>.|- 1 - i;align="center"|[[Файл:BMexample4.png|550px]] for |<tex>(i 19, 4)</tex>|Последние символы совпали. Предпоследние совпали. Третьи символы с конца различны, сдвигаемся на <tex> bmGs[5]= 0; i 4</tex>.|-align= m - 2; ++i)"center" bmGs|[m - 1 - suff[iФайл:BMexample5.png|550px]] |<tex>(23, 7)</tex>|Последние символы совпали, предпоследние различны. Алгоритм закончил работу.|-align= m - 1 - i;"center" |} В итоге, чтобы найти одно вхождение образца длиной <tex>m = 8</tex> в образце длиной <tex>n = 24</tex>, нам понадобилось <tex>17</tex> сравнений символов. ==Асимптотики== void BM* Фаза предварительных вычислений требует <tex>O(char m^2 + \sigma)</tex> времени и памяти.*x, int В худшем случае поиск требует <tex>O(m, char \cdot n)</tex> сравнений.*y, int В лучшем случае требует <tex > \Omega \left( \dfrac{n}{m} \right) {</tex> сравнений. int i, j, bmGs[XSIZE], bmBc[ASIZE]; '''Пример:''' Исходный текст <tex>bb \dots bb</* Preprocessing *tex> и шаблон <tex>abab \dots abab</ preBmGs(xtex>. Из-за того, что все символы <tex>b</tex> из текста повторяются в шаблоне <tex>\dfrac{m}{2}</tex> раз, эвристика хорошего суффикса будет пытаться сопоставить шаблон в каждой позиции (суммарно, bmGs<tex>n</tex> раз); preBmBc(x, а эвристика плохого символа в каждой позиции будет двигать строку <tex>\dfrac{m}{2}</tex> раз. Итого, bmBc<tex>O(n \cdot m); /* Searching *</tex>. j = 0; while (j где <= tex>n </tex> {{--- }} длина исходного текста, <tex>m) </tex> {{---}} длина шаблона, <tex>\sigma</tex> {{---}} размер алфавита.  for (i = m - 1; i >= 0 && x[i] Варианты=====Алгоритм Бойера — Мура — Хорспула=== y[i + j]; Этот алгоритм работает лучше Бойера--i);Мура на случайных текстах — для него оценка в среднем лучше. if (i < 0) {Алгоритм использует только сдвиги плохих символов, при этом за такой символ берётся символ из исходного текста, который соответствует последнему символу шаблона, независимо от того, где случилось несовпадение. OUTPUT(j);Поскольку реальные поисковые образцы редко имеют равномерное распределение, алгоритм Бойера-Мура-Хорспула может дать как выигрыш, так и проигрыш по сравнению с стандартной реализацией. j += bmGs[0];==Алгоритм Чжу — Такаоки=== }На коротких алфавитах сдвиги плохих символов не помогают уже на коротких суффиксах. Простейший способ улучшить работу алгоритма в таких условиях — вместо одного плохого символа строить таблицу для пары символов: несовпавшего и идущего перед ним. Такой алгоритм получил собственное имя: алгоритм Чжу — Такаоки. else j += MAXНа предварительную обработку расходуется <tex>O(bmGs[i], bmBc[y[i + j]] - m + 1 + i\sigma^2); } }</tex> времени.

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

* На искусственно подобранных неудачных текстах (например, needle=«колоколоколоколоколокол») скорость алгоритма Бойера-Мура серьёзно снижается. ==Источники информации==* [[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 Алгоритм Боуера-Мура]

==Ссылки==* [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]