418
правок
Изменения
Нет описания правки
==Алгоритм==
Алгоритм сравнивает символы шаблона <tex>y</tex> справа налево, начиная с самого правого, один за другим с символами исходной строки <tex>x</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] \neq y[i+j]</tex>, и <tex>m - i - 1</tex> символов шаблона уже совпало.
===Правило сдвига хорошего суффикса===
[[Файл:boyer-moore-algorithm-1.png|450px|thumb|center|'''Сдвиг хорошего суффикса''', вся подстрока <tex>u</tex> полностью встречается справа от символа <tex>c</tex>, отличного от символа <tex>a</tex>.]]
Если не существует такой подстроки, то смещение состоит в выравнивании самого длинного суффикса <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>, поэтому единственный вариант, что в эту подстроку попадет префикс.
[[Файл:boyer-moore-algorithm-2.png|450px|thumb|center|'''Сдвиг хорошего суффикса''', только суффикс подстроки <tex>u</tex> повторно встречается в <tex>x</tex>.]]
В таблице плохих символов указывается последняя позиция в шаблоне (исключая последнюю букву) каждого из символов алфавита. Для всех символов, не вошедших в шаблон, пишем <tex>m</tex>. Предположим, что у нас не совпал символ <tex>c</tex> из текста на очередном шаге с символом из шаблона. Очевидно, что в таком случае мы можем сдвинуть шаблон до первого вхождения этого символа <tex>c</tex> в шаблоне, потому что совпадений других символов точно не может быть. Если в шаблоне такого символа нет, то можно сдвинуть весь шаблон полностью.
Если символ исходного текста <tex>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>.]]
[[Файл:boyer-moore-algorithm-4.png|450px|thumb|center|'''Сдвиг плохого символа''', символ <tex>b</tex> не входит в <tex>x</tex>.]]
Обратите внимание, что сдвиг плохого символа может быть отрицательным, поэтому исходя из ранее приведенных свойств этих функций берется значение равное максимуму между сдвигом хорошего суффикса и сдвигом плохого символа.
===Формальное определение===
Теперь определим две функции сдвигов более формально следующим образом:
Для вычисления bmGs будем использовать функцию <tex>suffixLength</tex>, определенную так:
для всех <tex>i</tex> таких, что <tex>1 \leqslant i < m</tex> выполняется <tex>suffixLength[i]=\max\{k : x[i-k+1 .. \dots i]=x[m-k .. \dots m-1]\}</tex>
Сдвиги плохих символов будем хранить в массиве <tex>bmBc</tex> размером <tex>\sigma</tex>.
'''return''' table
Функция, проверяющая, что подстрока <tex>x[p..\dots m - 1]</tex> является префиксом шаблона <tex>x</tex>. Требует <tex>O(m - p)</tex> времени.
'''boolean''' isPrefix('''char'''[] x, '''int''' m, '''int''' p):
'''int''' j = 0
'''return''' len
Функция для вычисления сдвигов хороших суффиксов. Требует <tex>O(m)</tex> времени, несмотря на циклы в вызываемых функциях, из-за того, что каждый внутренний цикл в худшем случае будет выполняться на каждой позиции <tex>i</tex> не больше, чем <tex>i</tex> раз. Получается арифметическая прогрессиянатуральный ряд, сумма которой <tex>O(k \cdot m)</tex>, где первых членов которого <texdpi="150">k\frac{m \cdot (m - 1)}{2}</tex> {{---}} константа. Следовательно, получается оценка по времени <tex>O(m^2)</tex>.
'''int'''[] preBmGs('''char'''[] x, '''int''' m):
'''int''' table[m]
==Асимптотики==
* Фаза предварительных вычислений требует <tex>O(m ^2 + \sigma)</tex> времени и памяти
* В худшем случае поиск требует <tex>O(m \cdot n)</tex> сравнений.
* В лучшем случае требует <tex>O(n / m)</tex> сравнений.
'''Пример:'''
Исходный текст <tex>bb..\dots bb</tex> и шаблон <tex>abab..\dots abab</tex>. Из-за того, что все символы <tex>b</tex> из текста повторяются в шаблоне <tex>m / 2</tex> раз, эвристика хорошего суффикса будет пытаться сопоставить шаблон в каждой позиции (суммарно, <tex>n</tex> раз), а эвристика плохого символа в каждой позиции будет двигать строку <tex>m / 2</tex> раз. Итого, <tex>O(n \cdot m)</tex>.
где <tex>n</tex> {{---}} длина исходного текста, <tex>m</tex> {{---}} длина шаблона, <tex>\sigma</tex> {{---}} размер алфавита.
* [[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 Алгоритм Боуера-Мура]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Поиск подстроки в строке]]
