Изменения

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

Алгоритм сравнивает символы шаблона <tex>yx</tex> справа налево, начиная с самого правого, один за другим с символами исходной строки <tex>xy</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двиг, не подойдутсравнивать с текстом {{---}} возможность для модификации и дальнейшего ускорения алгоритма.

Если не существует такой подстрокитаких подстрок, то смещение состоит в выравнивании самого длинного суффикса <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>, поэтому единственный вариант, что в эту подстроку попадет префикс.

Если символ исходного текста <tex>y[i + j]</tex> встречается в шаблоне <tex>x</tex>, то происходит его выравнивание с его самым правым появлением в подстроке <tex>x[0 .. \dots m-2]</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>i</tex> таких, что <tex>0 \leqslant i < m</tex> выполняется <tex>bmGs[i+1]=\min\{s > 0 : Cs(i, s)\ and\ Co(i, s)\}</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=ASIZE</tex> обозначим размер нашего алфавита.

Функция для вычисления таблицы сдвигов плохих символов. Она будет равна длине шаблона для всех символов, которые не встречаются в шаблоне, и порядковому номеру с конца для остальных (кроме последнего, для него тоже берется длина шаблона). Вычисляется прямо по определению за <tex>O(m+\sigma)</tex>. '''int'''[] preBmBc('''stringchar''' [m] x, '''int''' m): '''int''' bmBctable<tex>[ASIZE</tex> <tex>|\Sigma|</tex> <tex>]</tex> <font color=green>// Значение Заполняем значением по умолчанию = m, равным длине шаблона</font> '''for''' i = 0 .. ASIZE<tex>|\Sigma|</tex> -1 bmBctable[i] = m <font color=green>// Вычисление функции по определению</font>

bmBctable[x[i]] = m - 1 - i - 1 '''return''' bmBc Функция для вычисления таблицы суффиксов. Она находит для каждой позиции в шаблоне <tex>x</tex> максимальную длину суффикса <tex>x</tex>, который повторяется в строке и заканчивается в данной позиции. 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{| class '''for''' i ="wikitable"p .. m - 1 '''if''' x[i] ! Строка || Значение функции= x[j]|-| abcabcabc || 0, 0, 3, 0, 0, 6, 0, 0, 9 '''return''' false|- ++j| abcabcc || 0, 0, 1, 0, 0, 1, 7|} '''return''' true

ТакжеФункция, очевидновозвращающая для позиции <tex>p</tex> длину максимальной подстроки, что значение функции для последнего элемента будет равно длине всей строкикоторая является суффиксом шаблона <tex>x</tex>. Требует <tex>O(m - p)</tex> времени.//здесь неправильно, нет смысла сравнивать элементы ШАБЛОНА С САМИМ СОБОЙ '''int'''[] suffixessuffixLength(string x, int m): '''intchar''' f = 0 [m] x, '''int''' suff[m] suff[m - 1] = mp): '''int''' g len = m - 10 '''forint''' i = m - 2 .. 0p '''ifint''' i > g and suff[i + m - 1 - f] < i - g suff[i] j = suff[i + m - 1 - f] '''else''' '''ifwhile''' i < g g = i f = i tex>\geqslant</tex> 0 '''whileand''' g >= 0 and x[gi] == x[g j] + m - 1 - f]+len --gi suff[i] = f - g-j '''return''' sufflen

Функция для вычисления сдвигов хороших суффиксов. Требует <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>. '''voidint''' [] preBmGs(string x, int m) '''intchar''' i, j, suff[XSIZEm]x): '''int''' bmGstable[m] suff = suffixes(x, m) '''forint''' i lastPrefixPosition = 0 .. m - 1 bmGs[i] = m j = 0

<font color=green>// Если подстрока x[i+1..m-1] является префиксом, то запомним её начало</font> '''if''' suff[isPrefix(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>

bmGs'''int''' slen = suffixLength(x, i) table[m - 1 - suff[i]slen] = m - 1 - i+ slen '''return''' table

'''voidfunction''' BM(string x'''char'''[n] y, int '''char'''[m, string y, int n] x):'''vector <int>''' '''vector <int>''' answer <font color=green>// вектор, содержащий все вхождения подстроки в строку</font> '''if''' bmGs[m]== 0 answer.pushBack(-1) <font color=green>// Искомая подстрока является пустой</font> '''intreturn''' bmBc[ASIZE]answer <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> '''intfor''' j = 0 '''while''' j <i = m - 1 .. n - m1 '''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</fonttex>.|-align="center"|[[Файл:BMexample2.png|550px]]|<tex>(8, 4)</tex> '''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, bmBc4)</tex>|Последние символы совпали. Предпоследние совпали. Третьи символы с конца различны, сдвигаемся на <tex> bmGs[5]= 4</tex>.|-align="center"|[y[i + jФайл:BMexample5.png|550px]] |<tex>(23, 7)</tex>|Последние символы совпали, предпоследние различны. Алгоритм закончил работу.|- align="center"|} В итоге, чтобы найти одно вхождение образца длиной <tex>m + 1 + i)= 8</tex> в образце длиной <tex>n = 24</tex>, нам понадобилось <tex>17</tex> сравнений символов.

* Фаза предварительных вычислений требует <tex>O(m ^2 + \sigma)</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>abcabcabcabcabc</tex>) скорость алгоритма Бойера-Мура серьёзно снижается.

==СсылкиИсточники информации==