Алгоритм Райта

Алгоритм Райта (англ. 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 + \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]3[/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]y = GCATCGCAGAGAGTATACAGTACG[/math] и образец [math]x=GCAGAGAG[/math]

Массив [math]bmBc[/math] после фазы препроцессинга

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

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

См. также

• Алгоритм Кнута-Морриса-Пратта
• Алгоритм Бойера-Мура
• Алгоритм Апостолико-Крочемора

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

• RAITA T., 1992, Tuning the Boyer-Moore-Horspool string searching algorithm, Software - Practice & Experience, 22(10):879-884.
• www-igm.univ-mlv.fr — Raita algorithm
• en.wikipedia.org — Raita algorithm