Двусторонний алгоритм — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 17: Строка 17:
 
Иными словами, <math>w</math> встречается по обе стороны границы между <math>u</math> и <math>v</math> и может "залезать" (overflow). Длина повторения в <math>(u, v)</math> называется '''локальным периодом'''; наименьший локальный период записывается как <math>r(u, v)</math>.
 
Иными словами, <math>w</math> встречается по обе стороны границы между <math>u</math> и <math>v</math> и может "залезать" (overflow). Длина повторения в <math>(u, v)</math> называется '''локальным периодом'''; наименьший локальный период записывается как <math>r(u, v)</math>.
  
Каждое разбиение <math>x</math> на <math>(u, v)</math> имеет как минимум одно повторение. Очевидно, что <math>1 \ge r(u, v) \ge |x|</math>
+
Каждое разбиение <math>x</math> на <math>(u, v)</math> имеет как минимум одно повторение. Очевидно, что <math>1 \leqslant r(u, v) \leqslant |x|</math>
 
Разбиение x на <math>(u, v)</math> такое, что <math>r(u, v) = per(x)</math> называется '''критическим разбиением''' <math>x</math>.
 
Разбиение x на <math>(u, v)</math> такое, что <math>r(u, v) = per(x)</math> называется '''критическим разбиением''' <math>x</math>.
 
}}
 
}}
  
 
Если <math>(u, v)</math> {{---}} критическое разбиение <math>x</math>, то на позиции <math>|u|</math> в <math>x</math> общий и локальный периоды одинаковы. Двусторонний алгоритм находит критическое разбиение <math>(x_l, x_r)</math> такое, что <math>|x_l| < per(x)</math> и длина <math>|x_l|</math> минимальна.
 
Если <math>(u, v)</math> {{---}} критическое разбиение <math>x</math>, то на позиции <math>|u|</math> в <math>x</math> общий и локальный периоды одинаковы. Двусторонний алгоритм находит критическое разбиение <math>(x_l, x_r)</math> такое, что <math>|x_l| < per(x)</math> и длина <math>|x_l|</math> минимальна.
Чтобы найти критическое разбиение <math>(x_l, x_r)</math> мы сперва вычислим <math>z</math> {{---}} максимальный суффикс <math>x</math> в порядке <math><=</math> и максимальный суффикс <math>z~</math> для обратного порядка <math><=~</math>. Затем <math>(x_l, x_r)</math> выбираются так, что <math>|x_l| = max{|z|, |z~|}</math>.
+
Чтобы найти критическое разбиение <math>(x_l, x_r)</math> мы сперва вычислим <math>z</math> {{---}} максимальный суффикс <math>x</math> в порядке <math>\leqslant</math> и максимальный суффикс <math>z~</math> для обратного порядка <math>\geqslant</math>. Затем <math>(x_l, x_r)</math> выбираются так, что <math>|x_l| = max{|z|, |z~|}</math>.
 
Фаза предобработки может быть выполнена за время O(m) и константное количество памяти.
 
Фаза предобработки может быть выполнена за время O(m) и константное количество памяти.
 
Фаза поиска в двустороннем алгоритме состоит из сравнения символов <math>x_r</math> слева направо и символов <math>x_l</math> справа налево. Когда происходит несовпадение при просмотре <math>k</math>-го символа в <math>x_r</math>, производится сдвиг длиной <math>k</math>. Когда происходит несовпадение при просмотре <math>x_l</math>, или когда образец встретился в строке, производится сдвиг длиной <math>per(x)</math>.
 
Фаза поиска в двустороннем алгоритме состоит из сравнения символов <math>x_r</math> слева направо и символов <math>x_l</math> справа налево. Когда происходит несовпадение при просмотре <math>k</math>-го символа в <math>x_r</math>, производится сдвиг длиной <math>k</math>. Когда происходит несовпадение при просмотре <math>x_l</math>, или когда образец встретился в строке, производится сдвиг длиной <math>per(x)</math>.

