Алгоритм Апостолико-Крочемора — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 48 промежуточных версий 4 участников)
Строка 1: Строка 1:
'''Алгоритм Апостолико-Крочемора''' (англ. ''Apostolico-Crochemore algorithm'') - вариация [[Алгоритм Бойера-Мура|Алгоритма Бойера-Мура]].
+
'''Алгоритм Апостолико Крочемора''' (англ. ''Apostolico Crochemore algorithm'') — алгоритм [[Поиск подстроки в строке|поиска подстроки в строке]].
  
==Характерные черты==
+
==Описание алгоритма==
* этап предобработки занимает <math>O(m)</math> времени и константное количество памяти,
+
 
* этап поиска занимает <math>O(n)</math> времени,
+
Нам даны: <tex>y</tex> {{---}} текст, <tex>x</tex> {{---}} образец, <tex>m = |x|</tex>, <tex>n = |y|</tex>.
* выполняет <tex>\frac{3}{2} n</tex> сравнений в худшем случае.
+
 
 +
Для начала рассмотрим ситуацию, когда мы сравниваем наш образец с <tex>y[j \ldots j + m - 1]</tex>. Предположим, что <tex>x[i] \neq y[i + j]</tex> при <tex>0 < i < m</tex>. Тогда <tex>x[0 \ldots i - 1] = y[j \ldots i + j - 1] = u</tex> и <tex>a = x[i] \neq y[i + j] = b</tex>.
 +
Когда сдвиг возможен, разумно ожидать, что префикс <tex>v</tex> шаблона совпадет c некоторым суффиксом <tex>u</tex>. Более того, если мы хотим избежать несовпадения при сдвиге, то нужно, чтобы символ, следующий за префиксом <tex>v</tex> в шаблоне, не совпадал с <tex>a</tex>. Такой наибольший префикс <tex>v</tex> называется '''помеченным бордером''' строки <tex>u</tex>.
 +
 
 +
{{Определение
 +
|id=tagged border
 +
|definition='''Помеченный бордер''' (англ. ''tagged border'') строки <tex>\beta</tex> {{---}} строка <tex>\alpha : \forall i = 1 \ldots n - 1, \alpha[i] = \beta[i + (m - n)], \alpha[n] \neq \beta[m], n = |\alpha|, m = |\beta|</tex>.
 +
}}
 +
 
 +
Введем обозначение: пусть <tex>t[i]</tex> {{---}} длина наибольшего бордера для <tex>x[0 .. i - 1]</tex> за которым следует символ <tex>c \neq x[i]</tex> и <tex>-1</tex> если нет такого помеченного бордера, где <tex>0 < i \leqslant m</tex> (<tex>t[0] = -1</tex>). Затем, после сдвига, сравнение можно продолжить между символами <tex>x[t[i]]</tex> и <tex>y[i + j]</tex> не потеряв  никакого вхождения <tex>x</tex> в <tex>y</tex> и избежав отступа по тексту (смотри рисунок ниже).
 +
 
 +
 
 +
[[Файл:Apostolico-Crochemore-Shifts.png]]
 +
 
 +
Примечание: <tex>v</tex> {{---}} помеченный бордер строки <tex>u</tex>.
 +
 
 +
 
 +
Пусть теперь <tex>l = 0</tex>, если <tex>x = c ^ m</tex> и <tex>c \in \Sigma</tex>, иначе <tex>l</tex> равно позиции первого элемента, который не равен <tex>x[0]</tex> (<tex>x = a ^ l bu</tex>, где <tex>a \in \Sigma</tex>, <tex>b \in \Sigma</tex>, <tex>a \neq b</tex>, <tex>u \in \Sigma^*</tex>). При каждой подстановке шаблона к тексту к позиции <tex>i</tex> мы проводим следующие сравнения: <tex>x[l] = y[i + l], x[l + 1] = y[i + l + 1], \ldots , x[m - 2] = y[i + m - 2], x[m - 1] = y[i + m - 1],</tex><tex> x[0] = y[i], x[1] = y [i + 1], \ldots , x[l - 1] = y[i + l - 1]</tex>.
 +
 
 +
 
 +
