Турбо-алгоритм Бойера-Мура — различия между версиями
Zemskovk (обсуждение | вклад) (→Псевдокод) |
Zemskovk (обсуждение | вклад) (→Псевдокод) |
||
| Строка 43: | Строка 43: | ||
'''int''' v = m - 1 - j | '''int''' v = m - 1 - j | ||
'''int''' turbo_shift = u - v | '''int''' turbo_shift = u - v | ||
| − | '''int''' bc_shift = bm_bc[y[i+j]] - m + j + 1 | + | '''int''' bc_shift = bm_bc[y[i + j]] - m + j + 1 |
shift = MAX(turbo_shift, bc_shift) | shift = MAX(turbo_shift, bc_shift) | ||
| − | shift = MAX(shift, bm_gs[j+1]) | + | shift = MAX(shift, bm_gs[j + 1]) |
| − | '''if''' (shift == bm_gs[j+1]) | + | '''if''' (shift == bm_gs[j + 1]) |
u = MIN((m - shift), v) | u = MIN((m - shift), v) | ||
'''else''' | '''else''' | ||
'''if''' (turbo_shift < bc_shift) | '''if''' (turbo_shift < bc_shift) | ||
| − | shift = MAX (shift, (u+1)) | + | shift = MAX(shift, (u + 1)) |
u = 0 | u = 0 | ||
i += shift | i += shift | ||
Версия 20:46, 3 апреля 2016
Алгоритм Бойера-Мура за линейное время(Турбо-алгоритм) является улучшением алгоритма Бойера-Мура. Алгоритм, разработанный группой учёных во главе с М.Крочемором предлагает другой подход к коротким алфавитам и заодно решает вторую проблему — квадратичную сложность в худшем случае.
Содержание
Алгоритм
Турбо-алгоритм Бойера-Мура не нуждается в дополнительном препроцессинге и требует только постоянную дополнительную память относительно оригинального алгоритма Бойера-Мура. Он состоит в запоминании сегмента текста, который соответствует суффикс шаблона во время последней попытки (и только тогда, когда сдвиг хорошего суффикса был выполнен). Эта методика представляет два преимущества:
- можно перепрыгнуть через этот сегмент;
- она может позволить выполнение 'турбо-сдвига'.
Турбо - сдвиг может произойти, если мы обнаружим, что суффикс образца, который сходится с текстом, короче, чем тот, который был запомнен ранее.
Пусть - запомненный сегмент, а - cуффикс, совпавший во время текущей попытки, такой что - суффикс . Тогда - суффикс , два символа и встречаются на расстоянии в тексте, и суффикс длины имеет период длины , а значит не может перекрыть оба появления символов и в тексте. Наименьший возможный сдвиг имеет длину ( его мы и называем турбо - сдвигом ).
Применение турбо-сдвига в случае
При , если сдвиг плохого символа больше, то совершаемый сдвиг будет больше либо равен . В этом случае символы и различны, так как мы предположили, что предыдущий сдвиг был сдвигом хорошего суффикса. Тогда сдвиг больший, чем турбо-сдвиг, но меньший совместит и с одним и тем же символом . Значит, если сдвиг плохого символа больше, то мы можем применить сдвиг больший, либо равный . Нельзя совместить символы с одним и тем же символом v.
Псевдокод
Стадия репроцессинга совпадает со стадией препроцессинга в алгоритме Бойера-Мура.
В сам алгоритм добавляется обработка турбо-сдвигов.
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)
OUTPUT(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)
shift = MAX(shift, bm_gs[j + 1])
if (shift == bm_gs[j + 1])
u = MIN((m - shift), v)
else
if (turbo_shift < bc_shift)
shift = MAX(shift, (u + 1))
u = 0
i += shift
Асимптотика
- Фаза препроцессинга требует времени и памяти, где — размер алфавита.
- Фаза поиска требует времени.
- В худшем случае поиск требует сравнений.
