Двусторонний алгоритм — различия между версиями
Heatwave (обсуждение | вклад) (→См. также) |
м (rollbackEdits.php mass rollback) |
||
(не показаны 24 промежуточные версии 8 участников) | |||
Строка 2: | Строка 2: | ||
==Характерные черты== | ==Характерные черты== | ||
− | * | + | * Требует упорядоченный алфавит, |
* этап предобработки занимает <math>O(m)</math> времени и константное количество памяти, | * этап предобработки занимает <math>O(m)</math> времени и константное количество памяти, | ||
− | * этап поиска за время <math>O(n)</math>, где m {{---}} длина образца, а n {{---}} длина текста. | + | * этап поиска за время <math>O(n)</math>, где <tex>m</tex> {{---}} длина образца, а <tex>n</tex> {{---}} длина текста. |
==Описание алгоритма== | ==Описание алгоритма== | ||
Строка 35: | Строка 35: | ||
==Псевдокод== | ==Псевдокод== | ||
− | '''function''' twoWaySearch(String pattern, String text): | + | '''function''' twoWaySearch('''String''' pattern, '''String''' text): '''vector<int>''' |
− | + | <font color=green>//предобработка <tex>-</tex> вычисление критической позиции (в которой строка делится на <tex>u</tex> и <tex>v</tex>)</font> | |
− | + | <tex>\langle</tex>l1, p1<tex>\rangle</tex> = maxSuffix(pattern, <tex>\leqslant</tex>) | |
− | <tex>\langle</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> | |
− | + | <font color=green>//<tex>p</tex> <tex>-</tex> период <tex>x</tex>, <tex>l</tex> <tex>-</tex> такая критическая позиция, что <tex>l<p</tex></font> | |
− | + | '''vector<int> ''' occurences <font color=green>// набор всех вхождений образца в текст</font> | |
− | + | '''int''' pos = 0 | |
− | + | '''int''' memPrefix = 0 | |
− | + | '''while''' pos + pattern.length <tex>\leqslant</tex> text.length | |
− | + | <font color=green>//первый этап: просмотр <tex>v</tex> слева направо</font> | |
− | + | '''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''' | |
− | + | <font color=green>//второй этап: просмотр <tex>u</tex> справа налево</font> | |
− | + | '''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 | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | '''while''' | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | ''' | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
'''return''' occurences | '''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 Краткое описание алгоритма, пример работы] | ||
[[Категория:Алгоритмы и структуры данных]] | [[Категория:Алгоритмы и структуры данных]] | ||
[[Категория:Поиск подстроки в строке]] | [[Категория:Поиск подстроки в строке]] | ||
[[Категория:Точный поиск]] | [[Категория:Точный поиск]] |
Текущая версия на 19:31, 4 сентября 2022
Двусторонний алгоритм (англ. Two Way algorithm) — алгоритм поиска подстроки в строке.
Характерные черты
- Требует упорядоченный алфавит,
- этап предобработки занимает времени и константное количество памяти,
- этап поиска за время , где — длина образца, а — длина текста.
Описание алгоритма
Строка
разбивается на две части и так, что . Затем фаза поиска в двустороннем алгоритме состоит в сравнении символов слева направо, и затем, если на первом этапе не происходит несовпадений, в сравнении символов справа налево (второй этап). Фаза предобработки, таким образом, заключается в поиске подходящего разбиения .Определение: |
— разбиение строки , если . |
Определение: |
Пусть
| — разбиение . Повторение в — слово такое, что для него выполнены следующие условия:
Определение: |
Длина повторения в | называется локальным периодом; наименьший локальный период записывается как . Каждое разбиение на имеет как минимум одно повторение. Очевидно, что
Определение: |
Разбиение | на такое, что называется критическим разбиением .
Если — критическое разбиение , то на позиции в общий и локальный периоды одинаковы. Двусторонний алгоритм находит критическое разбиение такое, что и длина минимальна.
Чтобы найти критическое разбиение мы сперва вычислим — максимальный суффикс в лексикографическом порядке, характерном для заданного алфавита и максимальный суффикс для обратного лексикографического порядка . Затем выбираются так, что .
Фаза поиска в двустороннем алгоритме состоит из сравнения символов
слева направо и символов справа налево. Когда происходит несовпадение при просмотре -го символа в , производится сдвиг длиной . Когда происходит несовпадение при просмотре или когда образец встретился в строке, производится сдвиг длиной . Такие действия приводят к квадратичной работе алгоритма в худшем случае, но этого можно избежать запоминанием префикса: когда производится сдвиг длиной , длина совпадающего префикса образца в начале "окна" (а именно ) после сдвига запоминается, чтобы не просматривать ее заново при следующем проходе.Псевдокод
function twoWaySearch(String pattern, String text): vector<int> //предобработкавычисление критической позиции (в которой строка делится на и ) l1, p1 = maxSuffix(pattern, ) l2, p2 = maxSuffix(pattern, ) l, p = l1 l2 ? l1, p1 : l2, p2 // период , такая критическая позиция, что vector<int> occurences // набор всех вхождений образца в текст int pos = 0 int memPrefix = 0 while pos + pattern.length text.length //первый этап: просмотр слева направо int i = max(l, memPrefix) + 1 while i pattern.length and pattern[i] = text[pos + i] i++ if i pattern.length pos = pos + max(i - l, memPrefix - p + 1) memPrefix = 0 else //второй этап: просмотр справа налево int j = l while j memPrefix and pattern[j] text[pos + j] j-- if j memPrefix occurences.pushBack(pos) pos = pos + p memPrefix = pattern.length - p return occurences
Ценность алгоритма
Двусторонний алгоритм отчасти похож на алгоритм Бойера-Мура (просмотр символов справа налево и сдвиг позиции при несовпадении на втором этапе), и в лучшем случае работает немногим медленнее его, а в худшем — значительно превосходит[1], но главное отличие двустороннего алгоритма от алгоритмов Кнута-Морриса-Пратта и Бойера-Мура — константное количество затрачиваемой дополнительной памяти.
Именно этот алгоритм (при выполнении ряда условий) используется в реализации поиска подстроки в glibc[2].