Турбо-алгоритм Бойера-Мура
Турбо-алгоритм Бойера-Мура (англ. Turbo Boyer-Moore) является улучшением алгоритма Бойера-Мура. Турбо-алгоритм, разработанный группой учёных во главе с М.Крочемором, предлагает другой подход к коротким алфавитам и заодно решает вторую проблему — квадратичную сложность в худшем случае.
Алгоритм
Турбо-алгоритм Бойера-Мура не нуждается в дополнительном препроцессинге и требует только постоянную дополнительную память относительно оригинального алгоритма Бойера-Мура. Он состоит в запоминании сегмента текста, который соответствует суффиксу шаблона во время последней попытки (и только тогда, когда сдвиг хорошего суффикса был выполнен). Эта методика представляет два преимущества:
- Можно перепрыгнуть через этот сегмент.
- Она может позволить выполнение «турбо-сдвига».
Турбо-сдвиг может произойти, если мы обнаружим, что суффикс образца, который сходится с текстом, короче, чем тот, который был запомнен ранее.
Определение турбо-сдвига
Пусть — запомненный сегмент, а — cуффикс, совпавший во время текущей попытки, такой что — суффикс . Тогда — суффикс , два символа и встречаются на расстоянии в тексте, и суффикс длины имеет период длины , а значит не может перекрыть оба появления символов и в тексте. Наименьший возможный сдвиг имеет длину (его мы и называем турбо-сдвигом).
Применение турбо-сдвига в случае |v| < |u|
При , если длина сдвига плохого символа больше, чем длина сдвига хорошего суффикса и длины турбо-сдвига, то длина фактического сдвига должна быть больше или равна . Действительно, в этом случае два символа и различны, так как мы предположили, что предыдущий сдвиг был сдвигом хороший суффикса. Тогда сдвиг больший, чем турбо-сдвиг, но меньший, чем будет выравнивать и с таким же символом в , в этом случае длина фактического сдвига должна быть по крайней мере равен .
Нельзя совместить символы с одним и тем же символом .
Описание алгоритма
В алгоритм Бойера-Мура дополнительно добавится запоминание длины сегмента текста, который соответствует суффиксу шаблона во время последней попытки, который мы не будем лишний раз рассматривать при сравнении суффиксов двух подстрок, а также запоминании размера сдвига , который мы совершили. Вычислять его будем следующим образом:
- Если текущем шаге у нас подстрока совпала с шаблоном , то ( равен периоду шаблона ), .
- Иначе возможны два случая:
- Если сдвиг хорошего суффикса не меньше турбо-сдвига и сдвига плохого символа, тогда , ( текущая подстрока).
- В противном случае, , ( длина турбо-сдвига, длина сдвига плохого символа), если турбо-сдвиг меньше сдвига плохого символа, то должен быть не больше ( сегмент текста, рассматриваемый на прошлом шаге).
Псевдокод
Стадия препроцессинга совпадает со стадией препроцессинга в алгоритме Бойера-Мура, функция вычислений сдвигов плохих символов и функция вычисления хороших суффиксов не меняются, меняется только сам алгоритм, в него добавляется обработка турбо-сдвигов.
function TBM(char[] x, char[] y, int n, int m): List<int>
int i = 0
int u = 0
int shift = m
List<int> answer;
if (m == 0)
return
//Предварительные вычисления
int bmBc[] = preBmBc(x, m)
int bmGs[] = preBmGs(x, m)
while (i <= n - m)
int j = m - 1
while (j >= 0 and x[j] == y[i + j])
--j
if (u != 0 and j == m - 1 - shift)
j -= u
if (j < 0)
answer.add(i)
shift = bmGs[0]
u = m - shift
else
int v = m - 1 - j
int turboShift = u - v
int bCShift = bmBc[y[i + j]] - m + j + 1
shift = max(turboShift, bCShift, bmGs[j + 1])
if (shift == bmGs[j + 1])
u = min((m - shift), v)
else
if (turboShift < bcShift)
shift = min(shift, (u + 1))
u = 0
i += shift
return answer
Асимптотика
| Утверждение: |
|
|
Стадия препроцессинга совпадает со стадией препроцессинга в алгоритме Бойера-Мура, поэтому рассмотрим только стадию поиска. Разобьём поиск на стадии. Каждая стадия делится на две операции: сканирование и сдвиг. На этапе мы назовём длину суффикса шаблона, что совпадает с текстом. Этому предшествует символ, который не совпадает с соответствующим символом в тексте (в случае когда не соответствует длине шаблона). Мы также назовём длину сдвига, сделанного на этапе . Рассмотрим три типа стадий в зависимости от характера сканирования и сдвига. Мы говорим, что сдвиг на стадии короткий, если . Тогда три типа сдвигов будут:
Идея доказательства состоит в амортизации сравнения со сдвигами. Определим стоимость следующим образом:
В случае стадии типа (1), стоимость соответствует единственному сравнению несовпадающих символов. Другие сравнения, проведенные в течение той же стадии, являются стоимостью последующих этапов. Общее количество сравнений выполняемых алгоритмом это сумма стоимостей. Мы хотим доказать, что . Во второй длину последнего сдвига заменим . Даже с этим предположением, мы имеем , и если неравенство выполняется, тo . Для стадии типа (1), очевидным образом меньше, чем , так как . Для стадии типа (2), , по определению длинных сдвигов. Остается рассмотреть стадии типа (3). Так как в этой ситуации мы имеем , единственный вариант, что обычный сдвиг применяется на стадии . Тогда мы запоминаем этот момент. На следующей стадии, , мы что-то запомнили, что приводит к возможному турбо-сдвигу. Ситуация на стадии , основная ситуация, когда турбо-сдвиг возможен. Прежде чем продолжить доказательство, мы сначала рассмотрим два случая и установим неравенства (по стоимости стадии ), которые используем позже.
Можно считать, что на стадии случай (б) имеет место, потому что это дает нам верхнюю границу (это верно, если , случай можно обрабатывать напрямую). Если стадия типа (1), то , а затем , что даже лучше, чем ожидалось. Если на стадии мы имеем , то мы получим то, что ожидалось: . Последняя ситуация для рассмотрения, когда на стадии мы имеем . Это означает, что, как уже упоминалось ранее, обычный сдвиг применяется на стадии . Таким образом, приведенный выше анализ также применяется на стадии , и, так как только случай (а) может произойти тогда мы получаем . Мы, наконец, получаем . Последний аргумент, доказывающий первый шаг индукции: если все стадии до таковы, что , то . Пусть первый этап после этапа такой, что . Целое число существует потому, что иначе получим бесконечную последовательность сдвигов с уменьшающейся длиной. После этого мы получим . Это показывает нам, что , что и требовалось. |
Пример работы
Пусть нам дана строка и образец
Построим массив :
Рассмотрим шаги алгоритма:
| Изображение | Описание | |
|---|---|---|
|
Делаем сравнение последних символов, оно неудачно, сдвигаемся на . | |
|
Последние два символа совпали, сдвигаемся на . | |
|
Все символы совпали, Продолжим работу (для примера, в обычном варианте на этом этапе мы можем выйти, если требуется найти только одно вхождение) и сдвинемся на . | |
|
Последние два символа совпали, сдвигаемся на . | |
|
Последние символы совпали, сравниваем предпоследние, сдвигаемся. Строка закончилась, выходим. |
В итоге, чтобы найти одно вхождение образца длиной в образце длиной нам понадобилось сравнений символов
