3622
правки
Изменения
м
→Сравнение с Алгоритмом Бойера-Мура
[[Файл:RaitaComparing.png|350px|thumb|Right|Верхняя кривая {{---}} алгоритм Бойера-Мура, нижняя {{---}} Райта]]
В своей статье Тим Райта экспериментально проверил ускорение алгоритма на реальных текстах. Тесты были приведены на в техническом отчете, написанном на английском языке. Длина текста составила <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> вносят наибольший вклад в быстродействие модификации. (В алгоритме Бойера-Мура мы будем идти с конца, пока не найдем различия, то есть произведем сравнение на всем суффиксе, в то время как в алгоритме Райта мы выйдем сразу после несовпадения первых символов).