Во время поиска вхождений мы рассматриваем данную тройку <tex>(i, j, k)</tex> где:
 +
* шаблон сравнивается с <tex>y[j, \ldots , j + m - 1]</tex>
 +
* <tex>0 \leqslant k \leqslant l</tex> и <tex>x[0, \ldots, k - 1] = y[j, \ldots , j + k - 1]</tex>
 +
* <tex>l \leqslant i < m</tex> и <tex>x[l, \ldots, i - 1] = y[j + l, \ldots , i + j - 1]</tex>
 +
(см. рисунок ниже)
 +
 
 +
Вначале инициализируем эту тройку <tex>(l, 0, 0)</tex>.
 +
Теперь опишем, как по уже вычисленной тройке <tex>(i, j, k)</tex> перейти к следующей.
 +
Возможны три случая в зависимости от значения <tex>i</tex>:
 +
 
 +
# <tex>i = l</tex>:
 +
#: Если <tex>x[i] = y[i + j]</tex>, тогда следующая тройка <tex>(i + 1, j, k)</tex>.
 +
#: Если <tex>x[i] \neq y[i + j]</tex>, тогда следующая тройка <tex>(l, j + 1, \max(0, k - 1))</tex>.
 +
# <tex>l < i < m </tex>
 +
#: Если <tex>x[i] = y[i + j]</tex>, тогда следующая тройка <tex>(i + 1, j, k)</tex>.
 +
#: Если <tex>x[i] \neq y[i + j]</tex>, тогда возможны два случая в зависимости от значения <tex>t[i]</tex>:
 +
#:* Если <tex>t[i] \leqslant l</tex>, тогда следующая тройка <tex>(l, i + j - t[i], \max(0, t[i]))</tex>.
 +
#:* Если <tex>t[i] > l</tex>, тогда следующая тройка <tex>(t[i], i + j - t[i], l)</tex>.
 +
# <tex>i = m</tex>:
 +
#: Если <tex> k < l </tex> и <tex>x[k] = y[j + k]</tex>, тогда следующая тройка <tex>(i, j, k + 1)</tex>.
 +
#: Иначе либо <tex>k < l</tex> и <tex>x[k] \ne y[l + k]</tex>, либо <tex>k = l</tex>. Если <tex>k = l</tex>, то вхождение <tex>x</tex> в <tex>y</tex> найдено. В обоих случаях следующая тройка вычисляется, как в случае <tex>l < i < m </tex>.
 +
 
 +
 
 +
[[Файл:Apostolico-Crochemore-Example.png]]
 +
 
 +
==Псевдокод==
 +
'''void''' getT('''string''' x, '''int''' t[]): <font color=green>//функция, вычисляющая массив <tex>t</tex> для строки <tex>x</tex></font>
 +
    '''int''' i = 0
 +
    '''int''' j = t[0] = -1
 +
    '''while''' i < x.size
 +
      '''while''' j > -1 '''and''' x[i] <tex>\neq</tex> x[j]
 +
          j = t[j]
 +
      i++
 +
      j++
 +
      '''if''' i < m '''and''' x[i] == x[j]
 +
          t[i] = t[j]
 +
      '''else'''
 +
          t[i] = j
 +
   
 +
