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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Асимптотика)
м (rollbackEdits.php mass rollback)
 
(не показано 35 промежуточных версий 3 участников)
Строка 1: Строка 1:
'''Алгоритм Райта''' {{---}} алгоритм поиска подстроки в строке, который опубликовал Тим Райта в 1991 году, являющийся модификацией [[Алгоритм Бойера-Мура|алгоритма Бойера-Мура]] и улучшающий его асимптотику
+
'''Алгоритм Райта''' (англ. ''Raita algorithm'') {{---}} алгоритм поиска подстроки в строке, который опубликовал Тим Райта в 1991 году, являющийся модификацией [[Алгоритм Бойера-Мура|алгоритма Бойера-Мура]] и улучшающий его асимптотику.
  
 
==Описание алгоритма==
 
==Описание алгоритма==
Алгоритм Райта ищет образец <tex>x</tex> в заданном тексте <tex>y</tex> сравнивания их символы. Сравнение происходит в следующем порядке (окном текста  <tex>y</tex> будем называть последовательность символов <tex>i \dots m - i + 1</tex>, где <tex>m</tex> {{---}} длина образца <tex>x</tex>):
+
Алгоритм Райта ищет образец <tex>x</tex> в заданном тексте <tex>y</tex>, сравнивания их символы. Окном текста  <tex>y</tex> будем называть последовательность символов <tex>i \dots m - i + 1</tex>, где <tex>m</tex> {{---}} длина образца <tex>x</tex>. Сравнение происходит в следующем порядке:
  
 
# '''Последний''' символ образца сравнивается с самым '''правым''' символом окна.
 
# '''Последний''' символ образца сравнивается с самым '''правым''' символом окна.
 
# Если они совпадают, то '''первый''' символ сравнивается с самым '''левым''' символом окна.
 
# Если они совпадают, то '''первый''' символ сравнивается с самым '''левым''' символом окна.
# Если они опять совпали, то сравниваются символы, находящиеся по середине образца и окна.
+
# Если они опять совпали, то сравниваются символы, находящиеся в середине образца и окна.
  
Если все шаги прошли успешно, то начинаем сравнивать образец и текст посимвольно в обычном порядке, начиная с второго с конца символа. В противном случае, выполняем функцию сдвига плохого символа, которая обрабона в стадии препроцессинга. Эта функция аналогична той, которая была использована в фазе препроцессинга [[Алгоритм Бойера-Мура|алгоритма Бойера-Мура]].
+
Если все шаги прошли успешно, то начинаем сравнивать образец и текст посимвольно в обычном порядке, начиная с второго с конца символа. В противном случае вызываем функцию выполнения сдвига плохого символа, которая отработала в стадии препроцессинга. Эта функция аналогична той, которая была использована в фазе препроцессинга [[Алгоритм Бойера-Мура|алгоритма Бойера-Мура]]. Кроме того, в третьем шаге, в зависимости от специфики текста, можно брать не средний символ, а случайный, либо с каким-то определенным индексом.
  
 
==Псевдокод==
 
==Псевдокод==
 +
Функция поиска индекса первого вхождения сивола в массиве <tex>y</tex> с позиции <tex> \mathtt{fromIndex}</tex> до позиции <tex> \mathtt{toIndex}</tex>:
 +
