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

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

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

Псевдокод

  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
        }
     }
     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[m]
        for (i = 0 .. m - 1){
     	    result[i] = m;
        }
        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];
     //Поиск
     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]1 (bmBc[A])[/math] после сравнения

Сдвигаемся на [math]2 (bmBc[G])[/math] после второго сравнения

Сдвигаемся на [math]2 (bmBc[G])[/math]

Сдвигаемся на [math]2 (bmBc[G])[/math] после всех сравнений

Сдвигаемся на [math]1 (bmBc[A])[/math]

Сдвигаемся на [math]8 (bmBc[T])[/math]

Сдвигаемся на [math]2 (bmBc[G])[/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.
• Raita algorithm
• Raita algorithm на англ вики