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

Материал из Викиконспекты
Перейти к: навигация, поиск
(2, 3, 4)
(→‎Псевдокод)
Строка 11: Строка 11:
  
 
==Псевдокод==
 
==Псевдокод==
 +
Побочные функции
 +
'''int''' findFirst('''char'''[] y, '''int''' fromIndex, '''int''' toIndex, '''char''' symbol)
 +
    '''for''' (i = fromIndex .. toIndex)
 +
      '''if''' (y[i] == symbol)
 +
          '''return''' i
 +
    '''return''' -1
 +
'''boolean''' restEquals('''char'''[] y, '''int''' fromIndex, '''char'''[] x, '''int''' toIndex)
 +
    '''for''' (i = fromIndex .. toIndex)
 +
      '''if''' (y[i] != x[i - fromIndex + 1])
 +
          '''return''' false
 +
    '''return''' true
  
−
  '''void''' RAITA('''char'''[] x, '''int''' m, '''char'''[] y, '''int''' n) {
+
Стадия препроцессинга (совпадает со стадией препроцессинга в [[Алгоритм Бойера-Мура|алгоритме Бойера-Мура]])
−
      '''int'''[] bmBc
+
'''int'''[] preBmBc('''char'''[] x, '''int''' m)  
−
      '''char''' c, firstCh, middleCh, lastCh;
+
    '''int'''[] result = '''int'''[ASIZE]
−
      '''if''' (m == 0)
+
    <font color=green>//Где ASIZE {{---}} размер алфавита</font>
−
        '''return'''
+
    '''for''' (i = 0 .. ASIZE - 1)
−
      '''else if''' (m == 1) {
+
      result[i] = m;
−
        <font color=green>//Проверка на случай поиска вхождения одного символа</font>
+
    '''for''' (i = 0 .. m - 2)
−
        '''int''' match = 0
+
      result[x[i]] = m - i - 1;
−
        '''while''' (match < n) {
+
    '''return''' result
−
            match = findFirst(y, match, n - 1, x[0])
+
 
−
            '''if''' (match != -1) {
+
Основная стадия алгоритма
−
              '''print'''(match)
+
'''void''' RAITA('''char'''[] x, '''int''' m, '''char'''[] y, '''int''' n)  
−
            }
+
    '''int'''[] bmBc
−
            '''else'''
+
    '''char''' c, firstCh, middleCh, lastCh;
−
              '''print'''(<font color=green>"No matches"</font>)
+
    '''if''' (m == 0)
−
            '''return'''
+
      '''return'''
−
        }
+
    '''else if''' (m == 1)  
−
      }
+
      <font color=green>//Проверка на случай поиска вхождения одного символа</font>
−
      '''int''' findFirst('''char'''[] y, '''int''' fromIndex, '''int''' toIndex, '''char''' symbol){
+
      '''int''' match = 0
−
        '''for''' (i = fromIndex .. toIndex){
+
      '''while''' (match < n)
−
            '''if''' (y[i] == symbol){
+
          match = findFirst(y, match, n - 1, x[0])
−
                '''return''' i
+
          '''if''' (match != -1)
−
            }
+
            '''print'''(match)
−
        }
+
          '''else'''
−
        '''return''' -1
+
            '''print'''(<font color=green>"No matches"</font>)
−
      }
+
          '''return'''
−
      '''boolean''' restEquals('''char'''[] y, '''int''' fromIndex, '''char'''[] x, '''int''' toIndex){
+
    bmBc = preBmBc (x, m)
−
        '''for''' (i = fromIndex .. toIndex){
+
    firstCh = x[0];
−
            '''if''' (y[i] != x[i - fromIndex + 1]){
+
    middleCh = x[m/2];
−
                '''return''' false
+
    lastCh = x[m - 1];
−
            }
+
    <font color=green>//Поиск</font>
−
        }
+
    '''int''' j = 0
−
        '''return''' true
+
    '''while''' (j <= n - m)  
−
      }
+
      c = y[j + m - 1]
−
    <font color=green> //Стадия препроцессинга</font>
+
      '''if''' (lastCh == c && middleCh == y[j + m / 2] && firstCh == y[j] &&
−
      '''int'''[] preBmBc('''char'''[] x, '''int''' m) {
+
          restEquals(y, j + 1, x, j + m - 2))
−
        '''int'''[] result = '''int'''[m]
+
          '''print'''(j)
−
        '''for''' (i = 0 .. m - 1){
+
          '''return'''
−
          result[i] = m;
+
      j += bmBc[c];
−
        }
+
    '''print'''(<font color=green>"No matches"</font>)
−
        '''for''' (i = 0 .. m - 2){
 
−
          result[x[i]] = m - i - 1;
 
−
        }
 
−
        '''return''' result
 
−
      }
 
−
      bmBc = preBmBc (x, m)
 
−
      firstCh = x[0];
 
−
      middleCh = x[m/2];
 
−
      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>)
 
−
  }
 
  
 
==Асимптотика==
 
==Асимптотика==

Версия 16:43, 27 марта 2016

Алгоритм Райта (англ. 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. Если они опять совпали, то сравниваются символы, находящиеся посередине образца и окна.

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

Псевдокод

Побочные функции 

int findFirst(char[] y, int fromIndex, int toIndex, char symbol)
   for (i = fromIndex .. toIndex)
      if (y[i] == symbol)
         return i
   return -1
boolean restEquals(char[] y, int fromIndex, char[] x, int toIndex)
   for (i = fromIndex .. toIndex)
      if (y[i] != x[i - fromIndex + 1])
         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)[/math] времени и памяти
  • В худшем случае поиск требует [math]O(m \cdot n)[/math] сравнений.

Пример

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

Массив [math]bmBc[/math] после фазы препроцессинга
Изображение [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] сравнений символов

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

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Алгоритм_Райта&oldid=52913»