🗊Презентация Поиск подстрок

Категория: Устройства и комплектующие
Нажмите для полного просмотра!
Поиск подстрок, слайд №1Поиск подстрок, слайд №2Поиск подстрок, слайд №3Поиск подстрок, слайд №4Поиск подстрок, слайд №5Поиск подстрок, слайд №6Поиск подстрок, слайд №7Поиск подстрок, слайд №8Поиск подстрок, слайд №9Поиск подстрок, слайд №10Поиск подстрок, слайд №11Поиск подстрок, слайд №12Поиск подстрок, слайд №13Поиск подстрок, слайд №14Поиск подстрок, слайд №15Поиск подстрок, слайд №16Поиск подстрок, слайд №17Поиск подстрок, слайд №18Поиск подстрок, слайд №19Поиск подстрок, слайд №20Поиск подстрок, слайд №21Поиск подстрок, слайд №22Поиск подстрок, слайд №23Поиск подстрок, слайд №24Поиск подстрок, слайд №25Поиск подстрок, слайд №26Поиск подстрок, слайд №27Поиск подстрок, слайд №28Поиск подстрок, слайд №29Поиск подстрок, слайд №30Поиск подстрок, слайд №31Поиск подстрок, слайд №32Поиск подстрок, слайд №33Поиск подстрок, слайд №34Поиск подстрок, слайд №35Поиск подстрок, слайд №36Поиск подстрок, слайд №37Поиск подстрок, слайд №38Поиск подстрок, слайд №39Поиск подстрок, слайд №40Поиск подстрок, слайд №41Поиск подстрок, слайд №42Поиск подстрок, слайд №43Поиск подстрок, слайд №44Поиск подстрок, слайд №45Поиск подстрок, слайд №46Поиск подстрок, слайд №47Поиск подстрок, слайд №48Поиск подстрок, слайд №49Поиск подстрок, слайд №50Поиск подстрок, слайд №51Поиск подстрок, слайд №52Поиск подстрок, слайд №53Поиск подстрок, слайд №54Поиск подстрок, слайд №55Поиск подстрок, слайд №56Поиск подстрок, слайд №57
Скачать

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Поиск подстрок. Доклад-сообщение содержит 57 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

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

Слайд 1


Поиск подстрок
Описание слайда:
Поиск подстрок

Слайд 2


Определения Алфавит – конечное множество символов. Строка (слово) – это последовательность символов из некоторого алфавита. Длина строки – количество символов в строке. X=x[1]x[2]...x[n] – строка длинной n, где x[i] – i-ый символ строки Х, принадлежащий алфавиту. Строка, не содержащая ни одного символа, называется пустой.
Описание слайда:
Определения Алфавит – конечное множество символов. Строка (слово) – это последовательность символов из некоторого алфавита. Длина строки – количество символов в строке. X=x[1]x[2]...x[n] – строка длинной n, где x[i] – i-ый символ строки Х, принадлежащий алфавиту. Строка, не содержащая ни одного символа, называется пустой.

Слайд 3


Определения Строка X называется подстрокой строки Y, если найдутся такие строки Z1 и Z2, что Y=Z1XZ2. Подстрока X называется префиксом строки Y, если есть такая подстрока Z, что Y=XZ. Подстрока X называется суффиксом строки Y, если есть такая подстрока Z, что Y=ZX.
Описание слайда:
Определения Строка X называется подстрокой строки Y, если найдутся такие строки Z1 и Z2, что Y=Z1XZ2. Подстрока X называется префиксом строки Y, если есть такая подстрока Z, что Y=XZ. Подстрока X называется суффиксом строки Y, если есть такая подстрока Z, что Y=ZX.

Слайд 4


Постановка задачи Есть образец   и строка, надо определить индекс, начиная с которого образец   содержится в строке. Если   не содержится  — вернуть индекс, который не может быть интерпретирован как позиция в строке (например, отрицательное число). При необходимости отслеживать каждое вхождение образца в текст имеет смысл завести дополнительную функцию, вызываемую при каждом обнаружении образца.
Описание слайда:
Постановка задачи Есть образец   и строка, надо определить индекс, начиная с которого образец   содержится в строке. Если   не содержится  — вернуть индекс, который не может быть интерпретирован как позиция в строке (например, отрицательное число). При необходимости отслеживать каждое вхождение образца в текст имеет смысл завести дополнительную функцию, вызываемую при каждом обнаружении образца.

