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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Описание алгоритма)
(Пример)
Строка 84: Строка 84:
 
[[Файл:RaitaPre.png|thumb|center|Массив <tex>bmBc</tex> после фазы препроцессинга]]
 
[[Файл:RaitaPre.png|thumb|center|Массив <tex>bmBc</tex> после фазы препроцессинга]]
  
 
+
{| class = "wikitable"
[[Файл:Raita1.png|thumb|450px|center|Сдвигаемся на <tex>1 (bmBc[A])</tex> после сравнения]]
+
! Изображение !! <tex>(j, bmBc[y[j]])</tex> !! Описание
 
+
|-align="center"
[[Файл:Raita2.png|thumb|450px|center|Сдвигаемся на <tex>2 (bmBc[G])</tex> после второго сравнения]]
+
|[[Файл:Raita1.png|500px]]
 
+
|<tex>(7, 1)</tex>
[[Файл:Raita3.png|thumb|450px|center|Сдвигаемся на <tex>2 (bmBc[G])</tex>]]
+
|Делаем сравнение последних символов, оно неудачно, сдвигаемся.
 
+
|-align="center"
[[Файл:Raita4.png|thumb|450px|center|Сдвигаемся на <tex>2 (bmBc[G])</tex> после всех сравнений]]
+
|[[Файл:Raita2.png|500px]]
 
+
|<tex>(8, 2)</tex>
[[Файл:Raita5.png|thumb|450px|center|Сдвигаемся на <tex>1 (bmBc[A])</tex>]]
+
|Последние символы совпали, сравниваем первые, сдвигаемся.
 
+
|-align="center"
[[Файл:Raita6.png|thumb|450px|center|Сдвигаемся на <tex>8 (bmBc[T])</tex>]]
+
|[[Файл:Raita3.png|500px]]
 
+
|<tex>(10, 2)</tex>
[[Файл:Raita7.png|thumb|450px|center|Сдвигаемся на <tex>2 (bmBc[G])</tex>]]
+
|Последние символы совпали, сравниваем первые, сдвигаемся.
 +
|-align="center"
 +
|[[Файл:Raita4.png|500px]]
 +
|<tex>(12, 2)</tex>
 +
|Совпали последний, первый и средний символы, пробегаемся по всему шаблону и сравниваем символы. Нашли строчку в тексте. Продолжим работу (для примера, в обычном варианте на этом этапе мы можем выйти, если требуется найти только одно вхождение) и сдвинемся.
 +
|-align="center"
 +
|[[Файл:Raita5.png|500px]]
 +
|<tex>(14, 1)</tex>
 +
|Делаем сравнение последних символов, оно неудачно, сдвигаемся.
 +
|-align="center"
 +
|[[Файл:Raita6.png|500px]]
 +
|<tex>(15, 8)</tex>
 +
|Делаем сравнение последних символов, оно неудачно, сдвигаемся.
 +
|-align="center"
 +
|[[Файл:Raita7.png|500px]]
 +
|<tex>(23, 2)</tex>
 +
|Последние символы совпали, сравниваем первые, сдвигаемся. Строка закончилась, выхожим.
 +
|-
 +
|}
  
 
В итоге, чтобы найти одно вхождение образца длиной <tex>m = 8</tex> в образце длиной <tex>n = 24</tex> нам понадобилось <tex>18</tex> сравнений символов
 
В итоге, чтобы найти одно вхождение образца длиной <tex>m = 8</tex> в образце длиной <tex>n = 24</tex> нам понадобилось <tex>18</tex> сравнений символов

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

Алгоритм Райта — алгоритм поиска подстроки в строке, который опубликовал Тим Райта в 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](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] сравнений символов

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