Турбо-алгоритм Бойера-Мура — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 5: Строка 5:
 
# можно перепрыгнуть через этот сегмент;
 
# можно перепрыгнуть через этот сегмент;
 
# она может позволить выполнение 'турбо-сдвига'.
 
# она может позволить выполнение 'турбо-сдвига'.
 +
Турбо - сдвиг может произойти, если мы обнаружим, что суффикс образца, который сходится с текстом, короче, чем тот, который был запомнен ранее.
 +
 +
Пусть <tex>u</tex> - запомненный сегмент, а <tex>v</tex> - cуффикс, совпавший во время текущей попытки, такой что <tex>uzv</tex> - суффикс <tex>x</tex>. Тогда <tex>av</tex> - суффикс <tex>x</tex>, два символа <tex>а</tex> и <tex>b</tex> встречаются на расстоянии p в тексте, и суффикс x длины |uzv| имеет период длины p, а значит не может перекрыть оба появления символов а и b в тексте. Наименьший возможный сдвиг имеет длину |u| - |v| ( его мы и называем турбо - сдвигом ).
 +
 
==Псевдокод==
 
==Псевдокод==
 
==Асимптотики==
 
==Асимптотики==

Версия 20:58, 31 марта 2016

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

Алгоритм

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

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

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

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

Псевдокод

Асимптотики

См. также

Ссылки