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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Менее адский псевдокод, комментарии)
Строка 50: Строка 50:
 
     memPrefix <tex>\leftarrow</tex> 0
 
     memPrefix <tex>\leftarrow</tex> 0
 
     '''while''' pos + pattern.length <tex>\leqslant</tex> text.length
 
     '''while''' pos + pattern.length <tex>\leqslant</tex> text.length
     <font color=green>//первая фаза: просмотр <tex>v</tex> слева направо</font>
+
     <font color=green>//первый этап: просмотр <tex>v</tex> слева направо</font>
 
         i <tex>\leftarrow \max</tex>(l, memPrefix) + 1
 
         i <tex>\leftarrow \max</tex>(l, memPrefix) + 1
 
         '''while''' i <tex>\leqslant</tex> pattern.length '''and''' pattern[i] <tex>=</tex> text[pos + i]
 
         '''while''' i <tex>\leqslant</tex> pattern.length '''and''' pattern[i] <tex>=</tex> text[pos + i]
Строка 58: Строка 58:
 
             memPrefix <tex>\leftarrow</tex> 0
 
             memPrefix <tex>\leftarrow</tex> 0
 
         '''else'''
 
         '''else'''
             <font color=green>//вторая фаза: просмотр <tex>u</tex> справа налево</font>
+
             <font color=green>//второй этап: просмотр <tex>u</tex> справа налево</font>
 
             j <tex>\leftarrow</tex> l
 
             j <tex>\leftarrow</tex> l
 
             '''while''' j <tex> > </tex> memPrefix '''and''' pattern[j] <tex>=</tex> text[pos + j]
 
             '''while''' j <tex> > </tex> memPrefix '''and''' pattern[j] <tex>=</tex> text[pos + j]
Строка 67: Строка 67:
 
             memPrefix <tex>\leftarrow</tex> pattern.length <tex>-</tex> p
 
             memPrefix <tex>\leftarrow</tex> pattern.length <tex>-</tex> p
 
     '''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>, но главное отличие двустороннего алгоритма от алгоритмов Кнута-Морриса-Пратта и Бойера-Мура {{---}} константное количество затрачиваемой дополнительной памяти.
  
 
== Источники информации ==
 
== Источники информации ==
 
* [http://monge.univ-mlv.fr/~mac/Articles-PDF/CP-1991-jacm.pdf  Оригинал статьи (M. Crochemore, D. Perrin)]
 
* [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  Краткое описание алгоритма, пример работы]
 
* [http://www-igm.univ-mlv.fr/~lecroq/string/node26.html#SECTION00260  Краткое описание алгоритма, пример работы]
 +
 +
== Примечания ==
 +
<references/>
  
 
== См. также ==
 
== См. также ==

Версия 01:37, 16 июня 2015

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

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

  • требует упорядоченный алфавит,
  • этап предобработки занимает [math]O(m)[/math] времени и константное количество памяти,
  • этап поиска за время [math]O(n)[/math], где m — длина образца, а n — длина текста.

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

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

Определение:
[math](u, v)[/math]разбиение строки [math]x[/math], если [math]x = uv[/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](u, v)[/math] называется локальным периодом; наименьший локальный период записывается как [math]r(u, v)[/math]. Каждое разбиение [math]x[/math] на [math](u, v)[/math] имеет как минимум одно повторение. Очевидно, что [math]1 \leqslant r(u, v) \leqslant |x|[/math]


Определение:
Разбиение [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| \lt 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):
    //предобработка [math]-[/math] вычисление критической позиции (в которой строка делится на [math]u[/math] и [math]v[/math])
    [math]\langle[/math]l1, p1[math]\rangle[/math] [math]\leftarrow[/math] maxSuffix(pattern, [math]\leqslant[/math])
    [math]\langle[/math]l2, p2[math]\rangle[/math] [math]\leftarrow[/math] maxSuffix(pattern, [math]\geqslant[/math])
    if l1 [math]\geqslant[/math] l2
        l = l1
        p = p1
    else
        len = l2
        p = p2
    //[math]p[/math] [math]-[/math] период [math]x[/math], [math]l[/math] [math]-[/math] такая критическая позиция, что [math]l\lt p[/math]
    occurences = [math]\varnothing[/math]
    pos [math]\leftarrow[/math] 0
    memPrefix [math]\leftarrow[/math] 0
    while pos + pattern.length [math]\leqslant[/math] text.length
    //первый этап: просмотр [math]v[/math] слева направо
        i [math]\leftarrow \max[/math](l, memPrefix) + 1
        while i [math]\leqslant[/math] pattern.length and pattern[i] [math]=[/math] text[pos + i]
            i++
        if i [math]\leqslant[/math] pattern.length
            pos [math]\leftarrow[/math] pos + [math]\max[/math](i [math]-[/math] l, memPrefix [math]-[/math] p [math]+[/math] 1)
            memPrefix [math]\leftarrow[/math] 0
        else
            //второй этап: просмотр [math]u[/math] справа налево
            j [math]\leftarrow[/math] l
            while j [math] \gt  [/math] memPrefix and pattern[j] [math]=[/math] text[pos + j]
                j--
            if j [math]\leqslant[/math] memPrefix
                pos [math]\rightarrow[/math] occurences
            pos [math]\leftarrow[/math] pos [math]+[/math] p
            memPrefix [math]\leftarrow[/math] pattern.length [math]-[/math] p
    return occurences

Ценность алгоритма

Двусторонний алгоритм отчасти похож на алгоритм Бойера-Мура (просмотр символов справа налево и сдвиг позиции при несовпадении на втором этапе), и в лучшем случае работает немногим медленнее его, а в худшем — значительно превосходит[1], но главное отличие двустороннего алгоритма от алгоритмов Кнута-Морриса-Пратта и Бойера-Мура — константное количество затрачиваемой дополнительной памяти.

Источники информации

Примечания

См. также