Изменения

'''Алгоритм Райта''' (англ. ''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>y</tex> с позиции <tex>\mathtt{fromIndex}</tex> и до <tex>\mathtt{toIndex}</tex> и <tex>x</tex> с начала и до конца совпадают: '''voidboolean''' RAITArestEquals('''char'''[] xy, '''int''' mfromIndex, '''char'''[] yx, '''int''' ntoIndex) {: '''intfor'''[] bmBc '''char''' c, firstCh, middleCh, lastCh;(i = fromIndex .. toIndex) '''if''' (m y[i] !== 0x[i - fromIndex]) '''return'''false '''else ifreturn''' true Стадия препроцессинга (m == 1совпадает со стадией препроцессинга в [[Алгоритм Бойера-Мура|алгоритме Бойера-Мура]]) {: <font color=green>//Проверка на случай поиска вхождения одного символа</font> '''int''' match = 0 [] preBmBc('''whilechar''' (match < n) { match = findFirst(y, match, n - 1, x[0]) x, '''ifint''' (match != -1m) {: '''printint'''(match) } [] result = '''elseint'''[ASIZE] '''print'''( <font color=green>"No matches"//Где ASIZE {{---}} размер алфавита</font>) '''returnfor'''(i = 0 .. ASIZE - 1) } } '''int''' findFirst('''char''' result[i] y, '''int''' fromIndex, '''int''' toIndex, '''char''' symbol){= m; '''for''' (i = fromIndex 0 .. toIndexm - 2){ '''if''' (y result[x[i]] == symbol){m - i - 1; '''return''' iresult } }Основная стадия алгоритма: '''returnvoid''' -1 } '''boolean''' restEqualsRAITA('''char'''[] yx, '''int''' fromIndexm, '''char'''[] xy, '''int''' toIndexn){: '''int'''[] bmBc '''forchar''' (i = fromIndex .. toIndex){c, firstCh, middleCh, lastCh; '''if''' (y[i] !m == x[i - fromIndex + 1]0){ '''return''' false } } '''returnelse if''' true }(m == 1) <font color=green> //Стадия препроцессингаПроверка на случай поиска вхождения одного символа</font> '''int'''[] preBmBc(match = 0 '''charwhile'''(match < n) match = findFirst(y, match, n - 1, x[0] x, '''int''' m) { '''intif'''[] result (match != -1) '''intprint'''[m](match) '''forelse''' (i = 0 .. m - 1){ result[i] = m; } '''forprint''' (i <font color= 0 .. m - 2green>"No matches"</font>){ result[x[i]] = m - i - 1; } '''return''' result } <font color=green>//Вычисление массива плохих сиволов и объявление первого, последнего и среднего сиволов</font> 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] && <font color=green>//Совпадение шаблона и окна из текста</font> restEquals(y, j + 1, x, j + m - 2)){ '''print'''(j) '''return''' } j += bmBc[c]; } '''print'''(<font color=green>"No matches"</font>) }

* Фаза препроцессинга требует <tex>O(m+ \sigma)</tex> времени и памяти, где <tex>\sigma</tex> {{---}} размер алфавита.

==ПримерСравнение с Алгоритмом Бойера-Мура==Пусть нам дана строка <tex>y = GCATCGCAGAGAGTATACAGTACG</tex> и образец <tex>x=GCAGAGAG</tex>[[Файл:RaitaComparing.png|350px|thumb|Right|Верхняя кривая {{---}} алгоритм Бойера-Мура, нижняя {{---}} Райта]]

[[Файл:RaitaPreВ своей статье Тим Райта экспериментально проверил ускорение алгоритма на реальных текстах.png|thumb|center|Массив Тесты были приведены в техническом отчете, написанном на английском языке. Длина текста составила <tex>29 550</tex> символов. Использовался '''ASCII''' алфавит (подразумевается теоритический размер алфавита, равный <tex>128</tex>, в тексте было использовано только <tex>bmBc85</tex> после фазы препроцессинга]]символов.) Шаблоны длиной <tex>2-20</tex> символов случайно выбирались из текста, а затем проходил их поиск в тексте. (См. рисунок)

[[Файл:Raita1Кроме того, производительность растет с увеличением <tex>m</tex>, поскольку вклад сравнений первого, последнего и среднего символа уменьшается.png|thumb|450px|center|Сдвигаемся С другой стороны, производительность ухудшается с уменьшением размера алфавита, поскольку вероятность того, что первый, средний и последний символ из шаблона и текста совпадут, увеличивается. Однако Тим Райта в своей статье пишет, что несмотря на теоритическую возможность ухудшения, на практике, скорее всего, разница будет заметна лишь на очень маленьких алфавитах (например, длины <tex>1 (bmBc[A])2</tex> после сравнения]]).

[[Файл:Raita2.png|thumb|450px|center|Сдвигаемся на ==Пример==Пусть нам дана строка <tex>2 (bmBc[G])y = GCATCGCAGAGAGTATACAGTACG</tex> и образец <tex>x=GCAGAGAG</tex> после второго сравнения]]

[[Файл:Raita3.png|thumb|450px|center|Сдвигаемся на Построим массив <tex>2 (bmBc[G])</tex>]]:

[[Файл:Raita4RaitaPre.png|thumb|450px|center|Сдвигаемся на <tex>2 (bmBc[G])</tex> после всех сравнений250px]]

[[ФайлРассмотрим шаги алгоритма:Raita5.png|thumb|450px|center|Сдвигаемся на <tex>1 (bmBc[A])</tex>]]

{| 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"|[[Файл:Raita6Raita3.png|thumb550px]]|450px<tex>(10, 2)</tex>|Последние символы совпали, сравниваем первые, сдвигаемся.|-align="center"|[[Файл:Raita4.png|550px]]|<tex>(12, 2)</tex>|Сдвигаемся Совпали последний, первый и средний символы, пробегаемся по всему шаблону и сравниваем символы. Нашли строчку в тексте. Продолжим работу (для примера, в обычном варианте на этом этапе мы можем выйти, если требуется найти только одно вхождение) и сдвинемся.|-align="center"|[[Файл:Raita5.png|550px]]|<tex>8 (bmBc14, 1)</tex>|Делаем сравнение последних символов, оно неудачно, сдвигаемся.|-align="center"|[[TФайл:Raita6.png|550px]]|<tex>(15, 8)</tex>|Делаем сравнение последних символов, оно неудачно, сдвигаемся.|-align="center"|[[Файл:Raita7.png|550px]]|<tex>(23, 2)</tex>|Последние символы совпали, сравниваем первые, сдвигаемся. Строка закончилась, выходим.|-|}

[[Файл:Raita7.png|thumb|450px|center|Сдвигаемся на В итоге, чтобы найти одно вхождение образца длиной <tex>m = 8</tex> в образце длиной <tex>n = 24</tex>, нам понадобилось <tex>2 (bmBc[G])18</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]* [https://en.wikipedia.org/wiki/Raita_algorithm Wikipedia {{---}} Raita algorithm на англ вики]* [http://www.di.ufpe.br/~paguso/courses/if767/bib/Raita_1992.pdf UFPE {{---}} Оригинальная статья]

[[Категория: Дискретная математика Алгоритмы и алгоритмыструктуры данных]]