Турбо-алгоритм Бойера-Мура
Турбо-алгоритм Бойера-Мура (англ. Turbo Boyer-Moore) является улучшением алгоритма Бойера-Мура. Турбо-алгоритм, разработанный группой учёных во главе с М.Крочемором, предлагает другой подход к коротким алфавитам и заодно решает вторую проблему — квадратичную сложность в худшем случае.
Алгоритм
Турбо-алгоритм Бойера-Мура не нуждается в дополнительном препроцессинге и требует только постоянную дополнительную память относительно оригинального алгоритма Бойера-Мура. Он состоит в запоминании сегмента текста, который соответствует суффиксу шаблона во время последней попытки (и только тогда, когда сдвиг хорошего суффикса был выполнен). Эта методика представляет два преимущества:
- Можно перепрыгнуть через этот сегмент.
- Она может позволить выполнение «турбо-сдвига».
Турбо-сдвиг может произойти, если мы обнаружим, что суффикс образца, который сходится с текстом, короче, чем тот, который был запомнен ранее.
Пусть — запомненный сегмент, а — cуффикс, совпавший во время текущей попытки, такой что — суффикс . Тогда — суффикс , два символа и встречаются на расстоянии в тексте, и суффикс длины имеет период длины , а значит не может перекрыть оба появления символов и в тексте. Наименьший возможный сдвиг имеет длину (его мы и называем турбо-сдвигом).
Применение турбо-сдвига в случае |v| < |u|
При , если сдвиг плохого символа больше, то совершаемый сдвиг будет больше либо равен . В этом случае символы и различны, так как мы предположили, что предыдущий сдвиг был сдвигом хорошего суффикса. Тогда сдвиг больший, чем турбо-сдвиг, но меньший совместит и с одним и тем же символом . Значит, если сдвиг плохого символа больше, то мы можем применить сдвиг больший либо равный .
Нельзя совместить символы с одним и тем же символом .
Псевдокод
Стадия препроцессинга совпадает со стадией препроцессинга в алгоритме Бойера-Мура.
В сам алгоритм добавляется обработка турбо-сдвигов.
function TBM(char[] x, char[] y, int n, int m)
int n = length(y)
int m = length(x)
int i = 0
int u = 0
int shift = m
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)
print(i)
shift = bm_gs[0]
u = m - shift
else
int v = m - 1 - j
int turbo_shift = u - v
int bc_shift = bm_bc[y[i + j]] - m + j + 1
shift = max(turbo_shift, bc_shift, bm_gs[j + 1])
if (shift == bm_gs[j + 1])
u = min((m - shift), v)
else
if (turbo_shift < bc_shift)
shift = min(shift, (u + 1))
u = 0
i += shift
Асимптотика
| Утверждение: |
|
|
Разобьём поиск на стадии. Каждая стадия делится на две операции: сканирование и сдвиг. На этапе мы назовём длину суффикса шаблона что совпадает с текстом. Этому предшествует символ, который не совпадает с соответствующим символом в тексте (в случае когда не соответствует длине шаблона). Мы также назовём длину сдвига сделанного на этапе . Рассмотрим три типа стадий в зависимости от характера сканирования и сдвига. Мы говорим, что сдвиг на стадии короткий, если . Тогда три типа сдвигов будут:
Идея доказательства состоит в амортизации сравнения со сдвигами. Определим стоимость следующим образом:
В случае стадии типа (1), стоимость соответствует единственному сравнению несовпадающих символов. Другие сравнения, проведенные в течение той же стадии, являются стоимостью последующих этапов. Общее количество сравнений выполняемых алгоритмом это сумма стоимостей. Мы хотим доказать, что . Во второй длину последнего сдвига заменим . Даже с этим предположением, мы имеем , и если неравенство выполняется, тo . Для стадии типа (1), очевидным образом меньше, чем , так как . Для стадии типа (2), , по определению длинных сдвигов. Остается рассмотреть стадии типа (3). Так как в этой ситуации мы имеем , единственный вариант, что обычный сдвиг применяется на стадии . Тогда мы запоминаем этот момент. На следующей стадии, , мы что-то запомнили, что приводит к возможному турбо-сдвигу. Ситуация на стадии , основная ситуация, когда турбо-сдвиг возможен. Прежде чем продолжить доказательство, мы сначала рассмотрим два случая и установим неравенства (по стоимости стадии ), которые используем позже.
|
