Поиск подстрок - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Содержание ▲

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

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

Слайд 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

Слайд 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

Описание слайда:

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

Теги Поиск подстрок

Похожие презентации