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

Категория: Устройства и комплектующие
Нажмите для полного просмотра!
Алгоритм Бойера - Мура, слайд №1Алгоритм Бойера - Мура, слайд №2Алгоритм Бойера - Мура, слайд №3Алгоритм Бойера - Мура, слайд №4Алгоритм Бойера - Мура, слайд №5Алгоритм Бойера - Мура, слайд №6Алгоритм Бойера - Мура, слайд №7Алгоритм Бойера - Мура, слайд №8Алгоритм Бойера - Мура, слайд №9Алгоритм Бойера - Мура, слайд №10Алгоритм Бойера - Мура, слайд №11Алгоритм Бойера - Мура, слайд №12Алгоритм Бойера - Мура, слайд №13
Скачать
Вы можете ознакомиться и скачать презентацию на тему Алгоритм Бойера - Мура. Доклад-сообщение содержит 13 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

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

Слайд 1


Алгоритм Бойера - Мура Применяется для поиска подстроки в строке
Описание слайда:
Алгоритм Бойера - Мура Применяется для поиска подстроки в строке

Слайд 2


История создания Алгоритм поиска строки Бойера — Мура, считается наиболее быстрым среди алгоритмов общего назначения, предназначенных для поиска подстроки в строке. Был разработан Робертом Бойером (англ.)русск. и Джеем Муром в 1977 году.
Описание слайда:
История создания Алгоритм поиска строки Бойера — Мура, считается наиболее быстрым среди алгоритмов общего назначения, предназначенных для поиска подстроки в строке. Был разработан Робертом Бойером (англ.)русск. и Джеем Муром в 1977 году.

Слайд 3


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

Слайд 4


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

Слайд 5


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

Слайд 6


Стоп - символ Предположим, что мы производим поиск слова «колокол». Первая же буква не совпала — «к» (назовём эту букву стоп-символом). Тогда можно сдвинуть шаблон вправо до последней его буквы «к». Если стоп-символа в шаблоне вообще нет, шаблон смещается за этот стоп-символ.
Описание слайда:
Стоп - символ Предположим, что мы производим поиск слова «колокол». Первая же буква не совпала — «к» (назовём эту букву стоп-символом). Тогда можно сдвинуть шаблон вправо до последней его буквы «к». Если стоп-символа в шаблоне вообще нет, шаблон смещается за этот стоп-символ.

Слайд 7


Стоп - символ В данном случае стоп-символ — «а», и шаблон сдвигается так, чтобы он оказался прямо за этой буквой. В алгоритме Бойера-Мура эвристика стоп-символа вообще не смотрит на совпавший суффикс, так что первая буква шаблона («к») окажется под «л», и будет проведена одна заведомо холостая проверка. Если стоп-символ «к» оказался за другой буквой «к», эвристика стоп-символа не работает.
Описание слайда:
Стоп - символ В данном случае стоп-символ — «а», и шаблон сдвигается так, чтобы он оказался прямо за этой буквой. В алгоритме Бойера-Мура эвристика стоп-символа вообще не смотрит на совпавший суффикс, так что первая буква шаблона («к») окажется под «л», и будет проведена одна заведомо холостая проверка. Если стоп-символ «к» оказался за другой буквой «к», эвристика стоп-символа не работает.

Слайд 8


Суффикс Если при сравнении строки и шаблона совпало 1 или больше символов, то шаблон сдвигается в зависимости от того, какой суффикс совпал В данном случае совпал суффикс «окол», и шаблон сдвигается вправо до ближайшего «окол». Если подстроки «окол» в шаблоне больше нет, но он начинается на «кол», сдвигается до «кол», и т. д.
Описание слайда:
Суффикс Если при сравнении строки и шаблона совпало 1 или больше символов, то шаблон сдвигается в зависимости от того, какой суффикс совпал В данном случае совпал суффикс «окол», и шаблон сдвигается вправо до ближайшего «окол». Если подстроки «окол» в шаблоне больше нет, но он начинается на «кол», сдвигается до «кол», и т. д.

Слайд 9


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

Слайд 10


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

Слайд 11


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

Слайд 12


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

Слайд 13


Спасибо за внимание!
Описание слайда:
Спасибо за внимание!

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию