Понравилась презентация – покажи это...
Слайд 0
Алгоритм Бойера - Мура
Применяется для поиска подстроки в строке
Слайд 1
Оценка сложности алгоритма
На непереодических шаблонах O(|haystack|+|needle|+|?|), на переодических O(|haystack|·|needle|+|?|)
haystack – исходная строка, needle –шаблон поиска, ? – алфавит, на котором производится сравнение
Слайд 2
Основные идеи алгоритма
Сканирование слева направо, сравнение справа налево
Поиск стоп - символа
Поиск совпавшего суффикса
Слайд 3
Сканирование и сравнение
Совмещается начало строки и начало шаблона, проверка идет с последнего символа шаблона
Если символы совпадают, то производится сравнение предпоследнего символа шаблона и т.д.
Если все символы совпали, то образец найден
Слайд 4
Стоп - символ
Если с шаблоном не совпала первая сравниваемая буква, то сдвигаем шаблон вправо до последней такой же буквы
Если в шаблоне нет стоп – символа, то сдвигаем шаблон за стоп – символ.
Слайд 5
Суффикс
Если при сравнении строки и шаблона совпало 1 или больше символов, то шаблон сдвигается в зависимости от того, какой суффикс совпал
Слайд 6
Таблица стоп - символов
В таблице указывается последняя позиция элемента в шаблоне (за исключением последней буквы)
Если в шаблоне нет такого элемента то в таблицу записывается ноль
Слайд 7
Таблица суффиксов
Для каждого возможного суффикса в таблицу записывается наименьшая величина, на которую надо сдвинуть шаблон чтобы он снова совпал с суффиксом
Слайд 8
Достоинства алгоритма
Оптимален при отсутствии возможности провести предварительную обработку текста
Достаточно быстрый в большинстве случаев
Слайд 9
Недостатки алгоритма
На больших алфавитах таблица стоп – символов может занимать много памяти
На некоторых “неудачных” текстах его скорость сильно снижается
Слайд 10
Конец
Спасибо за внимание!