Изменения

'''Алгоритм Бойера-Мура''', разработанный двумя учеными – {{---}} Бойером (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>x[i+1 \dots m-1]=y[i+j+1 \dots j+ m-1]=u</tex> и <tex>x[i] \sigma)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>O(y[i+j+1 \dots j+m -1]</tex> с соответствующим префиксом <tex>x</tex>. Из-за того, что мы не смогли найти такую подстроку, то, очевидно, что ни один суффикс шаблона <tex>x</tex> уже не будет лежать в подстроке <tex>y[i+j+1 \cdot n)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>O(n 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> сравнений.]] Обратите внимание, что сдвиг плохого символа может быть отрицательным, поэтому исходя из ранее приведенных свойств этих функций берется значение равное максимуму между сдвигом хорошего суффикса и сдвигом плохого символа. ===Формальное определение===

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

==Алгоритм==Алгоритм сравнивает символы ''шаблона'' (Пусть значения функции сдвига хорошего суффикса хранятся в массиве <tex>ybmGs</tex>) справа налево, начиная с самого правого, один за другим с символами ''исходной строки'' (размером <tex>xm+1</tex>). В случае несовпадения какого-либо символа (или полного совпадения всего шаблона) он использует две предварительно вычисляемых функций, чтобы сдвинуть позицию для начала сравнения вправо.

Пусть Определим два условия:* <tex>|y|\mathrm{Cs}(i, s)</tex>: для каждого <tex>k</tex> такого, что <tex>i < k < m</tex> выполняется <tex>s \geqslant k</tex> или <tex>x[k-s]=nx[k]</tex> и * <tex>|\mathrm{Co}(i, s)</tex>: если <tex>s < i</tex>, то выполняется <tex>x[i-s] \neq x|=m[i]</tex>.

Предположим, что в процессе сравнения возникает несовпадение между символом Тогда для всех <tex>x[i]=a</tex> шаблона и символом таких, что <tex>y[0 \leqslant i+j]=b</tex> исходного текста при проверке в позиции <tex>jm</tex>. Тогда выполняется <tex>xbmGs[i+1 .. m-1]=y[i+j+1 .. j+m-1]=u</tex\min\{s > и <tex>x[0 : \mathrm{Cs}(i] , s)\ \wedge\ \neq y[mathrm{Co}(i+j]</tex>, т.е. <tex>m - i - 1s)\}</tex> символов паттерна уже совпало.

Операция '''сдвига хорошего суффикса''' состоит в выравнивании подстроки А значение <tex>ubmGs[0]</tex> с его самым правым вхождением в <tex>x</tex>, что идет впереди символаопределим, отличного от как длину периода шаблона <tex>x[i]</tex>.

[[Файл:boyer-moore-algorithm-1.gif|450px|thumb|center|'''Сдвиг хорошего суффикса''', вся подстрока Для вычисления <tex> bmGs </tex> будем использовать функцию <tex>u\mathrm{suffixLength}</tex> полностью встречается повторно до символа , определенную так:для всех <tex>ci</tex>таких, отличного от символа что <tex>a1 \leqslant i < m</tex>.выполняется <tex>\mathrm{suffixLength}(i)=\max\{k : x[i-k+1 \dots i]=x[m-k \dots m-1]\}</tex>

Если не существует такого сегмента, то смещение состоит Сдвиги плохих символов будем хранить в выравнивании самого длинного суффикса массиве <tex>vbmBc</tex> подстроки размером <tex>\sigma</tex>y[i+j+1 .. j+m-1]Для каждого символа <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>.

[[Файл:boyer-moore-algorithm-2.gif|450px|thumb|center|'''Сдвиг хорошего суффикса''', только суффикс подстроки Массивы <tex>bmBc</tex> и <tex>bmGs</tex> вычисляются за <tex>uO(m^2+\sigma)</tex> повторно встречается в времени до основной фазы поиска и требуют, очевидно, <tex>xO(m+\sigma)</tex>памяти.]]

Операция '''сдвига плохого символа''' состоит в выравнивании символа исходного текста ==Псевдокод==Константой <tex>у[i + j]</tex> с его самым правым появлением в <tex>x[0 .. m-2]|\Sigma|=\sigma</tex>обозначим размер нашего алфавита.

Функция для вычисления таблицы сдвигов плохих символов. Она будет равна длине шаблона для всех символов, которые не встречаются в шаблоне, и порядковому номеру с конца для остальных (кроме последнего, для него тоже берется длина шаблона). Вычисляется прямо по определению за <tex>O(m+\sigma)</tex>. '''int'''[] preBmBc('''char'''[Файлm] x):boyer-moore-algorithm-3.gif '''int''' table<tex>[</tex> <tex>|450px|thumb|center\Sigma|</tex> <tex>]</tex> <font color=green>// Заполняем значением по умолчанию, равным длине шаблона</font> '''Сдвиг плохого символаfor''', символ i = 0 .. <tex>a|\Sigma|</tex> входит в - 1 table[i] = m <texfont color=green>x// Вычисление функции по определению</texfont> '''for''' i = 0 ..m - 2 table[x[i]]= m - 1 - i '''return''' table

Если Функция, проверяющая, что подстрока <tex>yx[i+jp \dots m - 1]</tex> не встречается в шаблоне x, то ни одно вхождение x в y не может включать в себя является префиксом шаблона <tex>y[i+j]x</tex>, и левый конец окна сравнения совмещен с символом непосредственно идущим после . Требует <tex>y[i+j]O(m - p)</tex>времени. '''boolean''' isPrefix('''char'''[m] x, т'''int''' p): '''int''' j = 0 '''for''' i = p .е. <tex>ym - 1 '''if''' x[i] != x[j] '''return''' false ++j+1]</tex>. '''return''' true

Функция, возвращающая для позиции <tex>p</tex> длину максимальной подстроки, которая является суффиксом шаблона <tex>x</tex>. Требует <tex>O(m - p)</tex> времени. //здесь неправильно, нет смысла сравнивать элементы ШАБЛОНА С САМИМ СОБОЙ '''int''' suffixLength('''char'''[[Файлm] x, '''int''' p):boyer-moore '''int''' len = 0 '''int''' i = p '''int''' j = m -algorithm-4.gif|450px|thumb|center|1 '''Сдвиг плохого символаwhile''', символ i <tex>b\geqslant</tex> не входит в <tex>0 '''and''' x</tex>.[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>. void preBmBc'''int'''[] preBmGs('''char *'''[m] x, ): '''int ''' table[m, int bmBc[]) { '''int i;''' lastPrefixPosition = m '''for (''' i = m - 1 .. 0; <font color=green>// Если подстрока x[i +1..m-1] является префиксом, то запомним её начало< ASIZE; /font> '''if''' isPrefix(x, i +1) lastPrefixPosition = i +i)1 bmBctable[m - 1 - i] = lastPrefixPosition - i + m;- 1 <font color=green>// Вычисление функции по определению</font> '''for (''' i = 0; i < .. m - 1; ++2 '''int''' slen = suffixLength(x, i) bmBc[xtable[i]slen] = m - 1 - i - 1;+ 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]