Презентация на тему Алгоритм Бойера - Мура

Презентация на тему Алгоритм Бойера - Мура, предмет презентации: Шаблоны, картинки для презентаций. Этот материал содержит 11 слайдов. Красочные слайды и илюстрации помогут Вам заинтересовать свою аудиторию. Для просмотра воспользуйтесь проигрывателем, если материал оказался полезным для Вас - поделитесь им с друзьями с помощью социальных кнопок и добавьте наш сайт презентаций ThePresentation.ru в закладки!

Слайды и текст этой презентации

Слайд 1
Текст слайда:

Алгоритм Бойера - Мура

Применяется для поиска подстроки в строке


Слайд 2
Текст слайда:

Оценка сложности алгоритма

На непереодических шаблонах O(|haystack|+|needle|+|Σ|), на переодических O(|haystack|·|needle|+|Σ|)
haystack – исходная строка, needle –шаблон поиска, Σ – алфавит, на котором производится сравнение


Слайд 3
Текст слайда:

Основные идеи алгоритма

Сканирование слева направо, сравнение справа налево
Поиск стоп - символа
Поиск совпавшего суффикса


Слайд 4
Текст слайда:

Сканирование и сравнение

Совмещается начало строки и начало шаблона, проверка идет с последнего символа шаблона
Если символы совпадают, то производится сравнение предпоследнего символа шаблона и т.д.
Если все символы совпали, то образец найден


Слайд 5
Текст слайда:

Стоп - символ

Если с шаблоном не совпала первая сравниваемая буква, то сдвигаем шаблон вправо до последней такой же буквы
Если в шаблоне нет стоп – символа, то сдвигаем шаблон за стоп – символ.


Слайд 6
Текст слайда:

Суффикс

Если при сравнении строки и шаблона совпало 1 или больше символов, то шаблон сдвигается в зависимости от того, какой суффикс совпал


Слайд 7
Текст слайда:

Таблица стоп - символов

В таблице указывается последняя позиция элемента в шаблоне (за исключением последней буквы)
Если в шаблоне нет такого элемента то в таблицу записывается ноль


Слайд 8
Текст слайда:

Таблица суффиксов

Для каждого возможного суффикса в таблицу записывается наименьшая величина, на которую надо сдвинуть шаблон чтобы он снова совпал с суффиксом


Слайд 9
Текст слайда:

Достоинства алгоритма

Оптимален при отсутствии возможности провести предварительную обработку текста
Достаточно быстрый в большинстве случаев


Слайд 10
Текст слайда:

Недостатки алгоритма

На больших алфавитах таблица стоп – символов может занимать много памяти
На некоторых “неудачных” текстах его скорость сильно снижается


Слайд 11
Текст слайда:

Конец

Спасибо за внимание!


Обратная связь

Если не удалось найти и скачать презентацию, Вы можете заказать его на нашем сайте. Мы постараемся найти нужный Вам материал и отправим по электронной почте. Не стесняйтесь обращаться к нам, если у вас возникли вопросы или пожелания:

Email: Нажмите что бы посмотреть 

Что такое ThePresentation.ru?

Это сайт презентаций, докладов, проектов, шаблонов в формате PowerPoint. Мы помогаем школьникам, студентам, учителям, преподавателям хранить и обмениваться учебными материалами с другими пользователями.


Для правообладателей

Яндекс.Метрика