Слайд 5


Пример Дана последовательность символов x[1]..x[n]. Определить, встречаются ли в ней идущие друг за другом символы "abcd". (Другими словами, требуется выяснить, есть ли в слове x[1]..x[n] подслово "abcd".)
Описание слайда:
Пример Дана последовательность символов x[1]..x[n]. Определить, встречаются ли в ней идущие друг за другом символы "abcd". (Другими словами, требуется выяснить, есть ли в слове x[1]..x[n] подслово "abcd".)

Слайд 6


Простой алгоритм Решение. Имеется примерно n (если быть точным, n-3) позиций, на которых может находиться искомая подстрока в исходной строке. Для каждой из позиций можно проверить, действительно ли с нее начинается подстрока , сравнив четыре символа. Но обычно слово x[1]..x[n] просматривается слева направо, до появления буквы 'a'. Как только она появилась, ищем за ней букву 'b', затем 'c', и, наконец, 'd'. Если ожидания оправдываются, то слово "abcd" обнаружено. Если же какая-то из нужных букв не появляется, начинаем поиск с новой позиции.
Описание слайда:
Простой алгоритм Решение. Имеется примерно n (если быть точным, n-3) позиций, на которых может находиться искомая подстрока в исходной строке. Для каждой из позиций можно проверить, действительно ли с нее начинается подстрока , сравнив четыре символа. Но обычно слово x[1]..x[n] просматривается слева направо, до появления буквы 'a'. Как только она появилась, ищем за ней букву 'b', затем 'c', и, наконец, 'd'. Если ожидания оправдываются, то слово "abcd" обнаружено. Если же какая-то из нужных букв не появляется, начинаем поиск с новой позиции.

Слайд 7


Применение простого алгоритма
Описание слайда:
Применение простого алгоритма

Слайд 8