'''int''' findFirst('''char'''[] y, '''int''' fromIndex, '''int''' toIndex, '''char''' symbol):
 +
    '''for''' (i = fromIndex .. toIndex)
 +
      '''if''' (y[i] == symbol)
 +
          '''return''' i
 +
    '''return''' -1
  
  '''void''' RAITA('''char'''[] x, '''int''' m, '''char'''[] y, '''int''' n) {
+
Проверка, что все символы в <tex>y</tex> с позиции <tex>\mathtt{fromIndex}</tex> и до <tex>\mathtt{toIndex}</tex> и <tex>x</tex> с начала и до конца совпадают:
      '''int'''[] bmBc
+
'''boolean''' restEquals('''char'''[] y, '''int''' fromIndex, '''char'''[] x, '''int''' toIndex):
      '''char''' c, firstCh, middleCh, lastCh;
+
    '''for''' (i = fromIndex .. toIndex)
      '''if''' (m == 0)
+
      '''if''' (y[i] != x[i - fromIndex])
        '''return'''
+
          '''return''' false
      '''else if''' (m == 1) {
+
    '''return''' true
        <font color=green>//Проверка на случай поиска вхождения одного символа</font>
+
 
        '''int''' match = 0
+
Стадия препроцессинга (совпадает со стадией препроцессинга в [[Алгоритм Бойера-Мура|алгоритме Бойера-Мура]]):
        '''while''' (match < n) {
+
'''int'''[] preBmBc('''char'''[] x, '''int''' m):
            match = findFirst(y, match, n - 1, x[0])
+
    '''int'''[] result = '''int'''[ASIZE]
            '''if''' (match != -1) {
+
    <font color=green>//Где ASIZE {{---}} размер алфавита</font>
              '''print'''(match)
+
    '''for''' (i = 0 .. ASIZE - 1)
            }
+
      result[i] = m;
            '''else'''
+
    '''for''' (i = 0 .. m - 2)
              '''print'''(<font color=green>"No matches"</font>)
+
      result[x[i]] = m - i - 1;
            '''return'''
+
    '''return''' result
        }
+
 
      }
+
Основная стадия алгоритма:
      '''int''' findFirst('''char'''[] y, '''int''' fromIndex, '''int''' toIndex, '''char''' symbol){
+
'''void''' RAITA('''char'''[] x, '''int''' m, '''char'''[] y, '''int''' n):
        '''for''' (i = fromIndex .. toIndex){
+
    '''int'''[] bmBc
            '''if''' (y[i] == symbol){
+
    '''char''' c, firstCh, middleCh, lastCh;
                '''return''' i
+
    '''if''' (m == 0)
            }
+
      '''return'''
        }
+
    '''else if''' (m == 1)
        '''return''' -1
+
      <font color=green>//Проверка на случай поиска вхождения одного символа</font>
      }
+
      '''int''' match = 0
      '''boolean''' restEquals('''char'''[] y, '''int''' fromIndex, '''char'''[] x, '''int''' toIndex){
+
      '''while''' (match < n)
        '''for''' (i = fromIndex .. toIndex){
+
          match = findFirst(y, match, n - 1, x[0])
            '''if''' (y[i] != x[i - fromIndex + 1]){
+
          '''if''' (match != -1)
                '''return''' false
+
            '''print'''(match)
            }
+
          '''else'''
        }
+
            '''print'''(<font color=green>"No matches"</font>)
        '''return''' true
+
          '''return'''
      }
+
    <font color=green>//Вычисление массива плохих сиволов и объявление первого, последнего и среднего сиволов</font>
    <font color=green> //Стадия препроцессинга</font>
+
    bmBc = preBmBc (x, m)
      '''int'''[] preBmBc('''char'''[] x, '''int''' m) {
+
    firstCh = x[0];
        '''int'''[] result = '''int'''[m]
+
    middleCh = x[m/2];
        '''for''' (i = 0 .. m - 1){
+
    lastCh = x[m - 1];
          result[i] = m;
+
    <font color=green>//Поиск</font>
        }
+
    '''int''' j = 0
        '''for''' (i = 0 .. m - 2){
+
    '''while''' (j <= n - m)  
          result[x[i]] = m - i - 1;
+
      c = y[j + m - 1]
        }
+
      '''if''' (lastCh == c && middleCh == y[j + m / 2] && firstCh == y[j] &&   <font color=green>//Совпадение шаблона и окна из текста</font>
        '''return''' result
+
          restEquals(y, j + 1, x, j + m - 2))
      }
+
          '''print'''(j)
      bmBc = preBmBc (x, m)
+
          '''return'''
      firstCh = x[0];
+
      j += bmBc[c];
      middleCh = x[m/2];
+
    '''print'''(<font color=green>"No matches"</font>)
      lastCh = x[m - 1];
 
      <font color=green>//Поиск</font>
 
      '''int''' j = 0
 
      '''while''' (j <= n - m) {
 
        c = y[j + m - 1]
 
        '''if''' (lastCh == c && middleCh == y[j + m / 2] && firstCh == y[j] &&
 
            restEquals(y, j + 1, x, j + m - 2)){
 
            '''print'''(j)
 
            '''return'''
 
        }
 
        j += bmBc[c];
 
      }
 
      '''print'''(<font color=green>"No matches"</font>)
 
  }
 
  
 
