Двусторонний алгоритм

2019-05-13T21:07:58Z

94.25.228.79: /* Ценность алгоритма */

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

==Характерные черты==
* Требует упорядоченный алфавит,
* этап предобработки занимает <math>O(m)</math> времени и константное количество памяти,
* этап поиска за время <math>O(n)</math>, где <tex>m</tex> {{---}} длина образца, а <tex>n</tex> {{---}} длина текста.

==Описание алгоритма==
Строка <tex>x</tex> разбивается на две части <math>u</math> и <math>v</math> так, что <math>x = uv</math>. Затем фаза поиска в двустороннем алгоритме состоит в сравнении символов <math>v</math> слева направо, и затем, если на первом этапе не происходит несовпадений, в сравнении символов <math>u</math> справа налево (второй этап).
Фаза предобработки, таким образом, заключается в поиске подходящего разбиения <tex>(u, v)</tex>.
{{Определение
|definition = <tex>(u, v)</tex> {{---}} '''разбиение''' строки <tex>x</tex>, если <tex>x = uv</tex>.
}}

{{Определение
|definition = Пусть <math>(u, v)</math> {{---}} разбиение <math>x</math>. '''Повторение''' в <math>(u, v)</math> {{---}} слово <math>w</math> такое, что для него выполнены следующие условия:
# <math>w</math> {{---}} суффикс <math>u</math> или <math>u</math> {{---}} суффикс <math>w</math>.
# <math>w</math> {{---}} префикс <math>v</math> или <math>v</math> {{---}} префикс <math>w</math>.}}

{{Определение
|definition = Длина повторения в <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>}}

{{Определение
|definition = Разбиение <math>x</math> на <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>(u, v)</math> такое, что <math>|u| < per(x)</math> и длина <math>|u|</math> минимальна.
Чтобы найти критическое разбиение <math>(u, v)</math> мы сперва вычислим <math>z</math> {{---}} максимальный суффикс <math>x</math> в лексикографическом порядке, характерном для заданного алфавита <math>\leqslant</math> и максимальный суффикс <math>\widetilde{z}</math> для обратного лексикографического порядка <math>\geqslant</math>. Затем <math>(u, v)</math> выбираются так, что <math>|u| = \max(|z|, |\widetilde{z}|)</math>.

Фаза поиска в двустороннем алгоритме состоит из сравнения символов <math>v</math> слева направо и символов <math>u</math> справа налево. Когда происходит несовпадение при просмотре <math>k</math>-го символа в <math>v</math>, производится сдвиг длиной <math>k</math>. Когда происходит несовпадение при просмотре <math>u</math> или когда образец встретился в строке, производится сдвиг длиной <math>per(x)</math>.
Такие действия приводят к квадратичной работе алгоритма в худшем случае, но этого можно избежать запоминанием префикса: когда производится сдвиг длиной <math>per(x)</math>, длина совпадающего префикса образца в начале "окна" (а именно <math>m - per(x)</math>) после сдвига запоминается, чтобы не просматривать ее заново при следующем проходе.

==Псевдокод==

'''function''' twoWaySearch('''String''' pattern, '''String''' text): '''vector<int>'''
//предобработка <tex>-</tex> вычисление критической позиции (в которой строка делится на <tex>u</tex> и <tex>v</tex>)
<tex>\langle</tex>l1, p1<tex>\rangle</tex> = maxSuffix(pattern, <tex>\leqslant</tex>)
<tex>\langle</tex>l2, p2<tex>\rangle</tex> = maxSuffix(pattern, <tex>\geqslant</tex>)
<tex>\langle</tex>l, p<tex>\rangle</tex> = l1 <tex>\geqslant</tex> l2 ? <tex>\langle</tex>l1, p1<tex>\rangle</tex> : <tex>\langle</tex>l2, p2<tex>\rangle</tex>
//<tex>p</tex> <tex>-</tex> период <tex>x</tex>, <tex>l</tex> <tex>-</tex> такая критическая позиция, что <tex>l<p</tex>
'''vector<int> ''' occurences // набор всех вхождений образца в текст
'''int''' pos = 0
'''int''' memPrefix = 0
'''while''' pos + pattern.length <tex>\leqslant</tex> text.length
//первый этап: просмотр <tex>v</tex> слева направо
'''int''' i = max(l, memPrefix) + 1
'''while''' i <tex>\leqslant</tex> pattern.length '''and''' pattern[i] = text[pos + i]
i++
'''if''' i <tex>\leqslant</tex> pattern.length
pos = pos + max(i - l, memPrefix - p + 1)
memPrefix = 0
'''else'''
//второй этап: просмотр <tex>u</tex> справа налево
'''int''' j = l
'''while''' j <tex> > </tex> memPrefix '''and''' pattern[j] <tex>=</tex> text[pos + j]
j--
'''if''' j <tex>\leqslant</tex> memPrefix
occurences.pushBack(pos)
pos = pos + p
memPrefix = pattern.length - p
'''return''' occurences

== Ценность алгоритма ==
Двусторонний алгоритм отчасти похож на алгоритм Бойера-Мура (просмотр символов справа налево и сдвиг позиции при несовпадении на втором этапе), и в лучшем случае работает немногим медленнее его, а в худшем {{---}} значительно превосходит<ref>[http://monge.univ-mlv.fr/~mac/Articles-PDF/CP-1991-jacm.pdf Journal of the Association for Computing Machinery, Vol. 38, No, 1, July 1991] Оценки скорости работы</ref>, но главное отличие двустороннего алгоритма от алгоритмов Кнута-Морриса-Пратта и Бойера-Мура {{---}} константное количество затрачиваемой дополнительной памяти.

Именно этот алгоритм (при выполнении ряда условий) используется в реализации поиска подстроки в glibc<ref>[https://github.com/bminor/glibc/blob/glibc-2.28/string/strstr.c#L88 Реализация функции strstr в glibc]</ref>.

== См. также ==
* [[Алгоритм Кнута-Морриса-Пратта ]]
* [[Алгоритм Бойера-Мура]]

== Примечания ==
<references/>

== Источники информации ==
* [http://monge.univ-mlv.fr/~mac/Articles-PDF/CP-1991-jacm.pdf Оригинал статьи (M. Crochemore, D. Perrin)]
* [http://www-igm.univ-mlv.fr/~lecroq/string/node26.html#SECTION00260 Краткое описание алгоритма, пример работы]

[[Категория:Алгоритмы и структуры данных]]
[[Категория:Поиск подстроки в строке]]
[[Категория:Точный поиск]]

Викиконспекты - Вклад участника [ru]

Двусторонний алгоритм