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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Описание алгоритма)
м (Псевдокод)
Строка 35: Строка 35:
 
     <tex>\langle</tex>len1, p1<tex>\rangle</tex> <tex>\leftarrow</tex> maxSuffix(pattern, <tex>\leqslant</tex>)
 
     <tex>\langle</tex>len1, p1<tex>\rangle</tex> <tex>\leftarrow</tex> maxSuffix(pattern, <tex>\leqslant</tex>)
 
     <tex>\langle</tex>len2, p2<tex>\rangle</tex> <tex>\leftarrow</tex> maxSuffix(pattern, <tex>\geqslant</tex>)
 
     <tex>\langle</tex>len2, p2<tex>\rangle</tex> <tex>\leftarrow</tex> maxSuffix(pattern, <tex>\geqslant</tex>)
     '''if''' len1 <tex>\geqslant</tex> len2:
+
     '''if''' len1 <tex>\geqslant</tex> len2
 
         len = len1
 
         len = len1
 
         p = p1
 
         p = p1
     '''else''':
+
     '''else'''
 
         len = len2
 
         len = len2
 
         p = p2
 
         p = p2
Строка 44: Строка 44:
 
     pos <tex>\leftarrow</tex> 0
 
     pos <tex>\leftarrow</tex> 0
 
     memPrefix <tex>\leftarrow</tex> 0
 
     memPrefix <tex>\leftarrow</tex> 0
     '''if''' len < n/2 '''and''' pattern[1<tex>\ldots</tex>len] <tex>-</tex> суффикс pattern[len + 1<tex>\ldots</tex>len + p]:
+
     '''if''' len < n/2 '''and''' pattern[1<tex>\ldots</tex>len] <tex>-</tex> суффикс pattern[len + 1<tex>\ldots</tex>len + p]
         '''while''' pos + n <tex>\leqslant</tex> text.length:
+
         '''while''' pos + n <tex>\leqslant</tex> text.length
 
             i <tex>\leftarrow \max</tex>(l, memPrefix) + 1
 
             i <tex>\leftarrow \max</tex>(l, memPrefix) + 1
             '''while''' i <tex>\leqslant</tex> n '''and''' pattern[i] <tex>=</tex> text[pos + i]:
+
             '''while''' i <tex>\leqslant</tex> n '''and''' pattern[i] <tex>=</tex> text[pos + i]
 
                 i++
 
                 i++
             '''if''' i <tex>\leqslant</tex> n:
+
             '''if''' i <tex>\leqslant</tex> n
 
                 pos <tex>\leftarrow</tex> pos + <tex>\max</tex>(i <tex>-</tex> len, memPrefix <tex>-</tex> p <tex>+</tex> 1)
 
                 pos <tex>\leftarrow</tex> pos + <tex>\max</tex>(i <tex>-</tex> len, memPrefix <tex>-</tex> p <tex>+</tex> 1)
 
                 memPrefix <tex>\leftarrow</tex> 0
 
                 memPrefix <tex>\leftarrow</tex> 0
             '''else''':
+
             '''else'''
 
                 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]
 
                     j--
 
                     j--
                 '''if''' j <tex>\leqslant</tex> memPrefix:
+
                 '''if''' j <tex>\leqslant</tex> memPrefix
 
                     pos <tex>\rightarrow</tex> occurences
 
                     pos <tex>\rightarrow</tex> occurences
 
                 pos <tex>\leftarrow</tex> pos <tex>+</tex> p
 
                 pos <tex>\leftarrow</tex> pos <tex>+</tex> p
 
                 memPrefix <tex>\leftarrow</tex> n <tex>-</tex> p
 
                 memPrefix <tex>\leftarrow</tex> n <tex>-</tex> p
     '''else''':
+
     '''else'''
 
         q <tex>\leftarrow \max</tex>(len, n <tex>-</tex> len) <tex>+</tex> 1
 
         q <tex>\leftarrow \max</tex>(len, n <tex>-</tex> len) <tex>+</tex> 1
         '''while''' pos + n <tex>\leqslant</tex> text.length:
+
         '''while''' pos + n <tex>\leqslant</tex> text.length
 
             i <tex>\leftarrow</tex> len + 1
 
             i <tex>\leftarrow</tex> len + 1
             '''while''' i <tex>\leqslant</tex> n '''and''' pattern[i] <tex>=</tex> text[pos <tex>+</tex> i]:
+
             '''while''' i <tex>\leqslant</tex> n '''and''' pattern[i] <tex>=</tex> text[pos <tex>+</tex> i]
 
                 i++
 
                 i++
             '''if''' i <tex>\leqslant</tex> n:
+
             '''if''' i <tex>\leqslant</tex> n
 
                 pos <tex>\leftarrow</tex> pos <tex>+</tex> i <tex>-</tex> len
 
                 pos <tex>\leftarrow</tex> pos <tex>+</tex> i <tex>-</tex> len
             '''else''':
+
             '''else'''
 
                 j <tex>\leftarrow</tex> len
 
                 j <tex>\leftarrow</tex> len
                 '''while''' j <tex> > </tex> 0 '''and''' pattern[j] <tex>=</tex> text[pos <tex>+</tex> j]:
+
                 '''while''' j <tex> > </tex> 0 '''and''' pattern[j] <tex>=</tex> text[pos <tex>+</tex> j]
 
                     j--
 
                     j--
 
                 '''if''' j <tex>=</tex> 0:
 
                 '''if''' j <tex>=</tex> 0:

Версия 14:14, 14 июня 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]

Разбиение [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](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]\widetilde{z}[/math] для обратного порядка [math]\geqslant[/math]. Затем [math](x_l, x_r)[/math] выбираются так, что [math]|x_l| = \max(|z|, |\widetilde{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] сравнений и использует константное количество памяти.

Псевдокод

function twoWaySearch(String pattern, String text):
    n = pattern.length
    [math]\langle[/math]len1, p1[math]\rangle[/math] [math]\leftarrow[/math] maxSuffix(pattern, [math]\leqslant[/math])
    [math]\langle[/math]len2, p2[math]\rangle[/math] [math]\leftarrow[/math] maxSuffix(pattern, [math]\geqslant[/math])
    if len1 [math]\geqslant[/math] len2
        len = len1
        p = p1
    else
        len = len2
        p = p2
    occurences = [math]\varnothing[/math]
    pos [math]\leftarrow[/math] 0
    memPrefix [math]\leftarrow[/math] 0
    if len < n/2 and pattern[1[math]\ldots[/math]len] [math]-[/math] суффикс pattern[len + 1[math]\ldots[/math]len + p]
        while pos + n [math]\leqslant[/math] text.length
            i [math]\leftarrow \max[/math](l, memPrefix) + 1
            while i [math]\leqslant[/math] n and pattern[i] [math]=[/math] text[pos + i]
                i++
            if i [math]\leqslant[/math] n
                pos [math]\leftarrow[/math] pos + [math]\max[/math](i [math]-[/math] len, memPrefix [math]-[/math] p [math]+[/math] 1)
                memPrefix [math]\leftarrow[/math] 0
            else
                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] n [math]-[/math] p
    else
        q [math]\leftarrow \max[/math](len, n [math]-[/math] len) [math]+[/math] 1
        while pos + n [math]\leqslant[/math] text.length
            i [math]\leftarrow[/math] len + 1
            while i [math]\leqslant[/math] n and pattern[i] [math]=[/math] text[pos [math]+[/math] i]
                i++
            if i [math]\leqslant[/math] n
                pos [math]\leftarrow[/math] pos [math]+[/math] i [math]-[/math] len
            else
                j [math]\leftarrow[/math] len
                while j [math] \gt  [/math] 0 and pattern[j] [math]=[/math] text[pos [math]+[/math] j]
                    j--
                if j [math]=[/math] 0:
                    pos [math]\rightarrow[/math] occurences
                pos [math]\leftarrow[/math] pos [math]+[/math] q
    return occurences

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