Алгоритм Рабина-Карпа Пусть алфавит D={0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, то есть каждый символ в алфавите есть d–ичная цифра, где d=│D│. Пример Образец имеет вид W = 3 1 4 1 5 Вычисляем значения чисел из окна длины |W|=5 по mod q, q — простое число.
Описание слайда:
Алгоритм Рабина-Карпа Пусть алфавит D={0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, то есть каждый символ в алфавите есть d–ичная цифра, где d=│D│. Пример Образец имеет вид W = 3 1 4 1 5 Вычисляем значения чисел из окна длины |W|=5 по mod q, q — простое число.

Слайд 9


Использование хеш-функции
Описание слайда:
Использование хеш-функции

Слайд 10


Хеш функция Ключ к производительности алгоритма Рабина — Карпа - низкая вероятность коллизий и эффективное вычисление значения хеш последовательных подстрок текста.  Рабин и Карп предложили использовать  полиномиальный хеш.
Описание слайда:
Хеш функция Ключ к производительности алгоритма Рабина — Карпа - низкая вероятность коллизий и эффективное вычисление значения хеш последовательных подстрок текста.  Рабин и Карп предложили использовать  полиномиальный хеш.

Слайд 11


Алгоритм Рабина-Карпа Для ускорения модульной арифметики q выбирают  равным степени двойки минус один (так называемые простые числа Мерсенна): для 32-х битовых машин лучше всего подходит q=2^{31}-1, для 64-х битовых —  q=2^{61}-1
Описание слайда:
Алгоритм Рабина-Карпа Для ускорения модульной арифметики q выбирают  равным степени двойки минус один (так называемые простые числа Мерсенна): для 32-х битовых машин лучше всего подходит q=2^{31}-1, для 64-х битовых —  q=2^{61}-1

Слайд 12


Алгоритм Рабина-Карпа Для быстрого вычисления р используют схему Горнера: P[1..m]- образец, р – число, которое является десятичной записью образца. p=P[m]+10(P[m-1]+10(P[m-2] + … + 10(P[2] + 10p[1])…))
Описание слайда:
Алгоритм Рабина-Карпа Для быстрого вычисления р используют схему Горнера: P[1..m]- образец, р – число, которое является десятичной записью образца. p=P[m]+10(P[m-1]+10(P[m-2] + … + 10(P[2] + 10p[1])…))

Слайд 13


Алгоритм Рабина-Карпа Т[1..n]- текст, ts – число, которое является десятичной записью T[s+1..s+m]. Если вычислено ts , ts+1 можно вычислить за О(1) ts+1 = 10(ts -10m-1 T[s+1])+T[s+m+1]
Описание слайда:
Алгоритм Рабина-Карпа Т[1..n]- текст, ts – число, которое является десятичной записью T[s+1..s+m]. Если вычислено ts , ts+1 можно вычислить за О(1) ts+1 = 10(ts -10m-1 T[s+1])+T[s+m+1]

Слайд 14


Алгоритм Рабина-Карпа n=length[T] m=length[P] h= dm-1 mod q p=0 t0 = 0 For i=1 to m {p= (d p +P[i]) mod q t0 = (d t0 +T[i]) mod q }
Описание слайда:
Алгоритм Рабина-Карпа n=length[T] m=length[P] h= dm-1 mod q p=0 t0 = 0 For i=1 to m {p= (d p +P[i]) mod q t0 = (d t0 +T[i]) mod q }

Слайд 15


Алгоритм Рабина-Карпа(продолжение) For s=0 to n-m { if p== ts if P[1..m]== T[s+1..s+m] print образец входит со сдвигом s; If s<n-m ts+1 = d(ts -h T[s+1])+T[s+m+1] mod q }
Описание слайда:
Алгоритм Рабина-Карпа(продолжение) For s=0 to n-m { if p== ts if P[1..m]== T[s+1..s+m] print образец входит со сдвигом s; If s<n-m ts+1 = d(ts -h T[s+1])+T[s+m+1] mod q }

Слайд 16


Временная сложность алгоритма Рабина-Карпа O(n)+O(mv), v – количество вхождений образца в текст
Описание слайда:
Временная сложность алгоритма Рабина-Карпа O(n)+O(mv), v – количество вхождений образца в текст

Слайд 17


Поиск подстрок с помощью конечных автоматов(abcd) при чтении слова x слева направо мы в каждый момент находимся в одном из следующих состояний: "начальное" (0), "сразу после a" (1), "сразу после ab" (2), "сразу после abc" (3) и "сразу после abcd" (4).
Описание слайда:
Поиск подстрок с помощью конечных автоматов(abcd) при чтении слова x слева направо мы в каждый момент находимся в одном из следующих состояний: "начальное" (0), "сразу после a" (1), "сразу после ab" (2), "сразу после abc" (3) и "сразу после abcd" (4).

Слайд 18


Конечные автоматы Читая очередную букву, мы переходим в следующее состояние по правилу: <Текущее состояние> <Очередная буква> <Новое состояние >
Описание слайда:
Конечные автоматы Читая очередную букву, мы переходим в следующее состояние по правилу: <Текущее состояние> <Очередная буква> <Новое состояние >

Слайд 19


Алгоритм состояние буква состояние 0 a 1 0 кроме a 0 1 b 2 1 a 1 1 кроме a,b 0 2 c 3 2 a 1 2 кроме a,c 0 3 d 4 3 a 1 3 кроме a,d 0 Состояние 4 - конечное
Описание слайда:
Алгоритм состояние буква состояние 0 a 1 0 кроме a 0 1 b 2 1 a 1 1 кроме a,b 0 2 c 3 2 a 1 2 кроме a,c 0 3 d 4 3 a 1 3 кроме a,d 0 Состояние 4 - конечное

Слайд 20


Фрагмент алгоритма1 i=1; state=0; {i - первая непрочитанная буква, state - состояние} while (i <> n+1) and (state <> 4) { if state ==0 { if x[i] == ‘a’ { state= 1; }
Описание слайда:
Фрагмент алгоритма1 i=1; state=0; {i - первая непрочитанная буква, state - состояние} while (i <> n+1) and (state <> 4) { if state ==0 { if x[i] == ‘a’ { state= 1; }

Слайд 21


Фрагмент алгоритма2 else { state= 0; } } else if state = 1 { if x[i] == ‘b’ { state= 2; } else if x[i] == ‘a’ { state= 1; }else
Описание слайда:
Фрагмент алгоритма2 else { state= 0; } } else if state = 1 { if x[i] == ‘b’ { state= 2; } else if x[i] == ‘a’ { state= 1; }else

Слайд 22


Фрагмент алгоритма3 { state= 0; } }else if state == 2 { if x[i] == ‘c’ { state= 3; } else if x[i] == ‘a’ { state= 1; } else { state= 0;}
Описание слайда:
Фрагмент алгоритма3 { state= 0; } }else if state == 2 { if x[i] == ‘c’ { state= 3; } else if x[i] == ‘a’ { state= 1; } else { state= 0;}

Слайд 23


Фрагмент алгоритма4 }else if state == 3 { if x[i] == ‘d’ { state= 4; } else if x[i] == ‘a’ { state= 1; } else { state= 0; } } } answer = (state = 4);
Описание слайда:
Фрагмент алгоритма4 }else if state == 3 { if x[i] == ‘d’ { state= 4; } else if x[i] == ‘a’ { state= 1; } else { state= 0; } } } answer = (state = 4);

Слайд 24


Усовершенствованный алгоритм Написать программу, которая ищет произвольный образец в произвольном слове. Это можно делать в два этапа: 1. сначала по образцу строится таблица переходов конечного автомата 2. читается входное слово и состояние преобразуется в соответствии с этой таблицей
Описание слайда:
Усовершенствованный алгоритм Написать программу, которая ищет произвольный образец в произвольном слове. Это можно делать в два этапа: 1. сначала по образцу строится таблица переходов конечного автомата 2. читается входное слово и состояние преобразуется в соответствии с этой таблицей

Слайд 25


Алгоритм Кнута - Морриса – Пратта (КМП) Работает за время O(m+n), где m – длина образца, n – длина текста Для произвольного слова X рассмотрим все его начала (префиксы), одновременно являющиеся его концами (суффиксами), и выберем из них самое длинное Примеры: l(aba)=a, l(abab)=ab, l(ababa)=aba, l(abc) = пустое слово.
Описание слайда:
Алгоритм Кнута - Морриса – Пратта (КМП) Работает за время O(m+n), где m – длина образца, n – длина текста Для произвольного слова X рассмотрим все его начала (префиксы), одновременно являющиеся его концами (суффиксами), и выберем из них самое длинное Примеры: l(aba)=a, l(abab)=ab, l(ababa)=aba, l(abc) = пустое слово.

Слайд 26


КМП Длина наиболее длинного префикса, являющегося одновременно суффиксом есть префикс-функция от строки. Префикс –функция заданного образца несет информацию о том, где в образце повторно встречаются различные префиксы образца. Использование этой информации позволяет избежать проверки заведомо недопустимых сдвигов.
Описание слайда:
КМП Длина наиболее длинного префикса, являющегося одновременно суффиксом есть префикс-функция от строки. Префикс –функция заданного образца несет информацию о том, где в образце повторно встречаются различные префиксы образца. Использование этой информации позволяет избежать проверки заведомо недопустимых сдвигов.

Слайд 27


π-функция Алгоритм вычисления Символы строк нумеруются с 1. Пусть π(S,i) = k. Попробуем вычислить префикс-функцию для i + 1. Если S[i + 1] = S[k + 1], то, естественно, π(S,i + 1) = k + 1. Если нет — пробуем меньшие суффиксы. Очевидно, что   также будет суффиксом строки, а для любого   строка   суффиксом не будет. Таким образом, получается алгоритм:
Описание слайда:
π-функция Алгоритм вычисления Символы строк нумеруются с 1. Пусть π(S,i) = k. Попробуем вычислить префикс-функцию для i + 1. Если S[i + 1] = S[k + 1], то, естественно, π(S,i + 1) = k + 1. Если нет — пробуем меньшие суффиксы. Очевидно, что   также будет суффиксом строки, а для любого   строка   суффиксом не будет. Таким образом, получается алгоритм:

Слайд 28


π-функция При S[i + 1] = S[k + 1] — положить π(S,i + 1) = k + 1. Иначе при k = 0 — положить π(S,i + 1) = 0. Иначе — установить k: = π(S,k), GOTO 1.
Описание слайда:
π-функция При S[i + 1] = S[k + 1] — положить π(S,i + 1) = k + 1. Иначе при k = 0 — положить π(S,i + 1) = 0. Иначе — установить k: = π(S,k), GOTO 1.

Слайд 29


Пример Для строки 'abcdabscabcdabia' вычисление будет таким: 'a'!='b' => π=0;(длина строки 2; строка ab ) 'a'!='c' => π=0; (длина строки 3; строка abс ) 'a'!='d' => π=0;(длина строки 4; строка abcd) 'a'=='a' => π=π+1=1; (длина строки 5; строка abcdа) 'b'=='b' => π=π+1=2;(длина строки 6; строка abcdаb) 'c'!='s' => π=0; (длина строки 6; строка abcdаbs) 'a'!='c' => π=0; (длина строки 7; строка abcdаbsс)
Описание слайда:
Пример Для строки 'abcdabscabcdabia' вычисление будет таким: 'a'!='b' => π=0;(длина строки 2; строка ab ) 'a'!='c' => π=0; (длина строки 3; строка abс ) 'a'!='d' => π=0;(длина строки 4; строка abcd) 'a'=='a' => π=π+1=1; (длина строки 5; строка abcdа) 'b'=='b' => π=π+1=2;(длина строки 6; строка abcdаb) 'c'!='s' => π=0; (длина строки 6; строка abcdаbs) 'a'!='c' => π=0; (длина строки 7; строка abcdаbsс)

Слайд 30


Пример 'a'=='a' => π=π+1=1; (длина строки 8; строка abcdаbsса) 'b'=='b' => π=π+1=2; (длина строки 9; строка abcdаbsсаb) 'c'=='c' => π=π+1=3; (длина строки 9; строка abcdаbsсаbс) 'd'=='d' => π=π+1=4;(длина строки 10; строка abcdаbsсаbсd) 'a'=='a' => π=π+1=5; (длина строки 10; строка abcdаbsсаbсdа) 'b'=='b' => π=π+1=6; (длина строки 11; строка abcdаbsсаbсdаb) ‘s'!='i' => π=0; (длина строки 12; строка abcdаbsсаbсdаbi) 'a'=='a' => π=π+1=1; (длина строки 13; строка abcdаbsсаbсdаbiа)
Описание слайда:
Пример 'a'=='a' => π=π+1=1; (длина строки 8; строка abcdаbsса) 'b'=='b' => π=π+1=2; (длина строки 9; строка abcdаbsсаb) 'c'=='c' => π=π+1=3; (длина строки 9; строка abcdаbsсаbс) 'd'=='d' => π=π+1=4;(длина строки 10; строка abcdаbsсаbсd) 'a'=='a' => π=π+1=5; (длина строки 10; строка abcdаbsсаbсdа) 'b'=='b' => π=π+1=6; (длина строки 11; строка abcdаbsсаbсdаb) ‘s'!='i' => π=0; (длина строки 12; строка abcdаbsсаbсdаbi) 'a'=='a' => π=π+1=1; (длина строки 13; строка abcdаbsсаbсdаbiа)

Слайд 31


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

Слайд 32


Алгоритм КМП-поиска После частичного совпадения начальной части образца W с соответствующими символами строки Т фактически известна пройденная часть строки и можно «вычислить» некоторые сведения (на основе самого образа W), с помощью которых далее быстро продвинемся по тексту.
Описание слайда:
Алгоритм КМП-поиска После частичного совпадения начальной части образца W с соответствующими символами строки Т фактически известна пройденная часть строки и можно «вычислить» некоторые сведения (на основе самого образа W), с помощью которых далее быстро продвинемся по тексту.

Слайд 33


Алгоритм КМП Идея КМП-поиска – при каждом несовпадении двух символов текста и образца образец сдвигается на все пройденное расстояние, так как меньшие сдвиги не могут привести к полному совпадению
Описание слайда:
Алгоритм КМП Идея КМП-поиска – при каждом несовпадении двух символов текста и образца образец сдвигается на все пройденное расстояние, так как меньшие сдвиги не могут привести к полному совпадению

Слайд 34


Z- функция Пусть ищется строка S1 в строке S2. Построим строку S= S1$S2, где $ — символ, не встречающийся ни в S1, ни в S2. Далее вычислим значения префикс-функции от строки S и всех её префиксов. Теперь, если префикс-функция от префикса строки S длины i равна n, где n—длина S1, и i>n, то в строке S2есть вхождение S1, начиная с позиции i-2n.
Описание слайда:
Z- функция Пусть ищется строка S1 в строке S2. Построим строку S= S1$S2, где $ — символ, не встречающийся ни в S1, ни в S2. Далее вычислим значения префикс-функции от строки S и всех её префиксов. Теперь, если префикс-функция от префикса строки S длины i равна n, где n—длина S1, и i>n, то в строке S2есть вхождение S1, начиная с позиции i-2n.

Слайд 35


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

Слайд 36


Описание алгоритма. Алгоритм основан на трёх идеях Сканирование слева направо, сравнение справа налево.  2. Эвристика стоп-символа.  3. Эвристика совпавшего суффикса. 
Описание слайда:
Описание алгоритма. Алгоритм основан на трёх идеях Сканирование слева направо, сравнение справа налево.  2. Эвристика стоп-символа.  3. Эвристика совпавшего суффикса. 

Слайд 37


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

Слайд 38


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

Слайд 39


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

Слайд 40


Эвристика стоп-символа.  Если стоп-символа в шаблоне вообще нет, шаблон смещается за этот стоп-символ. Строка: * * * * * * а л * * * * * * * * Шаблон: к о л о к о л Следующий шаг: к о л о к о л В данном случае стоп-символ — «а»,
Описание слайда:
Эвристика стоп-символа.  Если стоп-символа в шаблоне вообще нет, шаблон смещается за этот стоп-символ. Строка: * * * * * * а л * * * * * * * * Шаблон: к о л о к о л Следующий шаг: к о л о к о л В данном случае стоп-символ — «а»,

Слайд 41


Эвристика стоп-символа.  Если стоп-символ «к» оказался за другой буквой «к», эвристика стоп-символа не работает Строка: * * * * к к о л * * * * * Шаблон: к о л о к о л Следующий шаг: к о л о к о л ????? В таких ситуациях выручает третья идея алгоритма— эвристика совпавшего суффикса.
Описание слайда:
Эвристика стоп-символа.  Если стоп-символ «к» оказался за другой буквой «к», эвристика стоп-символа не работает Строка: * * * * к к о л * * * * * Шаблон: к о л о к о л Следующий шаг: к о л о к о л ????? В таких ситуациях выручает третья идея алгоритма— эвристика совпавшего суффикса.

Слайд 42


Эвристика совпавшего суффикса Если при сравнении строки и шаблона совпало один или больше символов, шаблон сдвигается в зависимости от совпавшего суффикса Строка: * * * т о к о л * * * * * Шаблон: к о л о к о л Следующий шаг: к о л о к о л
Описание слайда:
Эвристика совпавшего суффикса Если при сравнении строки и шаблона совпало один или больше символов, шаблон сдвигается в зависимости от совпавшего суффикса Строка: * * * т о к о л * * * * * Шаблон: к о л о к о л Следующий шаг: к о л о к о л

Слайд 43


Алгоритм Бойера —Мура Обе эвристики требуют предварительных вычислений. По шаблону поиска заполняются две таблицы. Таблица стоп-символов по размеру соответствует алфавиту (для алфавита из 256 символов, её длина 256); Таблица суффиксов соответствует шаблону.
Описание слайда:
Алгоритм Бойера —Мура Обе эвристики требуют предварительных вычислений. По шаблону поиска заполняются две таблицы. Таблица стоп-символов по размеру соответствует алфавиту (для алфавита из 256 символов, её длина 256); Таблица суффиксов соответствует шаблону.

Слайд 44


Таблица стоп-символов В таблице стоп-символов указывается последняя позиция в образце (исключая последнюю букву) каждого из символов алфавита. Для символов, не вошедших в  образец, пишем 0 (для нумерации с 0 — соответственно, −1).
Описание слайда:
Таблица стоп-символов В таблице стоп-символов указывается последняя позиция в образце (исключая последнюю букву) каждого из символов алфавита. Для символов, не вошедших в  образец, пишем 0 (для нумерации с 0 — соответственно, −1).

Слайд 45


Таблица стоп-символов образец =«abcdadcd» Символ a b c d [остальные] Последняя позиция 5 2 7 6 0 Обратите внимание, для стоп-символа «d» последняя позиция будет 6, а не 8 — последняя буква не учитывается При несовпадении в позиции i по стоп-символу c, сдвиг будет i-StopTable[c].
Описание слайда:
Таблица стоп-символов образец =«abcdadcd» Символ a b c d [остальные] Последняя позиция 5 2 7 6 0 Обратите внимание, для стоп-символа «d» последняя позиция будет 6, а не 8 — последняя буква не учитывается При несовпадении в позиции i по стоп-символу c, сдвиг будет i-StopTable[c].

Слайд 46


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

Слайд 47


Таблица суффиксов Например, для «abcdadcd» Суффикс [пустой] d cd dcd ... abcdadcd Сдвиг 1 2 4 8 ... 8 Иллюстрация было ? ?d ?cd ?dcd ... abcdadcd стало abcdadcd abcdadcd abcdadcd abcdadcd ... abcdadcd
Описание слайда:
Таблица суффиксов Например, для «abcdadcd» Суффикс [пустой] d cd dcd ... abcdadcd Сдвиг 1 2 4 8 ... 8 Иллюстрация было ? ?d ?cd ?dcd ... abcdadcd стало abcdadcd abcdadcd abcdadcd abcdadcd ... abcdadcd

Слайд 48


Таблица суффиксов Если шаблон начинается и заканчивается одной и той же комбинацией букв, |шаблон| вообще не появится в таблице. Например, для шаблон =«колокол» для всех суффиксов (кроме пустого) сдвиг будет равен 4.
Описание слайда:
Таблица суффиксов Если шаблон начинается и заканчивается одной и той же комбинацией букв, |шаблон| вообще не появится в таблице. Например, для шаблон =«колокол» для всех суффиксов (кроме пустого) сдвиг будет равен 4.

Слайд 49


Быстрый алгоритм вычисления таблицы суффиксов Использует  префикс-функцию  строки m = length(suff) pi[] = префикс-функция(suff) pi1[] = префикс-функция(обращение(suff)) for j=0..m suffshift[j] = m - pi[m] for i=1..m j = m - pi1[i] suffshift[j] = min(suffshift[j], i - pi1[i])
Описание слайда:
Быстрый алгоритм вычисления таблицы суффиксов Использует  префикс-функцию  строки m = length(suff) pi[] = префикс-функция(suff) pi1[] = префикс-функция(обращение(suff)) for j=0..m suffshift[j] = m - pi[m] for i=1..m j = m - pi1[i] suffshift[j] = min(suffshift[j], i - pi1[i])

Слайд 50


Быстрый алгоритм вычисления таблицы суффиксов  suffshift[0] соответствует всей совпавшей строке;  suffshift[m] — пустому суффиксу. Так как префикс-функция вычисляется за O(|шаблон|) операций, вычислительная сложность этого шага также равняется  O(|шаблон|)
Описание слайда:
Быстрый алгоритм вычисления таблицы суффиксов  suffshift[0] соответствует всей совпавшей строке;  suffshift[m] — пустому суффиксу. Так как префикс-функция вычисляется за O(|шаблон|) операций, вычислительная сложность этого шага также равняется  O(|шаблон|)

Слайд 51


Пример работы алгоритма БМ Искомый шаблон — «abbad». Таблица стоп-символов: Символ a b [остальные] Позиция 4 3 0 Таблица суффиксов для всех возможных суффиксов (кроме пустого) даёт максимальный сдвиг — 5
Описание слайда:
Пример работы алгоритма БМ Искомый шаблон — «abbad». Таблица стоп-символов: Символ a b [остальные] Позиция 4 3 0 Таблица суффиксов для всех возможных суффиксов (кроме пустого) даёт максимальный сдвиг — 5

Слайд 52


Пример работы алгоритма БМ Накладываем образец на строку. abeccaabadbabbad abbad Совпадения суффикса нет — таблица суффиксов даёт сдвиг на одну позицию. Для несовпавшего символа исходной строки «с» (5-я позиция) в таблице стоп-символов записан 0. Сдвигаем образец вправо на 5-0=5 позиций
Описание слайда:
Пример работы алгоритма БМ Накладываем образец на строку. abeccaabadbabbad abbad Совпадения суффикса нет — таблица суффиксов даёт сдвиг на одну позицию. Для несовпавшего символа исходной строки «с» (5-я позиция) в таблице стоп-символов записан 0. Сдвигаем образец вправо на 5-0=5 позиций

Слайд 53


Пример работы алгоритма БМ аbeccaabadbabbad abbad Символы 3—5 совпали, а второй — нет. Эвристика стоп-символа для «а» не работает (2-4=-2). Часть символов совпала, используем эвристику совпавшего суффикса. Шаблон сдвигается на пять позиций!
Описание слайда:
Пример работы алгоритма БМ аbeccaabadbabbad abbad Символы 3—5 совпали, а второй — нет. Эвристика стоп-символа для «а» не работает (2-4=-2). Часть символов совпала, используем эвристику совпавшего суффикса. Шаблон сдвигается на пять позиций!

Слайд 54


Пример работы алгоритма БМ аbeccaabadbabbad abbad Совпадения суффикса нет. По таблице стоп-символов сдвигаем образец на 1 позицию и получаем искомое вхождение образца: аbeccaabadbabbad abbad
Описание слайда:
Пример работы алгоритма БМ аbeccaabadbabbad abbad Совпадения суффикса нет. По таблице стоп-символов сдвигаем образец на 1 позицию и получаем искомое вхождение образца: аbeccaabadbabbad abbad

Слайд 55


Алгоритм Бойера-Мура Достоинства Алгоритм Бойера-Мура на «хороших» данных очень быстр, а вероятность появления «плохих» данных крайне мала. Поэтому он оптимален в большинстве случаев, когда нет возможности провести предварительную обработку текста На коротких текстах выигрыш не оправдывает предварительных вычислений.
Описание слайда:
Алгоритм Бойера-Мура Достоинства Алгоритм Бойера-Мура на «хороших» данных очень быстр, а вероятность появления «плохих» данных крайне мала. Поэтому он оптимален в большинстве случаев, когда нет возможности провести предварительную обработку текста На коротких текстах выигрыш не оправдывает предварительных вычислений.

Слайд 56


Алгоритм Бойера-Мура Недостатки не расширяются до приблизительного поиска, поиска любой строки из нескольких. Не рекомендуют использовать алгоритм, если текст изменяется редко. На больших алфавитах таблица стоп-символов может занимать много памяти. В таких используют спец. методы хранения таблиц
Описание слайда:
Алгоритм Бойера-Мура Недостатки не расширяются до приблизительного поиска, поиска любой строки из нескольких. Не рекомендуют использовать алгоритм, если текст изменяется редко. На больших алфавитах таблица стоп-символов может занимать много памяти. В таких используют спец. методы хранения таблиц

Слайд 57


Алгоритм Бойера-Мура На искусственно подобранных «неудачных» текстах (например, шаблон=«колоколоколоколоколокол») скорость алгоритма Бойера-Мура серьёзно снижается
Описание слайда:
Алгоритм Бойера-Мура На искусственно подобранных «неудачных» текстах (например, шаблон=«колоколоколоколоколокол») скорость алгоритма Бойера-Мура серьёзно снижается

Скачать

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