Изменения

'''Алгоритм Райта''' (англ. ''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>a</tex> и образец <tex>aa..baa</tex>. В таком случае, <tex>BmBc[a]</tex> будет равен <tex>1</tex>, то есть после каждой фазы сравнений мы будем сдвигаться на <tex>1</tex>. Значит, всего будет <tex>n</tex> фаз сравнений, а каждая фаза будет работать отработает за <tex>m - 2</tex>, поскольку расхождение будет только в <tex>3</tex> третьем с конца символе, то мы сравним сначала последний, потом первый, потом средний, а затем пойдем с самого начала, сравнивая все символы подряд. Итого получаем асимптотику <tex>O(m \cdot n)</tex>

'''Пример:''' текст, вида <tex>a..ba..ab..a</tex> и образец <tex>ba..ab</tex>. В таком случае, <tex>BmBc[b]</tex> будет равен <tex>m - 1</tex>. Значит, всего будет не более чем <tex>n / (m - 1)</tex> фаз сравнений, а каждая фаза (кроме той, в которой мы нашли вхождение строки) будет работать за <tex>1</tex>, поскольку расхождение будет уже в последних символах. Итого получаем асимптотику <tex > \Omega(n / m)</tex>

В своей статье Тим Райта экспериментально проверил ускорение алгоритма на реальных текстах. Тесты были приведены на в техническом отчете, написанном на английском языке. Длина текста составила <tex>29 550</tex> символов. Использовался '''ASCII''' алфавит (подразумевается теоритический размер алфавита, равный <tex>128</tex>, в тексте было использовано только <tex>85</tex> символов.) Шаблоны длиной <tex>2-20</tex> символов случайно выбирались из текста, а затем проходил их поиск в тексте. (См. рисунок)

Результат показывает ускорение модификации алгоритма на <tex>21-27\%</tex> относительно оригинального на всех шаблонах. Шаблон встречался в тексте как минимум один раз (из-за метода его выбора). Однако, результаты теста на шаблонах, которые не встречались в тексте, были очень похожи на верхнюю кривую. Очевидно, что шаблоны, имеющие часто встречающиеся суффиксы, такие как <tex>-ion</tex> или <tex>-ed</tex> вносят наибольший вклад в быстродействие модификации. (В алгоритме Бойера-Мура мы будем идти с конца, пока не найдем различия, то есть произведем сравнение на всем суффиксе, в то время как в алгоритме Райта мы выйдем сразу после несовпадения первых символов).

Кроме того, производительность растет с увеличением <tex>m</tex>, поскольку вклад сравнений первого, последнего и среднего символа уменьшается. С другой стороны, производительность ухудшается с уменьшением размера алфавита, поскольку вероятность того, что первый, средний и последний символ из шаблона и текста совпадут, увеличивается. Однако, Тим Райт Райта в своей статье пишет, что несмотря на теоритическую возможность ухудшения, на практике, скорее всего, разница будет заметна лишь на очень маленьких алфавитах (например, длины <tex>2</tex>).

|Делаем сравнение последних символовСравниванием последние символы, оно неудачноони неравны, поэтому сдвигаемся.

|Последние символы совпали, сравниваем первые, сдвигаемся. Строка закончилась, выхожимвыходим.

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