Презентация Поиск подстрок онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Поиск подстрок абсолютно бесплатно. Урок-презентация на эту тему содержит всего 57 слайдов. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:57 слайдов
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:281.00 kB
- Просмотров:73
- Скачиваний:0
- Автор:неизвестен
Слайды и текст к этой презентации:
№1 слайд
Содержание слайда: Поиск подстрок
№2 слайд
Содержание слайда: Определения
Алфавит – конечное множество символов.
Строка (слово) – это последовательность символов из некоторого алфавита. Длина строки – количество символов в строке.
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.
№4 слайд
Содержание слайда: Постановка задачи
Есть образец и строка, надо определить индекс, начиная с которого образец содержится в строке. Если не содержится — вернуть индекс, который не может быть интерпретирован как позиция в строке (например, отрицательное число).
При необходимости отслеживать каждое вхождение образца в текст имеет смысл завести дополнительную функцию, вызываемую при каждом обнаружении образца.
№5 слайд
Содержание слайда: Пример
Дана последовательность символов x[1]..x[n]. Определить, встречаются ли в ней идущие друг за другом символы "abcd".
(Другими словами, требуется выяснить, есть ли в слове x[1]..x[n]
подслово "abcd".)
№6 слайд
Содержание слайда: Простой алгоритм
Решение. Имеется примерно 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 — простое число.
№9 слайд
Содержание слайда: Использование хеш-функции
№10 слайд
Содержание слайда: Хеш функция
Ключ к производительности алгоритма Рабина — Карпа - низкая вероятность коллизий и эффективное вычисление значения хеш последовательных подстрок текста.
Рабин и Карп предложили использовать полиномиальный хеш.
№11 слайд
Содержание слайда: Алгоритм Рабина-Карпа
Для ускорения модульной арифметики 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])…))
№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]
№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
}
№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
}
№16 слайд
Содержание слайда: Временная сложность алгоритма Рабина-Карпа
O(n)+O(mv),
v – количество вхождений образца в текст
№17 слайд
Содержание слайда: Поиск подстрок с помощью конечных автоматов(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 - конечное
№20 слайд
Содержание слайда: Фрагмент алгоритма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
№22 слайд
Содержание слайда: Фрагмент алгоритма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);
№24 слайд
Содержание слайда: Усовершенствованный алгоритм
Написать программу, которая ищет произвольный образец в произвольном слове. Это можно делать в два этапа:
1. сначала по образцу строится таблица переходов конечного автомата
2. читается входное слово и состояние преобразуется в соответствии с этой таблицей
№25 слайд
Содержание слайда: Алгоритм Кнута - Морриса – Пратта (КМП)
Работает за время 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. Если нет — пробуем меньшие суффиксы. Очевидно, что также будет суффиксом строки, а для любого строка суффиксом не будет. Таким образом, получается алгоритм:
№28 слайд
Содержание слайда: π-функция
При 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с)
№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а)
№31 слайд
Содержание слайда: Пример реализации
Пример.
(Символы, подвергшиеся сравнению, подчеркнуты.)
№32 слайд
Содержание слайда: Алгоритм КМП-поиска
После частичного совпадения начальной части образца W с соответствующими символами строки Т фактически известна пройденная часть строки и можно «вычислить» некоторые сведения (на основе самого образа W), с помощью которых далее быстро продвинемся по тексту.
№33 слайд
Содержание слайда: Алгоритм КМП
Идея КМП-поиска – при каждом несовпадении двух символов текста и образца образец сдвигается на все пройденное расстояние, так как меньшие сдвиги не могут привести к полному совпадению
№34 слайд
Содержание слайда: Z- функция
Пусть ищется строка S1 в строке S2. Построим строку S= S1$S2, где $ — символ, не встречающийся ни в S1, ни в S2. Далее вычислим значения префикс-функции от строки S и всех её префиксов. Теперь, если префикс-функция от префикса строки S длины i равна n, где n—длина S1, и i>n, то в строке S2есть вхождение S1, начиная с позиции i-2n.
№35 слайд
Содержание слайда: Алгоритм поиска строки Бойера —Мура
Был разработан Робертом Бойером и и Джеем Муром в 1977г.
Считается наиболее быстрым среди алгоритмов общего назначения, предназначенных для поиска подстроки в строке.
Общая оценка вычислительной сложности алгоритма О(длтекста+длобразца+мощню алф)
№36 слайд
Содержание слайда: Описание алгоритма.
Алгоритм основан на трёх идеях
Сканирование слева направо, сравнение справа налево.
2. Эвристика стоп-символа.
3. Эвристика совпавшего суффикса.
№37 слайд
Содержание слайда: Сканирование слева направо, сравнение справа налево.
Совмещается начало текста (строки) и шаблона, проверка начинается с последнего символа шаблона. Если символы совпадают, производится сравнение предпоследнего символа шаблона и т. д. Если все символы шаблона совпали с символами строки, значит, подстрока найдена, и поиск окончен.
№38 слайд
Содержание слайда: Сканирование слева направо, сравнение справа налево
Если какой-то символ шаблона не совпадает с соответствующим символом строки, шаблон сдвигается на несколько символов вправо, и проверка снова начинается с последнего символа.
Количество символов, на которые выполняется сдвиг, вычисляется по двум эвристикам
№39 слайд
Содержание слайда: Эвристика стоп-символа.
Пример: поиск слова «колокол».
Пусть первая же буква не совпала — «к» (назовём эту букву стоп-символом).
Можно сдвинуть шаблон вправо до последней буквы «к».
Строка: * * * * * * * к * * * * *
Шаблон: к о л о к о л
Следующий шаг: к о л о к о л
№40 слайд
Содержание слайда: Эвристика стоп-символа.
Если стоп-символа в шаблоне вообще нет, шаблон смещается за этот стоп-символ.
Строка: * * * * * * а л * * * * * * * *
Шаблон: к о л о к о л
Следующий шаг: к о л о к о л
В данном случае стоп-символ — «а»,
№41 слайд
Содержание слайда: Эвристика стоп-символа.
Если стоп-символ «к» оказался за другой буквой «к», эвристика стоп-символа не работает
Строка: * * * * к к о л * * * * *
Шаблон: к о л о к о л
Следующий шаг: к о л о к о л ?????
В таких ситуациях выручает третья идея алгоритма— эвристика совпавшего суффикса.
№42 слайд
Содержание слайда: Эвристика совпавшего суффикса
Если при сравнении строки и шаблона совпало один или больше символов, шаблон сдвигается в зависимости от совпавшего суффикса
Строка: * * * т о к о л * * * * *
Шаблон: к о л о к о л
Следующий шаг: к о л о к о л
№43 слайд
Содержание слайда: Алгоритм Бойера —Мура
Обе эвристики требуют предварительных вычислений.
По шаблону поиска заполняются две таблицы.
Таблица стоп-символов по размеру соответствует алфавиту (для алфавита из 256 символов, её длина 256);
Таблица суффиксов соответствует шаблону.
№44 слайд
Содержание слайда: Таблица стоп-символов
В таблице стоп-символов указывается последняя позиция в образце (исключая последнюю букву) каждого из символов алфавита. Для символов, не вошедших в образец, пишем 0 (для нумерации с 0 — соответственно, −1).
№45 слайд
Содержание слайда: Таблица стоп-символов
образец =«abcdadcd»
Символ a b c d [остальные]
Последняя позиция 5 2 7 6 0
Обратите внимание, для стоп-символа «d» последняя позиция будет 6, а не 8 — последняя буква не учитывается
При несовпадении в позиции i по стоп-символу c, сдвиг будет i-StopTable[c].
№46 слайд
Содержание слайда: Таблица суффиксов
Для каждого возможного суффикса S шаблона указывается наименьшая величина, на которую нужно сдвинуть вправо шаблон, чтобы он снова совпал с S. Если такой сдвиг невозможен, ставится длина шаблона(в обеих системах нумерации).
№47 слайд
Содержание слайда: Таблица суффиксов
Например, для «abcdadcd»
Суффикс
[пустой] d cd dcd ... abcdadcd
Сдвиг 1 2 4 8 ... 8
Иллюстрация
было ? ?d ?cd ?dcd ... abcdadcd
стало abcdadcd abcdadcd abcdadcd abcdadcd ... abcdadcd
№48 слайд
Содержание слайда: Таблица суффиксов
Если шаблон начинается и заканчивается одной и той же комбинацией букв, |шаблон| вообще не появится в таблице. Например, для шаблон =«колокол» для всех суффиксов (кроме пустого) сдвиг будет равен 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])
№50 слайд
Содержание слайда: Быстрый алгоритм вычисления таблицы суффиксов
suffshift[0] соответствует всей совпавшей строке;
suffshift[m] — пустому суффиксу.
Так как префикс-функция вычисляется за O(|шаблон|) операций, вычислительная сложность этого шага также равняется O(|шаблон|)
№51 слайд
Содержание слайда: Пример работы алгоритма БМ
Искомый шаблон — «abbad».
Таблица стоп-символов:
Символ a b [остальные]
Позиция 4 3 0
Таблица суффиксов для всех возможных суффиксов (кроме пустого) даёт максимальный сдвиг — 5
№52 слайд
Содержание слайда: Пример работы алгоритма БМ
Накладываем образец на строку.
abeccaabadbabbad
abbad
Совпадения суффикса нет — таблица суффиксов даёт сдвиг на одну позицию. Для несовпавшего символа исходной строки «с» (5-я позиция) в таблице стоп-символов записан 0. Сдвигаем образец вправо на 5-0=5 позиций
№53 слайд
Содержание слайда: Пример работы алгоритма БМ
аbeccaabadbabbad
abbad
Символы 3—5 совпали, а второй — нет. Эвристика стоп-символа для «а» не работает (2-4=-2).
Часть символов совпала, используем эвристику совпавшего суффикса. Шаблон сдвигается на пять позиций!
№54 слайд
Содержание слайда: Пример работы алгоритма БМ
аbeccaabadbabbad
abbad
Совпадения суффикса нет. По таблице стоп-символов сдвигаем образец на 1 позицию и получаем искомое вхождение образца:
аbeccaabadbabbad
abbad
№55 слайд
Содержание слайда: Алгоритм Бойера-Мура
Достоинства
Алгоритм Бойера-Мура на «хороших» данных очень быстр, а вероятность появления «плохих» данных крайне мала. Поэтому он оптимален в большинстве случаев, когда нет возможности провести предварительную обработку текста
На коротких текстах выигрыш не оправдывает предварительных вычислений.
№56 слайд
Содержание слайда: Алгоритм Бойера-Мура
Недостатки
не расширяются до приблизительного поиска, поиска любой строки из нескольких.
Не рекомендуют использовать алгоритм, если текст изменяется редко.
На больших алфавитах таблица стоп-символов может занимать много памяти. В таких используют спец. методы хранения таблиц
№57 слайд
Содержание слайда: Алгоритм Бойера-Мура
На искусственно подобранных «неудачных» текстах (например, шаблон=«колоколоколоколоколокол») скорость алгоритма Бойера-Мура серьёзно снижается
Скачать все slide презентации Поиск подстрок одним архивом:
