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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Псевдокод)
м (rollbackEdits.php mass rollback)
 
(не показаны 34 промежуточные версии 8 участников)
Строка 1: Строка 1:
'''Двусторонний алгоритм''' (англ. ''Two Way algorithm'') — алгоритм [[Наивный алгоритм поиска подстроки в строке#Постановка задачи|поиска подстроки в строке]].
+
'''Двусторонний алгоритм''' (англ. ''Two Way algorithm'') — алгоритм [[Поиск подстроки в строке|поиска подстроки в строке]].
  
 
==Характерные черты==
 
==Характерные черты==
* требует упорядоченный алфавит
+
* Требует упорядоченный алфавит,
* этап предобработки занимает <math>O(m)</math> времени и константное количество памяти
+
* этап предобработки занимает <math>O(m)</math> времени и константное количество памяти,
* этап поиска за время <math>O(n)</math>
+
* этап поиска за время <math>O(n)</math>, где <tex>m</tex> {{---}} длина образца, а <tex>n</tex> {{---}} длина текста.
* в худшем случае производится <math>2n - m</math> сравнений символов
 
  
 
==Описание алгоритма==
 
==Описание алгоритма==
Строка <tex>x</tex> разбивается на две части <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> справа налево (второй этап).
+
Строка <tex>x</tex> разбивается на две части <math>u</math> и <math>v</math> так, что <math>x = uv</math>. Затем фаза поиска в двустороннем алгоритме состоит в сравнении символов <math>v</math> слева направо, и затем, если на первом этапе не происходит несовпадений, в сравнении символов <math>u</math> справа налево (второй этап).
Фаза предобработки, таким образом, заключается в поиске подходящего разбиения <math>x_l</math> <math>x_r</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> такое, что для него выполнены следующие условия:
 
|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>u</math> или <math>u</math> {{---}} суффикс <math>w</math>.
# <math>w</math> {{---}} префикс <math>v</math> или <math>v</math> {{---}} префикс <math>w</math>.
+
# <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>.
+
{{Определение
 +
|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>
+
Каждое разбиение <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>.
+
 
 +
{{Определение
 +
|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>(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>(u, v)</math> такое, что <math>|u| < per(x)</math> и длина <math>|u|</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>.
+
Чтобы найти критическое разбиение <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>.
Фаза предобработки может быть выполнена за время 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>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>) после сдвига запоминается, чтобы не просматривать ее заново при следующем проходе.
 
Такие действия приводят к квадратичной работе алгоритма в худшем случае, но этого можно избежать запоминанием префикса: когда производится сдвиг длиной <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):
+
  '''function''' twoWaySearch('''String''' pattern, '''String''' text): '''vector<int>'''
     n = pattern.length
+
     <font color=green>//предобработка <tex>-</tex> вычисление критической позиции (в которой строка делится на <tex>u</tex> и <tex>v</tex>)</font>
    <tex>\langle</tex>len1, p1<tex>\rangle</tex> <tex>\leftarrow</tex> maxSuffix(pattern, <tex>\leqslant</tex>)
+
     <tex>\langle</tex>l1, p1<tex>\rangle</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>l2, p2<tex>\rangle</tex> = maxSuffix(pattern, <tex>\geqslant</tex>)
     '''if''' len1 <tex>\geqslant</tex> len2:
+
     <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>
        len = len1
+
    <font color=green>//<tex>p</tex> <tex>-</tex> период <tex>x</tex>, <tex>l</tex> <tex>-</tex> такая критическая позиция, что <tex>l<p</tex></font>
        p = p1
+
    '''vector<int> ''' occurences  <font color=green>// набор всех вхождений образца в текст</font>
    '''else''':
+
    '''int''' pos = 0
        len = len2
+
    '''int''' memPrefix = 0
        p = p2
+
    '''while''' pos + pattern.length <tex>\leqslant</tex> text.length
    occurences = <tex>\varnothing</tex>
+
    <font color=green>//первый этап: просмотр <tex>v</tex> слева направо</font>
    pos <tex>\leftarrow</tex> 0
+
        '''int''' i = max(l, memPrefix) + 1
     memPrefix <tex>\leftarrow</tex> 0
+
         '''while''' i <tex>\leqslant</tex> pattern.length '''and''' pattern[i] = text[pos + i]
    '''if''' len < n/2 '''and''' pattern[1<tex>\ldots</tex>len] <tex>-</tex> суффикс pattern[len + 1<tex>\ldots</tex>len + p]:
+
            i++
        '''while''' pos + n <tex>\leqslant</tex> text.length:
+
        '''if''' i <tex>\leqslant</tex> pattern.length
            i <tex>\leftarrow \max</tex>(l, memPrefix) + 1
+
            pos = pos + max(i - l, memPrefix - p + 1)
            '''while''' i <tex>\leqslant</tex> n '''and''' pattern[i] <tex>=</tex> text[pos + i]:
+
            memPrefix = 0
                i++
+
        '''else'''
            '''if''' i <tex>\leqslant</tex> n:
+
            <font color=green>//второй этап: просмотр <tex>u</tex> справа налево</font>
                pos <tex>\leftarrow</tex> pos + <tex>\max</tex>(i <tex>-</tex> len, memPrefix <tex>-</tex> p <tex>+</tex> 1)
+
             '''int''' j = l
                memPrefix <tex>\leftarrow</tex> 0
+
            '''while''' j <tex> > </tex> memPrefix '''and''' pattern[j] <tex>=</tex> text[pos + j]
            '''else''':
+
                j--
                j <tex>\leftarrow</tex> l
+
            '''if''' j <tex>\leqslant</tex> memPrefix
                '''while''' j <tex> > </tex> memPrefix '''and''' pattern[j] <tex>=</tex> text[pos + j]:
+
                occurences.pushBack(pos
                    j--
+
            pos = pos + p
                '''if''' j <tex>\leqslant</tex> memPrefix:
+
            memPrefix = pattern.length - p
                    pos <tex>\rightarrow</tex> occurences
 
                pos <tex>\leftarrow</tex> pos <tex>+</tex> p
 
                memPrefix <tex>\leftarrow</tex> n <tex>-</tex> p
 
    '''else''':
 
        q <tex>\leftarrow \max</tex>(len, n <tex>-</tex> len) <tex>+</tex> 1
 
         '''while''' pos + n <tex>\leqslant</tex> text.length:
 
            i <tex>\leftarrow</tex> len + 1
 
            '''while''' i <tex>\leqslant</tex> n '''and''' pattern[i] <tex>=</tex> text[pos <tex>+</tex> i]:
 
                i++
 
            '''if''' i <tex>\leqslant</tex> n:
 
                pos <tex>\leftarrow</tex> pos <tex>+</tex> i <tex>-</tex> len
 
             '''else''':
 
                j <tex>\leftarrow</tex> len
 
                '''while''' j <tex> > </tex> 0 '''and''' pattern[j] <tex>=</tex> text[pos <tex>+</tex> j]:
 
                    j--
 
                '''if''' j <tex>=</tex> 0:
 
                    pos <tex>\rightarrow</tex> occurences
 
                pos <tex>\leftarrow</tex> pos <tex>+</tex> q
 
 
     '''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) — алгоритм поиска подстроки в строке.

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

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

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

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

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

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

Именно этот алгоритм (при выполнении ряда условий) используется в реализации поиска подстроки в glibc[2].

См. также

Примечания

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