Версия 11:53, 10 июня 2015

Двусторонний алгоритм (англ. Two Way algorithm) — алгоритм поиска подстроки в строке.

Характерные черты

  • требует упорядоченный алфавит
  • этап предобработки занимает [math]O(m)[/math] времени и константное количество памяти
  • этап поиска за время [math]O(n)[/math]
  • в худшем случае производится [math]2n - m[/math] сравнений символов

Описание алгоритма

Образец [math]x[/math] разбивается на две части [math]x_l[/math] и [math]x_r[/math] так, что [math]x=[/math] [math]x_l[/math] [math]x_r[/math]. Затем фаза поиска в двустороннем алгоритме состоит в сравнении символов [math]x_r[/math] слева направо, и затем, если на этом первом этапе не происходит несовпадений, в сравнении символов [math]x_l[/math] справа налево (второй этап). Фаза предобработки, таким образом, заключается в поиске подходящего разбиения [math]x_l[/math] [math]x_r[/math].

Определение:
Пусть [math](u, v)[/math] — разбиение [math]x[/math]. Повторение в [math](u, v)[/math] — слово [math]w[/math] такое, что для него выполнены следующие условия:
  1. [math]w[/math] — суффикс [math]u[/math] или [math]u[/math] — суффикс [math]w[/math];
  2. [math]w[/math] — префикс [math]v[/math] или [math]v[/math] — префикс [math]w[/math].

Иными словами, [math]w[/math] встречается по обе стороны границы между [math]u[/math] и [math]v[/math] и может "залезать" (overflow). Длина повторения в [math](u, v)[/math] называется локальным периодом; наименьший локальный период записывается как [math]r(u, v)[/math].

Каждое разбиение [math]x[/math] на [math](u, v)[/math] имеет как минимум одно повторение. Очевидно, что [math]1 \leqslant r(u, v) \leqslant |x|[/math]

Разбиение x на [math](u, v)[/math] такое, что [math]r(u, v) = per(x)[/math] называется критическим разбиением [math]x[/math].


Если [math](u, v)[/math] — критическое разбиение [math]x[/math], то на позиции [math]|u|[/math] в [math]x[/math] общий и локальный периоды одинаковы. Двусторонний алгоритм находит критическое разбиение [math](x_l, x_r)[/math] такое, что [math]|x_l| \lt per(x)[/math] и длина [math]|x_l|[/math] минимальна. Чтобы найти критическое разбиение [math](x_l, x_r)[/math] мы сперва вычислим [math]z[/math] — максимальный суффикс [math]x[/math] в порядке [math]\leqslant[/math] и максимальный суффикс [math]z~[/math] для обратного порядка [math]\geqslant[/math]. Затем [math](x_l, x_r)[/math] выбираются так, что [math]|x_l| = max{|z|, |z~|}[/math]. Фаза предобработки может быть выполнена за время O(m) и константное количество памяти. Фаза поиска в двустороннем алгоритме состоит из сравнения символов [math]x_r[/math] слева направо и символов [math]x_l[/math] справа налево. Когда происходит несовпадение при просмотре [math]k[/math]-го символа в [math]x_r[/math], производится сдвиг длиной [math]k[/math]. Когда происходит несовпадение при просмотре [math]x_l[/math], или когда образец встретился в строке, производится сдвиг длиной [math]per(x)[/math]. Такие действия приводят к квадратичной работе алгоритма в худшем случае, но этого можно избежать запоминанием префикса: когда производится сдвиг длиной [math]per(x)[/math], длина совпадающего префикса образца в начале "окна" (а именно [math]m - per(x)[/math]) после сдвига запоминается, чтобы не просматривать ее заново при следующем проходе. Фаза поиска может быть выполнена за время [math]O(n)[/math]. Двусторонний алгоритм производит [math]2n - m[/math] сравнений символов в худшем случае; вариация этого алгоритма от Бреслауэра (Breslauer) выполняет менее [math]2n - m[/math] сравнений и использует константное количество памяти.

Псевдокод