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