'''vector''' aG('''string''' x, '''string''' y): <font color=green>//<tex>x</tex> {{---}} образец, <tex>y</tex> {{---}} текст</font>
 +
    '''int''' l
 +
    '''int''' t[x.size + 1]
 +
    '''vector''' v
 +
 +
    <font color=green>//этап предпосчета</font>
 +
    getT(x, t)
 +
    <font color=green>//вычисление значения <tex>l</tex> </font>
 +
    '''for''' l = 1; x[l - 1] == x[l]; l++
 +
    '''if''' l == x.size
 +
      l = 0
 +
 +
    <font color=green>//этап поиска</font>
 +
    '''int''' i = l
 +
    '''int''' j = 0
 +
    '''int''' k = 0
 +
    '''while''' j <tex>\leqslant</tex> y.size - x.size
 +
      '''while''' i < x.size '''and''' x[i] == y[i + j]  <font color=green>// если <tex>x[i] = y[i + j]</tex></font>
 +
          ++i                                <font color=green>// тогда следующая тройка <tex>(i + 1, j, k)</tex></font>
 +
      '''if''' i <tex>\geqslant</tex> x.size
 +
          '''while''' k < l '''and''' x[k] == y[j + k] <font color=green>// если <tex>k < l</tex> и <tex>x[k] = y[j + k]</tex></font>
 +
            ++k                          <font color=green>// тогда следующая тройка <tex>(i, j, k + 1)</tex></font>
 +
          '''if''' k <tex>\geqslant</tex> l          <font color=green>// если <tex>k = l</tex></font>
 +
            v.pushBack(j)  <font color=green>// тогда найдена подстрока в позиции j</font>
 +
      j += i - t[i]        <font color=green>// вычисляем новый сдвиг</font>
 +
      '''if''' i == l
 +
          k = max(0, k - 1) <font color=green>// если <tex>i = l</tex> и <tex>x[i] \neq y[i + j]</tex>, тогда следующая тройка <tex>(l, j + 1, \max(0, k - 1))</tex></font>
 +
      '''else if''' t[i] <tex>\leqslant</tex> l      <font color=green>// если <tex>t[i] \leqslant l</tex>, тогда следующая тройка <tex>(l, i + j - t[i], \max(0, t[i]))</tex></font>
 +
          k = max(0, t[i])
 +
          i = l
 +
      '''else'''              <font color=green>// если <tex>t[i] > l</tex>, тогда следующая тройка <tex>(t[i], i + j - t[i], l)</tex></font>
 +
          k = l
 +
          i = t[i]
 +
    '''return''' v
 +
 
 +
==Пример==
 +
{| class = "wikitable"
 +
! Изображение !! <tex>(i, j, k)</tex> !! Описание
 +
|-align="center"
 +
|[[Файл:Apostolico-Crochemore-step-1.png|500px]]
 +
|<tex>(1, 0, 0)</tex>
 +
|Подставив шаблон к позиции <tex>0</tex> получим, что <tex>x[1] \neq y[1]</tex>. Вычислив сдвиг, получим <tex>j = 1</tex>.
 +
|-align="center"
 +
|[[Файл:Apostolico-Crochemore-step-2.png|500px]]
 +
|<tex>(1, 1, 0)</tex>
 +
|Подставив шаблон к позиции <tex>1</tex> получим, что <tex>x[0, \ldots , 3] = y[1, \ldots , 4]</tex>. Следовательно, <tex>x</tex> подстрока <tex>y</tex> в позиции <tex>1</tex>. Вычислив сдвиг, получим <tex>j = 4</tex>.
 +
|-align="center"
 +
|[[Файл:Apostolico-Crochemore-step-3.png|500px]]
 +
|<tex>(1, 4, 1)</tex>
 +
|Подставив шаблон к позиции <tex>4</tex> получим, что <tex>x[1] \neq y[5]</tex>. Вычислив сдвиг, получим <tex>j = 5</tex>.
 +
|-align="center"
 +
|[[Файл:Apostolico-Crochemore-step-4.png|500px]]
 +
|<tex>(1, 5, 0)</tex>
 +
|Подставив шаблон к позиции <tex>5</tex> получим, что <tex>x[1] \neq y[6]</tex>. Вычислив сдвиг, получим <tex>j = 6</tex>.
 +
|-align="center"
 +
|[[Файл:Apostolico-Crochemore-step-5.png|500px]]
 +
|<tex>(1, 6, 0)</tex>
 +
|Подставив шаблон к позиции <tex>6</tex> получим, что <tex>x[1] \neq y[7]</tex>. Вычислив сдвиг, получим <tex>j = 7</tex>.
 +
|-align="center"
 +
|[[Файл:Apostolico-Crochemore-step-6.png|500px]]
 +
|<tex>(1, 7, 0)</tex>
 +
|Подставив шаблон к позиции <tex>7</tex> получим, что <tex>x[1] \neq y[8]</tex>. Вычислив сдвиг, получим <tex>j = 8</tex>.
 +
|-align="center"
 +
|[[Файл:Apostolico-Crochemore-step-7.png|500px]]
 +
|<tex>(1, 8, 0)</tex>
 +
|Подставив шаблон к позиции <tex>8</tex> получим, что <tex>x[0, \ldots , 3] = y[8, \ldots , 11]</tex>. Следовательно, <tex>x</tex> подстрока <tex>y</tex> в позиции <tex>8</tex>.
 +
|-
 +
|}
 +
 
 +
