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