==Асимптотика==
 
==Асимптотика==
* Фаза препроцессинга требует <tex>O(m)</tex> времени и памяти
+
* Фаза препроцессинга требует <tex>O(m + \sigma)</tex> времени и памяти, где <tex>\sigma</tex> {{---}} размер алфавита.
 
* В худшем случае поиск требует <tex>O(m \cdot n)</tex> сравнений.
 
* В худшем случае поиск требует <tex>O(m \cdot n)</tex> сравнений.
 +
'''Пример:''' текст, состоящий только из букв <tex>a</tex> и образец <tex>aa..baa</tex>. В таком случае <tex>BmBc[a]</tex> будет равен <tex>1</tex>, то есть после каждой фазы сравнений мы будем сдвигаться на <tex>1</tex>. Значит, всего будет <tex>n</tex> фаз сравнений, а каждая фаза отработает за <tex>m - 2</tex>, поскольку расхождение будет только в третьем с конца символе, то мы сравним сначала последний, потом первый, потом средний, а затем пойдем с самого начала, сравнивая все символы подряд. Итого получаем асимптотику <tex>O(m \cdot n)</tex>
 +
* В лучшем случае требует <tex > \Omega(n / m)</tex> сравнений.
 +
'''Пример:''' текст вида <tex>a..ba..ab..a</tex> и образец <tex>ba..ab</tex>. В таком случае <tex>BmBc[b]</tex> будет равен <tex>m - 1</tex>. Значит, всего будет не более чем <tex>n / (m - 1)</tex> фаз сравнений, а каждая фаза (кроме той, в которой мы нашли вхождение строки) будет работать за <tex>1</tex>, поскольку расхождение будет уже в последних символах. Итого получаем асимптотику  <tex > \Omega(n / m)</tex>
 +
 +
==Сравнение с Алгоритмом Бойера-Мура==
 +
[[Файл:RaitaComparing.png|350px|thumb|Right|Верхняя кривая {{---}} алгоритм Бойера-Мура, нижняя {{---}} Райта]]
 +
 +
В своей статье Тим Райта экспериментально проверил ускорение алгоритма на реальных текстах. Тесты были приведены в техническом отчете, написанном на английском языке. Длина текста составила <tex>29 550</tex> символов. Использовался '''ASCII''' алфавит (подразумевается теоритический размер алфавита, равный <tex>128</tex>, в тексте было использовано только <tex>85</tex> символов.) Шаблоны длиной <tex>2-20</tex> символов случайно выбирались из текста, а затем проходил их поиск в тексте. (См. рисунок)
 +
 +
Результат показывает ускорение модификации алгоритма на <tex>21-27\%</tex> относительно оригинального на всех шаблонах. Шаблон встречался в тексте как минимум один раз (из-за метода его выбора). Однако, результаты теста на шаблонах, которые не встречались в тексте, были очень похожи на верхнюю кривую. Очевидно, что шаблоны, имеющие часто встречающиеся суффиксы, такие как <tex>-ion</tex> или <tex>-ed</tex> вносят наибольший вклад в быстродействие модификации. (В алгоритме Бойера-Мура мы будем идти с конца, пока не найдем различия, то есть произведем сравнение на всем суффиксе, в то время как в алгоритме Райта мы выйдем сразу после несовпадения первых символов).
 +
 +
Кроме того, производительность растет с увеличением <tex>m</tex>, поскольку вклад сравнений первого, последнего и среднего символа уменьшается. С другой стороны, производительность ухудшается с уменьшением размера алфавита, поскольку вероятность того, что первый, средний и последний символ из шаблона и текста совпадут, увеличивается. Однако Тим Райта в своей статье пишет, что несмотря на теоритическую возможность ухудшения, на практике, скорее всего, разница будет заметна лишь на очень маленьких алфавитах (например, длины <tex>2</tex>).
  
 
==Пример==
 
