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

Здесь вы можете просмотреть и скачать доклад по теме «Алгоритм Бойера - Мура», размещенный в категории «Устройства и комплектующие», который поможет вам успешно провести свое мероприятие или подготовиться к занятию.

Информация о презентации

Алгоритм Бойера - Мура
Раздел:Устройства и комплектующие
Слайдов:13
Слов:361
Символов:2513
Просмотров:40
Скачиваний:2
Загрузка:онлайн
Размер:141.50 kB
Тип:ppt / pptx для PowerPoint/Impress
Теги:#символ, #шаблон, #стоп, #совпа, #букв, #суффикс, #алгоритм, #сдвига, #таблиц, #поиск

Похожие презентации об устройстве и комплектующих

Готовые презентации об устройстве и комплектующих

Содержание слайда №1 (64 знака, 10 слов)

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

Содержание слайда №2 (238 знаков, 31 слово)

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

Содержание слайда №3 (122 знака, 16 слов)

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

Содержание слайда №4 (244 знака, 34 слова)

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

Содержание слайда №5 (193 знака, 32 слова)

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

Содержание слайда №6 (276 знаков, 41 слово)

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

Содержание слайда №7 (392 знака, 58 слов)

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

Содержание слайда №8 (327 знаков, 52 слова)

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

Содержание слайда №9 (181 знак, 27 слов)

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

Содержание слайда №10 (159 знаков, 22 слова)

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

Содержание слайда №11 (141 знак, 15 слов)

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

Содержание слайда №12 (156 знаков, 20 слов)

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

Содержание слайда №13 (20 знаков, 3 слова)

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