Турбо-алгоритм Бойера-Мура

Алгоритм Бойера-Мура за линейное время(Турбо-алгоритм) является улучшением алгоритма Бойера-Мура. Алгоритм, разработанный группой учёных во главе с М.Крочемором предлагает другой подход к коротким алфавитам и заодно решает вторую проблему — квадратичную сложность в худшем случае.

Алгоритм

Турбо-алгоритм Бойера-Мура не нуждается в дополнительном препроцессинге и требует только постоянную дополнительную память относительно оригинального алгоритма Бойера-Мура. Он состоит в запоминании сегмента текста, который соответствует суффикс шаблона во время последней попытки (и только тогда, когда сдвиг хорошего суффикса был выполнен). Эта методика представляет два преимущества:

1. можно перепрыгнуть через этот сегмент;
2. она может позволить выполнение 'турбо-сдвига'.

Турбо - сдвиг может произойти, если мы обнаружим, что суффикс образца, который сходится с текстом, короче, чем тот, который был запомнен ранее.

Пусть [math]u[/math] - запомненный сегмент, а [math]v[/math] - cуффикс, совпавший во время текущей попытки, такой что [math]uzv[/math] - суффикс [math]x[/math]. Тогда [math]av[/math] - суффикс [math]x[/math], два символа [math]a[/math] и [math]b[/math] встречаются на расстоянии [math]p[/math] в тексте, и суффикс [math]x[/math] длины [math]|uzv|[/math] имеет период длины [math]p[/math], а значит не может перекрыть оба появления символов [math]a[/math] и [math]b[/math] в тексте. Наименьший возможный сдвиг имеет длину [math]|u| - |v|[/math] ( его мы и называем турбо - сдвигом ).

Применение турбо-сдвига в случае [math]|v| \lt |u|[/math]

При [math]|v| \lt |u|[/math], если сдвиг плохого символа больше, то совершаемый сдвиг будет больше либо равен [math]|u| - 1[/math]. В этом случае символы [math]c[/math] и [math]d[/math] различны, так как мы предположили, что предыдущий сдвиг был сдвигом хорошего суффикса. Тогда сдвиг больший, чем турбо-сдвиг, но меньший [math]|u| + 1[/math] совместит [math]c[/math] и [math]d[/math] с одним и тем же символом [math]v[/math]. Значит, если сдвиг плохого символа больше, то мы можем применить сдвиг больший, либо равный [math]|u| + 1[/math]. Нельзя совместить символы [math]c \neq d[/math] с одним и тем же символом v.

См. также

• Алгоритм Бойера-Мура
• Алгоритм Райта
• Алгоритм Кнута-Морриса-Пратта
• Алгоритм Апостолико-Крочемора

Ссылки

• Википедия — Алгоритм Бойера-Мура
• Wikipedia — Boyer–Moore string search algorithm
• Turbo Boyer-Moore algorithm
• Турбо Боуер-Мур