==Асимптотика алгоритма==
 +
Этап предподсчета, а именно вычисление массива <tex>t</tex> и переменной <tex>l</tex> занимает <math>O(m)</math> времени и константное количество памяти. Этап поиска занимает <math>O(n)</math> времени, более того, алгоритм в худшем случае выполнит <tex>\dfrac{3}{2} n</tex> сравнений.
 +
 
 +
==См. также==
 +
*[[Алгоритм Кнута-Морриса-Пратта|Алгоритм Кнута-Морриса-Пратта]]
 +
*[[Алгоритм Бойера-Мура|Алгоритм Бойера-Мура]]
 +
 
 +
==Источники информации==
 +
*[http://www-igm.univ-mlv.fr/~lecroq/string/node12.html#SECTION00120 www-igm.univ-mlv.fr — Apostolico-Crochemore algorithm]
 +
 
 +
[[Категория:Алгоритмы и структуры данных]]
 +
[[Категория:Поиск подстроки в строке]]
 +
[[Категория:Точный поиск]]

Текущая версия на 19:15, 4 сентября 2022

Алгоритм Апостолико — Крочемора (англ. Apostolico — Crochemore algorithm) — алгоритм поиска подстроки в строке.

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

Нам даны: [math]y[/math] — текст, [math]x[/math] — образец, [math]m = |x|[/math], [math]n = |y|[/math].

Для начала рассмотрим ситуацию, когда мы сравниваем наш образец с [math]y[j \ldots j + m - 1][/math]. Предположим, что [math]x[i] \neq y[i + j][/math] при [math]0 \lt i \lt m[/math]. Тогда [math]x[0 \ldots i - 1] = y[j \ldots i + j - 1] = u[/math] и [math]a = x[i] \neq y[i + j] = b[/math]. Когда сдвиг возможен, разумно ожидать, что префикс [math]v[/math] шаблона совпадет c некоторым суффиксом [math]u[/math]. Более того, если мы хотим избежать несовпадения при сдвиге, то нужно, чтобы символ, следующий за префиксом [math]v[/math] в шаблоне, не совпадал с [math]a[/math]. Такой наибольший префикс [math]v[/math] называется помеченным бордером строки [math]u[/math].


Определение:
Помеченный бордер (англ. tagged border) строки [math]\beta[/math] — строка [math]\alpha : \forall i = 1 \ldots n - 1, \alpha[i] = \beta[i + (m - n)], \alpha[n] \neq \beta[m], n = |\alpha|, m = |\beta|[/math].


Введем обозначение: пусть [math]t[i][/math] — длина наибольшего бордера для [math]x[0 .. i - 1][/math] за которым следует символ [math]c \neq x[i][/math] и [math]-1[/math] если нет такого помеченного бордера, где [math]0 \lt i \leqslant m[/math] ([math]t[0] = -1[/math]). Затем, после сдвига, сравнение можно продолжить между символами [math]x[t[i]][/math] и [math]y[i + j][/math] не потеряв никакого вхождения [math]x[/math] в [math]y[/math] и избежав отступа по тексту (смотри рисунок ниже).


Apostolico-Crochemore-Shifts.png

Примечание: [math]v[/math] — помеченный бордер строки [math]u[/math].


Пусть теперь [math]l = 0[/math], если [math]x = c ^ m[/math] и [math]c \in \Sigma[/math], иначе [math]l[/math] равно позиции первого элемента, который не равен [math]x[0][/math] ([math]x = a ^ l bu[/math], где [math]a \in \Sigma[/math], [math]b \in \Sigma[/math], [math]a \neq b[/math], [math]u \in \Sigma^*[/math]). При каждой подстановке шаблона к тексту к позиции [math]i[/math] мы проводим следующие сравнения: [math]x[l] = y[i + l], x[l + 1] = y[i + l + 1], \ldots , x[m - 2] = y[i + m - 2], x[m - 1] = y[i + m - 1],[/math][math] x[0] = y[i], x[1] = y [i + 1], \ldots , x[l - 1] = y[i + l - 1][/math].


Во время поиска вхождений мы рассматриваем данную тройку [math](i, j, k)[/math] где:

  • шаблон сравнивается с [math]y[j, \ldots , j + m - 1][/math]
  • [math]0 \leqslant k \leqslant l[/math] и [math]x[0, \ldots, k - 1] = y[j, \ldots , j + k - 1][/math]
  • [math]l \leqslant i \lt m[/math] и [math]x[l, \ldots, i - 1] = y[j + l, \ldots , i + j - 1][/math]

(см. рисунок ниже)

Вначале инициализируем эту тройку [math](l, 0, 0)[/math]. Теперь опишем, как по уже вычисленной тройке [math](i, j, k)[/math] перейти к следующей. Возможны три случая в зависимости от значения [math]i[/math]:

  1. [math]i = l[/math]:
    Если [math]x[i] = y[i + j][/math], тогда следующая тройка [math](i + 1, j, k)[/math].
    Если [math]x[i] \neq y[i + j][/math], тогда следующая тройка [math](l, j + 1, \max(0, k - 1))[/math].
  2. [math]l \lt i \lt m [/math]
    Если [math]x[i] = y[i + j][/math], тогда следующая тройка [math](i + 1, j, k)[/math].
    Если [math]x[i] \neq y[i + j][/math], тогда возможны два случая в зависимости от значения [math]t[i][/math]:
    • Если [math]t[i] \leqslant l[/math], тогда следующая тройка [math](l, i + j - t[i], \max(0, t[i]))[/math].
    • Если [math]t[i] \gt l[/math], тогда следующая тройка [math](t[i], i + j - t[i], l)[/math].
  3. [math]i = m[/math]:
    Если [math] k \lt l [/math] и [math]x[k] = y[j + k][/math], тогда следующая тройка [math](i, j, k + 1)[/math].
    Иначе либо [math]k \lt l[/math] и [math]x[k] \ne y[l + k][/math], либо [math]k = l[/math]. Если [math]k = l[/math], то вхождение [math]x[/math] в [math]y[/math] найдено. В обоих случаях следующая тройка вычисляется, как в случае [math]l \lt i \lt m [/math].


Apostolico-Crochemore-Example.png

Псевдокод

void getT(string x, int t[]): //функция, вычисляющая массив [math]t[/math] для строки [math]x[/math]
   int i = 0
   int j = t[0] = -1
   while i < x.size 
      while j > -1 and x[i] [math]\neq[/math] x[j]
         j = t[j]
      i++
      j++
      if i < m and x[i] == x[j]
         t[i] = t[j]
      else
         t[i] = j
   
vector aG(string x, string y): //[math]x[/math] — образец, [math]y[/math] — текст
   int l
   int t[x.size + 1]
   vector v

   //этап предпосчета
   getT(x, t)
   //вычисление значения [math]l[/math] 
   for l = 1; x[l - 1] == x[l]; l++
   if l == x.size
      l = 0

   //этап поиска
   int i = l
   int j = 0
   int k = 0
   while j [math]\leqslant[/math] y.size - x.size 
      while i < x.size and x[i] == y[i + j]  // если [math]x[i] = y[i + j][/math]
         ++i                                 // тогда следующая тройка [math](i + 1, j, k)[/math] 
      if i [math]\geqslant[/math] x.size 
         while k < l and x[k] == y[j + k] // если [math]k \lt  l[/math] и [math]x[k] = y[j + k][/math]
            ++k                           // тогда следующая тройка [math](i, j, k + 1)[/math] 
         if k [math]\geqslant[/math] l           // если [math]k = l[/math] 
            v.pushBack(j)   // тогда найдена подстрока в позиции j
      j += i - t[i]         // вычисляем новый сдвиг
      if i == l
         k = max(0, k - 1) // если [math]i = l[/math] и [math]x[i] \neq y[i + j][/math], тогда следующая тройка [math](l, j + 1, \max(0, k - 1))[/math]
      else if t[i] [math]\leqslant[/math] l      // если [math]t[i] \leqslant l[/math], тогда следующая тройка [math](l, i + j - t[i], \max(0, t[i]))[/math]
         k = max(0, t[i])
         i = l
      else              // если [math]t[i] \gt  l[/math], тогда следующая тройка [math](t[i], i + j - t[i], l)[/math]
         k = l
         i = t[i]
   return v

Пример

Изображение [math](i, j, k)[/math] Описание
Apostolico-Crochemore-step-1.png [math](1, 0, 0)[/math] Подставив шаблон к позиции [math]0[/math] получим, что [math]x[1] \neq y[1][/math]. Вычислив сдвиг, получим [math]j = 1[/math].
Apostolico-Crochemore-step-2.png [math](1, 1, 0)[/math] Подставив шаблон к позиции [math]1[/math] получим, что [math]x[0, \ldots , 3] = y[1, \ldots , 4][/math]. Следовательно, [math]x[/math] подстрока [math]y[/math] в позиции [math]1[/math]. Вычислив сдвиг, получим [math]j = 4[/math].
Apostolico-Crochemore-step-3.png [math](1, 4, 1)[/math] Подставив шаблон к позиции [math]4[/math] получим, что [math]x[1] \neq y[5][/math]. Вычислив сдвиг, получим [math]j = 5[/math].
Apostolico-Crochemore-step-4.png [math](1, 5, 0)[/math] Подставив шаблон к позиции [math]5[/math] получим, что [math]x[1] \neq y[6][/math]. Вычислив сдвиг, получим [math]j = 6[/math].
Apostolico-Crochemore-step-5.png [math](1, 6, 0)[/math] Подставив шаблон к позиции [math]6[/math] получим, что [math]x[1] \neq y[7][/math]. Вычислив сдвиг, получим [math]j = 7[/math].
Apostolico-Crochemore-step-6.png [math](1, 7, 0)[/math] Подставив шаблон к позиции [math]7[/math] получим, что [math]x[1] \neq y[8][/math]. Вычислив сдвиг, получим [math]j = 8[/math].
Apostolico-Crochemore-step-7.png [math](1, 8, 0)[/math] Подставив шаблон к позиции [math]8[/math] получим, что [math]x[0, \ldots , 3] = y[8, \ldots , 11][/math]. Следовательно, [math]x[/math] подстрока [math]y[/math] в позиции [math]8[/math].

Асимптотика алгоритма

Этап предподсчета, а именно вычисление массива [math]t[/math] и переменной [math]l[/math] занимает [math]O(m)[/math] времени и константное количество памяти. Этап поиска занимает [math]O(n)[/math] времени, более того, алгоритм в худшем случае выполнит [math]\dfrac{3}{2} n[/math] сравнений.

См. также

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