418
правок
Изменения
Нет описания правки
Пусть <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 .. m-1]=y[i+j+1 .. 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>.
[[Файл:boyer-moore-algorithm-3.gif|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.gif|450px|thumb|center|'''Сдвиг плохого символа''', символ <tex>b</tex> не входит в <tex>x</tex>.]]
'''return''' bmBc
Функция для вычисления таблицы суффиксов. Она находит для каждой позиции в шаблоне <tex>x</tex> максимальную длину суффикса <tex>x</tex>, который повторяется в строке и заканчивается в данной позиции. Например, для строки " '''abcabcabcПримеры:'''{| class="wikitable" таблица будет '''! Строка || Значение функции|-| abcabcabc || 0,0,3,0,0,6,0,0,9''', а для строки "'''|-| abcabcc'''" - '''|| 0,0,1,0,0,1,7'''. |} Также, очевидно, что значение функции для последнего элемента будет равно длине всей строки.
'''int'''[] '''suffixes'''(string x, int m):
'''int''' f = 0
* На больших алфавитах (например, Юникод) может занимать много памяти. В таких случаях либо обходятся хэш-таблицами, либо дробят алфавит, рассматривая, например, 4-байтовый символ как пару двухбайтовых.
* На искусственно подобранных неудачных текстах (например, шаблон "abcabcabcabcabc") скорость алгоритма Бойера-Мура серьёзно снижается.
==Варианты==
===Алгоритм Бойера — Мура — Хорспула===
Этот алгоритм работает лучше Бойера-Мура на случайных текстах — для него оценка в среднем лучше.
Алгоритм использует только сдвиги плохих символов, при этом за такой символ берётся символ из исходного текста, который соответствует последнему символу шаблона, независимо от того, где случилось несовпадение.
Поскольку реальные поисковые образцы редко имеют равномерное распределение, алгоритм Бойера-Мура-Хорспула может дать как выигрыш, так и проигрыш по сравнению с стандартной реализацией.
===Алгоритм Чжу — Такаоки===
На коротких алфавитах сдвиги плохих символов не помогают уже на коротких суффиксах. Простейший способ улучшить работу алгоритма в таких условиях — вместо одного плохого символа строить таблицу для пары символов: несовпавшего и идущего перед ним. Такой алгоритм получил собственное имя: алгоритм Чжу — Такаоки.
На предварительную обработку расходуется <tex>O(m+\sigma^2)</tex> времени.
==Ссылки==
