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