Алгоритм Райта
Алгоритм Райта (англ. Raita algorithm) — алгоритм поиска подстроки в строке, который опубликовал Тим Райта в 1991 году, являющийся модификацией алгоритма Бойера-Мура и улучшающий его асимптотику.
Содержание
Описание алгоритма
Алгоритм Райта ищет образец в заданном тексте , сравнивания их символы. Окном текста будем называть последовательность символов , где — длина образца . Сравнение происходит в следующем порядке:
- Последний символ образца сравнивается с самым правым символом окна.
- Если они совпадают, то первый символ сравнивается с самым левым символом окна.
- Если они опять совпали, то сравниваются символы, находящиеся в середине образца и окна.
Если все шаги прошли успешно, то начинаем сравнивать образец и текст посимвольно в обычном порядке, начиная с второго с конца символа. В противном случае вызываем функцию выполнения сдвига плохого символа, которая отработала в стадии препроцессинга. Эта функция аналогична той, которая была использована в фазе препроцессинга алгоритма Бойера-Мура. Кроме того, в третьем шаге, в зависимости от специфики текста, можно брать не средний символ, а случайный, либо с каким-то определенным индексом.
Псевдокод
Функция поиска индекса первого вхождения сивола в массиве с позиции до позиции :
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])
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")
Асимптотика
- Фаза препроцессинга требует времени и памяти, где — размер алфавита.
- В худшем случае поиск требует сравнений.
Пример: текст, состоящий только из букв и образец . В таком случае будет равен , то есть после каждой фазы сравнений мы будем сдвигаться на . Значит, всего будет фаз сравнений, а каждая фаза отработает за , поскольку расхождение будет только в третьем с конца символе, то мы сравним сначала последний, потом первый, потом средний, а затем пойдем с самого начала, сравнивая все символы подряд. Итого получаем асимптотику
- В лучшем случае требует сравнений.
Пример: текст вида и образец . В таком случае будет равен . Значит, всего будет не более чем фаз сравнений, а каждая фаза (кроме той, в которой мы нашли вхождение строки) будет работать за , поскольку расхождение будет уже в последних символах. Итого получаем асимптотику
Сравнение с Алгоритмом Бойера-Мура
В своей статье Тим Райта экспериментально проверил ускорение алгоритма на реальных текстах. Тесты были приведены в техническом отчете, написанном на английском языке. Длина текста составила символов. Использовался ASCII алфавит (подразумевается теоритический размер алфавита, равный , в тексте было использовано только символов.) Шаблоны длиной символов случайно выбирались из текста, а затем проходил их поиск в тексте. (См. рисунок)
Результат показывает ускорение модификации алгоритма на относительно оригинального на всех шаблонах. Шаблон встречался в тексте как минимум один раз (из-за метода его выбора). Однако, результаты теста на шаблонах, которые не встречались в тексте, были очень похожи на верхнюю кривую. Очевидно, что шаблоны, имеющие часто встречающиеся суффиксы, такие как или вносят наибольший вклад в быстродействие модификации. (В алгоритме Бойера-Мура мы будем идти с конца, пока не найдем различия, то есть произведем сравнение на всем суффиксе, в то время как в алгоритме Райта мы выйдем сразу после несовпадения первых символов).
Кроме того, производительность растет с увеличением , поскольку вклад сравнений первого, последнего и среднего символа уменьшается. С другой стороны, производительность ухудшается с уменьшением размера алфавита, поскольку вероятность того, что первый, средний и последний символ из шаблона и текста совпадут, увеличивается. Однако Тим Райта в своей статье пишет, что несмотря на теоритическую возможность ухудшения, на практике, скорее всего, разница будет заметна лишь на очень маленьких алфавитах (например, длины ).
Пример
Пусть нам дана строка и образец
Построим массив :
Рассмотрим шаги алгоритма:
| Изображение | Описание | |
|---|---|---|
|
Сравниванием последние символы, они неравны, поэтому сдвигаемся. | |
|
Последние символы совпали, сравниваем первые, сдвигаемся. | |
|
Последние символы совпали, сравниваем первые, сдвигаемся. | |
|
Совпали последний, первый и средний символы, пробегаемся по всему шаблону и сравниваем символы. Нашли строчку в тексте. Продолжим работу (для примера, в обычном варианте на этом этапе мы можем выйти, если требуется найти только одно вхождение) и сдвинемся. | |
|
Делаем сравнение последних символов, оно неудачно, сдвигаемся. | |
|
Делаем сравнение последних символов, оно неудачно, сдвигаемся. | |
|
Последние символы совпали, сравниваем первые, сдвигаемся. Строка закончилась, выходим. |
В итоге, чтобы найти одно вхождение образца длиной в образце длиной , нам понадобилось сравнений символов.