==Пример==
 +
Пусть нам дана строка <tex>y = GCATCGCAGAGAGTATACAGTACG</tex> и образец <tex>x=GCAGAGAG</tex>
 +
 +
Построим массив <tex>bmBc</tex>:
 +
 +
[[Файл:RaitaPre.png|250px]]
 +
 +
Рассмотрим шаги алгоритма:
 +
 +
{| class = "wikitable"
 +
! Изображение !! <tex>(j, bmBc[y[j]])</tex> !! Описание
 +
|-align="center"
 +
|[[Файл:Raita1.png|550px]]
 +
|<tex>(7, 1)</tex>
 +
|Сравниванием последние символы, они неравны, поэтому сдвигаемся.
 +
|-align="center"
 +
|[[Файл:Raita2.png|550px]]
 +
|<tex>(8, 2)</tex>
 +
|Последние символы совпали, сравниваем первые, сдвигаемся.
 +
|-align="center"
 +
|[[Файл:Raita3.png|550px]]
 +
|<tex>(10, 2)</tex>
 +
|Последние символы совпали, сравниваем первые, сдвигаемся.
 +
|-align="center"
 +
|[[Файл:Raita4.png|550px]]
 +
|<tex>(12, 2)</tex>
 +
|Совпали последний, первый и средний символы, пробегаемся по всему шаблону и сравниваем символы. Нашли строчку в тексте. Продолжим работу (для примера, в обычном варианте на этом этапе мы можем выйти, если требуется найти только одно вхождение) и сдвинемся.
 +
|-align="center"
 +
|[[Файл:Raita5.png|550px]]
 +
|<tex>(14, 1)</tex>
 +
|Делаем сравнение последних символов, оно неудачно, сдвигаемся.
 +
|-align="center"
 +
|[[Файл:Raita6.png|550px]]
 +
|<tex>(15, 8)</tex>
 +
|Делаем сравнение последних символов, оно неудачно, сдвигаемся.
 +
|-align="center"
 +
|[[Файл:Raita7.png|550px]]
 +
|<tex>(23, 2)</tex>
 +
|Последние символы совпали, сравниваем первые, сдвигаемся. Строка закончилась, выходим.
 +
|-
 +
|}
 +
 +
В итоге, чтобы найти одно вхождение образца длиной <tex>m = 8</tex> в образце длиной <tex>n = 24</tex>, нам понадобилось <tex>18</tex> сравнений символов.
 +
 +
==См. также==
 +
*[[Алгоритм Кнута-Морриса-Пратта|Алгоритм Кнута-Морриса-Пратта]]
 +
*[[Алгоритм Бойера-Мура|Алгоритм Бойера-Мура]]
 +
*[[Алгоритм Апостолико-Крочемора|Алгоритм Апостолико-Крочемора]]
  
 
==Источники информации==
 
==Источники информации==
* RAITA T., 1992, Tuning the Boyer-Moore-Horspool string searching algorithm, Software - Practice & Experience, 22(10):879-884.
+
* [http://www-igm.univ-mlv.fr/~lecroq/string/node22.html#SECTION00220 Exact string matching algorithms {{---}} Raita algorithm]
* [http://www-igm.univ-mlv.fr/~lecroq/string/node22.html#SECTION00220 Raita algorithm]
+
* [https://en.wikipedia.org/wiki/Raita_algorithm Wikipedia {{---}} Raita algorithm]
* [https://en.wikipedia.org/wiki/Raita_algorithm Raita algorithm на англ вики]
+
* [http://www.di.ufpe.br/~paguso/courses/if767/bib/Raita_1992.pdf UFPE {{---}} Оригинальная статья]
  
[[Категория: Дискретная математика и алгоритмы]]  
+
[[Категория:Алгоритмы и структуры данных]]
 
[[Категория: Поиск подстроки в строке]]
 
[[Категория: Поиск подстроки в строке]]
 
[[Категория: Точный поиск]]
 
[[Категория: Точный поиск]]

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

Алгоритм Райта (англ. Raita algorithm) — алгоритм поиска подстроки в строке, который опубликовал Тим Райта в 1991 году, являющийся модификацией алгоритма Бойера-Мура и улучшающий его асимптотику.

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

Алгоритм Райта ищет образец [math]x[/math] в заданном тексте [math]y[/math], сравнивания их символы. Окном текста [math]y[/math] будем называть последовательность символов [math]i \dots m - i + 1[/math], где [math]m[/math] — длина образца [math]x[/math]. Сравнение происходит в следующем порядке:

  1. Последний символ образца сравнивается с самым правым символом окна.
  2. Если они совпадают, то первый символ сравнивается с самым левым символом окна.
  3. Если они опять совпали, то сравниваются символы, находящиеся в середине образца и окна.

Если все шаги прошли успешно, то начинаем сравнивать образец и текст посимвольно в обычном порядке, начиная с второго с конца символа. В противном случае вызываем функцию выполнения сдвига плохого символа, которая отработала в стадии препроцессинга. Эта функция аналогична той, которая была использована в фазе препроцессинга алгоритма Бойера-Мура. Кроме того, в третьем шаге, в зависимости от специфики текста, можно брать не средний символ, а случайный, либо с каким-то определенным индексом.

Псевдокод

Функция поиска индекса первого вхождения сивола в массиве [math]y[/math] с позиции [math] \mathtt{fromIndex}[/math] до позиции [math] \mathtt{toIndex}[/math]:

int findFirst(char[] y, int fromIndex, int toIndex, char symbol):
   for (i = fromIndex .. toIndex)
      if (y[i] == symbol)
         return i
   return -1

Проверка, что все символы в [math]y[/math] с позиции [math]\mathtt{fromIndex}[/math] и до [math]\mathtt{toIndex}[/math] и [math]x[/math] с начала и до конца совпадают:

boolean restEquals(char[] y, int fromIndex, char[] x, int toIndex):
   for (i = fromIndex .. toIndex)
      if (y[i] != x[i - fromIndex])
         return false
   return true

Стадия препроцессинга (совпадает со стадией препроцессинга в алгоритме Бойера-Мура):

int[] preBmBc(char[] x, int m): 
   int[] result = int[ASIZE]
   //Где ASIZE — размер алфавита
   for (i = 0 .. ASIZE - 1)
      result[i] = m;
   for (i = 0 .. m - 2)
      result[x[i]] = m - i - 1;
   return result

Основная стадия алгоритма:

void RAITA(char[] x, int m, char[] y, int n): 
   int[] bmBc
   char c, firstCh, middleCh, lastCh;
   if (m == 0)
      return
   else if (m == 1) 
      //Проверка на случай поиска вхождения одного символа
      int match = 0
      while (match < n) 
         match = findFirst(y, match, n - 1, x[0])
         if (match != -1) 
            print(match)
         else
            print("No matches")
         return
   //Вычисление массива плохих сиволов и объявление первого, последнего и среднего сиволов
   bmBc = preBmBc (x, m)
   firstCh = x[0];
   middleCh = x[m/2];
   lastCh = x[m - 1];
   //Поиск
   int j = 0
   while (j <= n - m) 
      c = y[j + m - 1]
      if (lastCh == c && middleCh == y[j + m / 2] && firstCh == y[j] &&   //Совпадение шаблона и окна из текста
         restEquals(y, j + 1, x, j + m - 2))
         print(j)
         return
      j += bmBc[c];
   print("No matches")

Асимптотика

  • Фаза препроцессинга требует [math]O(m + \sigma)[/math] времени и памяти, где [math]\sigma[/math] — размер алфавита.
  • В худшем случае поиск требует [math]O(m \cdot n)[/math] сравнений.

Пример: текст, состоящий только из букв [math]a[/math] и образец [math]aa..baa[/math]. В таком случае [math]BmBc[a][/math] будет равен [math]1[/math], то есть после каждой фазы сравнений мы будем сдвигаться на [math]1[/math]. Значит, всего будет [math]n[/math] фаз сравнений, а каждая фаза отработает за [math]m - 2[/math], поскольку расхождение будет только в третьем с конца символе, то мы сравним сначала последний, потом первый, потом средний, а затем пойдем с самого начала, сравнивая все символы подряд. Итого получаем асимптотику [math]O(m \cdot n)[/math]

  • В лучшем случае требует [math] \Omega(n / m)[/math] сравнений.

Пример: текст вида [math]a..ba..ab..a[/math] и образец [math]ba..ab[/math]. В таком случае [math]BmBc[b][/math] будет равен [math]m - 1[/math]. Значит, всего будет не более чем [math]n / (m - 1)[/math] фаз сравнений, а каждая фаза (кроме той, в которой мы нашли вхождение строки) будет работать за [math]1[/math], поскольку расхождение будет уже в последних символах. Итого получаем асимптотику [math] \Omega(n / m)[/math]

Сравнение с Алгоритмом Бойера-Мура

Верхняя кривая — алгоритм Бойера-Мура, нижняя — Райта

В своей статье Тим Райта экспериментально проверил ускорение алгоритма на реальных текстах. Тесты были приведены в техническом отчете, написанном на английском языке. Длина текста составила [math]29 550[/math] символов. Использовался ASCII алфавит (подразумевается теоритический размер алфавита, равный [math]128[/math], в тексте было использовано только [math]85[/math] символов.) Шаблоны длиной [math]2-20[/math] символов случайно выбирались из текста, а затем проходил их поиск в тексте. (См. рисунок)

Результат показывает ускорение модификации алгоритма на [math]21-27\%[/math] относительно оригинального на всех шаблонах. Шаблон встречался в тексте как минимум один раз (из-за метода его выбора). Однако, результаты теста на шаблонах, которые не встречались в тексте, были очень похожи на верхнюю кривую. Очевидно, что шаблоны, имеющие часто встречающиеся суффиксы, такие как [math]-ion[/math] или [math]-ed[/math] вносят наибольший вклад в быстродействие модификации. (В алгоритме Бойера-Мура мы будем идти с конца, пока не найдем различия, то есть произведем сравнение на всем суффиксе, в то время как в алгоритме Райта мы выйдем сразу после несовпадения первых символов).

Кроме того, производительность растет с увеличением [math]m[/math], поскольку вклад сравнений первого, последнего и среднего символа уменьшается. С другой стороны, производительность ухудшается с уменьшением размера алфавита, поскольку вероятность того, что первый, средний и последний символ из шаблона и текста совпадут, увеличивается. Однако Тим Райта в своей статье пишет, что несмотря на теоритическую возможность ухудшения, на практике, скорее всего, разница будет заметна лишь на очень маленьких алфавитах (например, длины [math]2[/math]).

Пример

Пусть нам дана строка [math]y = GCATCGCAGAGAGTATACAGTACG[/math] и образец [math]x=GCAGAGAG[/math]

Построим массив [math]bmBc[/math]:

RaitaPre.png

Рассмотрим шаги алгоритма:

Изображение [math](j, bmBc[y[j]])[/math] Описание
Raita1.png [math](7, 1)[/math] Сравниванием последние символы, они неравны, поэтому сдвигаемся.
Raita2.png [math](8, 2)[/math] Последние символы совпали, сравниваем первые, сдвигаемся.
Raita3.png [math](10, 2)[/math] Последние символы совпали, сравниваем первые, сдвигаемся.
Raita4.png [math](12, 2)[/math] Совпали последний, первый и средний символы, пробегаемся по всему шаблону и сравниваем символы. Нашли строчку в тексте. Продолжим работу (для примера, в обычном варианте на этом этапе мы можем выйти, если требуется найти только одно вхождение) и сдвинемся.
Raita5.png [math](14, 1)[/math] Делаем сравнение последних символов, оно неудачно, сдвигаемся.
Raita6.png [math](15, 8)[/math] Делаем сравнение последних символов, оно неудачно, сдвигаемся.
Raita7.png [math](23, 2)[/math] Последние символы совпали, сравниваем первые, сдвигаемся. Строка закончилась, выходим.

В итоге, чтобы найти одно вхождение образца длиной [math]m = 8[/math] в образце длиной [math]n = 24[/math], нам понадобилось [math]18[/math] сравнений символов.

См. также

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