17 (1106254)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Курс «Алгоритмы и алгоритмические языки»1 семестр 2013/2014Лекция 171Формальная постановка задачи поиска по образцуДаны текст – массив T[N] длины N и образец – массив P[m]длины m ≤ N, где значениями элементов массивов T и Pявляются символы некоторого алфавита A.Говорят, что образец P входит в текст T со сдвигом s,если 0 ≤ s ≤ N – m и для всех i = 1, 2, …, m T[s + i] = P [i].Сдвиг s(T, P) называется допустимым, если P входит в T сосдвигом s = s(T, P) и недопустимым в противном случае.Задача поиска подстрок состоит в нахождении множествадопустимых сдвигов s(T, P) для заданного текста T и образца P.2Формальная постановка задачи поиска по образцуТерминология.

Пусть строки x, y, w ∈ A*, ε ∈ A* - пустая строка;|x| - длина строки x;xy – конкатенация строк x и y; |xy| = |x| + |y|;x = wy -> w – префикс (начало) x (обозначение w  x );x = yw -> w – суффикс (конец) x (обозначение w  x );если w – префикс или суффикс x, то |w| ≤ |x|;отношения префикса и суффикса транзитивны.Для любых x, y ∈ A* и любого a ∈ A соотношения x  yи xa  ya равносильны.Если S = S[r] – строка длины r, то ее префикс длины k, k ≤ r будетобозначаться Sk = S[k]; ясно, что S0 = ε, Sr = S.3Лемма (о двух суффиксах)Пусть x, y и z – строки, для которых x  z и y  z .Тогда если |x| ≤ |y|, то x  y , если |x| ≥ |y|, то y  x ,если |x| = |y|, то x = y .xxzxzzyyxyxxy|x| ≤ |y|y|x| ≥ |y|y|x| = |y|4Простой алгоритмПроверка совмещения двух строк: посимвольное сравнениеслева направо, которое прекращается (с отрицательнымрезультатом) при первом же расхождении.Оценка скорости сравнения строк x и y – Θ(t + 1), где t – длинанаибольшего общего префикса строк x и y.for (s = 0; s <= n – m; s++) {for (i = 0; i < m && P[i] == T[s + i]; i++);if (i == m)printf ("%d\n", s);}Время работы в худшем случае Θ((n – m + 1)⋅m) ~ Θ(n2).Причина: информация о тексте T, полученная при проверкеданного сдвига s, никак не используется при проверкеследующих сдвигов.

Например, если для образца dddcсдвиг s = 0 допустим, то сдвиги s = 1, 2, 3, недопустимы,так как T[3] == с.5Алгоритм Кнута – Морриса – Пратта. ИдеяПрефикс-функция, ассоциированная с образцом P, показывает,где в строке P повторно встречаются различные префиксы этойстроки. Если это известно, можно не проверять заведомонедопустимые сдвиги.Пример. Пусть ищутся вхождения образца P = a b a b a c a втекст T. Пусть для некоторого сдвига s оказалось, что первые qсимволов образца совпадают с символами текста. Значит,символы текста от T[s+1] до T[s+q] известны, что позволяетзаключить, что некоторые сдвиги заведомо недопустимы.6Алгоритм Кнута – Морриса – Пратта. ИдеяПусть P[1..q] = T[s+1..s+q]; каково минимальное значение сдвигаs′ > s, для которого P[1..k] = T[s′+1..s′+k], где s′+k = s+q?Число s′ - минимальное значение сдвига, большего s,которое совместимо с тем, что T[s+1..s+q] = P[1..q].Следовательно, значения сдвигов, меньшие s′ ,проверять не нужно.Лучше всего, когда s′ = s+q, так как в этом случае ненужно рассматривать сдвиги s+q-1, s+q-2, …, s+1.Кроме того, при проверке нового сдвига s′ можно нерассматривать первые его k символов образца: онизаведомо совпадут.Чтобы найти s′, достаточно знать образец P и число q:T[s′+1..s′+k] – суффикс Pq, поэтому k – это наибольшее число,для которого Pk является суффиксом Pq.

Зная k (число символов,заведомо совпадающих при проверке нового сдвига s′), можновычислить s′ по формуле s′ = s + (q – k).7Алгоритм Кнута – Морриса – Пратта. Префикс-функцияОпределение. Префикс-функцией, ассоциированной со строкойP[1..m], называется функция π: {1,2, …, m} → {0,1, …, m – 1},определенная следующим образом:π[q] = max{k: k<q & Pk  Pq }Иными словами, π[q] – длина наибольшего префикса P,являющегося суффиксом Pq.8Алгоритм Кнута – Морриса – Пратта. Префикс-функцияvoid prefix_func (char *pat, int *pi, int m) {int k, pi;/* Считаем, что pat и pi нумеруются от 1 */pi[1] = 0; k = 0;for (q = 2; q <= m; q++) {while (k > 0 && pat[k + 1] != pat[q])k = pi[k];if (pat[k + 1] == pat[q])k++;pi[q] = k;}}9Алгоритм Кнута – Морриса – Пратта.

Префикс-функцияЛемма 1. Обозначим π * [ q] = {q, π [ q], π 2 [ q],..., π t [ q]},где π i [q] есть i-я итерация префикс-функции, π t [ q] = 0.Пусть P – строка длины m c префикс-функцией π.Тогда для всех q = 1, 2, ..., m имеем π * [ q] = {k :Pk  Pq }.Лемма показывает, что при помощи итерированияпрефикс-функции можно для данного q найти все такие k, чтоPk является суффиксом Pq.Доказательство.(1)Покажем, что если i принадлежит π*[q], то Pi являетсясуффиксом Pq.Действительно, Pπ [ i ]  Pi по определению префиксфункции, так что каждый следующий членпоследовательности Pi , Pπ [ i ] , Pπ [π [ i ]] ,... являетсясуффиксом всех предыдущих.10Алгоритм Кнута – Морриса – Пратта. Префикс-функцияДоказательство.(2)Покажем, что наоборот, если Pi является суффиксом Pq,то i принадлежит π*[q].Расположим все Pi , являющиеся суффиксами Pq, впорядке уменьшения i (длины): Pi1, Pi2,…Покажем по индукции, что Pik = πk[q].База индукции (k=1): для максимального префикса Pi ,являющегося суффиксом Pq, по определению i=π[q].Шаг индукции: если Pik = πk[q], то по определениюj = π[πk[q]] соответствует максимальный префикс Pj,который является суффиксом Pik.

Обе строки Pj и Pikесть суффиксы Pq по построению. Таким максимальнымпрефиксом из оставшихся Pik+1, Pik+2,… по построениюявляется префикс Pik+1 ,то есть j = ik+1.(2) можно доказать и от противного: для наибольшегочисла j такого, что Pj  Pq , но j не входит в π*[q],определение префикс-функции нарушается11Алгоритм Кнута – Морриса – Пратта. Префикс-функцияπ [8] = {8,6,4,2,0}*12Алгоритм Кнута – Морриса – Пратта. Префикс-функцияЛемма 2. Пусть P – строка длины m c префикс-функцией π.Тогда для всех q = 1, 2, ..., m, для которых π [ q] > 0 ,*имеем π [ q ] − 1 ∈ π [ q − 1] .Доказательство.Если k = π [ q ] > 0 , то Pk является суффиксом Pqпо определению префикс-функции.Следовательно, Pk-1 является суффиксом Pq-1.Тогда по Лемме 1 k − 1 ∈ π * [ q − 1] , т.е.π [q] − 1 ∈ π *[q − 1] .Определим множества Eq-1 какEq −1 = {k : k ∈ π *[ q − 1] и P[k + 1] = P[ q]}.Множество Eq-1 состоит из таких k, что Pk является суффиксомPq-1, и за ними идут одинаковые буквы P[k+1] и P[q].Из определения вытекает, что Pk+1 есть суффикс Pq.13Алгоритм Кнута – Морриса – Пратта.

Префикс-функцияСледствие 1. Пусть P – строка длины m c префикс-функцией π.Тогда для всех q = 2, 3, ..., m0, если Eq −1 пусто;π [q] = 1 + max{k ∈ Eq −1}, если Eq −1 не пусто.Доказательство.Если r = π [ q] ≥ 1 , то P[r] = P[q] и по Лемме 2r − 1 = π [ q] − 1 ∈ π *[ q − 1] .Т.к. P[r] = P[q], то P[(r-1)+1] = P[q].Поэтому r − 1 ∈ Eq −1 по определению Eq-1 и из π [ q] ≥ 1следует непустота Eq-1.Следовательно, если Eq-1 пусто, то π [ q] = 0 .Если k ∈ Eq −1 , то Pk+1 есть суффикс Pq (из определения),следовательно,π [ q ] ≥ k + 1 и π [ q] ≥ 1 + max{k ∈ Eq −1}.То есть, если Eq-1 не пусто, то префикс-функцияположительна.

Но тогдаπ [ q] − 1 ∈ Eq −1 , π [ q] − 1 не большемаксимума из Eq-1, т.е. π [ q] ≤ 1 + max{k ∈ Eq −1}.14Алгоритм Кнута – Морриса – Пратта. Префикс-функция1 void prefix_func (char *pat, int *pi, int m) {2int k, pi;34/* Считаем, что pat и pi нумеруются от 1 */5pi[1] = 0; k = 0;6for (q = 2; q <= m; q++) {7while (k > 0 && pat[k + 1] != pat[q])8k = pi[k];9if (pat[k + 1] == pat[q])10k++;11pi[q] = k;12}13 }15Алгоритм Кнута – Морриса – Пратта.

Префикс-функцияТеорема 1. Функция prefix_func правильно вычисляетпрефикс-функцию π.Доказательство.Покажем, что при входе в цикл функции k = π[q-1].База индукции.При q = 2 k = 0, pi[q-1] = pi[1] = 0.Шаг индукции.Пусть при входе в цикл функции k = π[q-1].Код на строках 7-8while (k > 0 && pat[k + 1] != pat[q])k = pi[k];находит наибольший элемент Eq-1 (т.к. цикл перебираетв порядке убывания элементы из π*[q-1] и для каждогопроверяет равенство pat[k + 1] != pat[q])).16Алгоритм Кнута – Морриса – Пратта. Префикс-функцияТеорема 1. Функция prefix_func правильно вычисляетпрефикс-функцию π.Доказательство.После выхода из цикла на строках 7-8while (k > 0 && pat[k + 1] != pat[q])k = pi[k];1) если pat[k + 1] == pat[q], то выполняется код настроке 10:k++;что из Следствия 1 дает нам π[q].2) если pat[k + 1] != pat[q], то k == 0,множество Eq-1 пусто и π[q] = 0.17Алгоритм Кнута – Морриса – Пратта.

Функция kmpvoid kmp (char *text, char *pat, int m, int n) {int q;int pi[m + 1]; /* VLA-массив *//* Через alloca: int *pi = alloca ((m + 1) * sizeof (int)); *//* Считаем, что pat и text нумеруются от 1 */prefix_func (pat, pi, m);q = 0;for (i = 1; i <= n; i++) {while (q > 0 && pat[q + 1] != text[i])q = pi[q];if (pat[q + 1] == text[i])q++;if (q == m) {printf ("образец входит со сдвигом %d\n", i – m);q = pi[q];}18}Алгоритм Кнута – Морриса – Пратта. Функция kmpАлгоритм КМП для подстроки P и текста Т эквивалентенвычислению префикс-функции для строки Q = P#T, где# – символ, заведомо не встречающийся в обеих строкахДлина максимального префикса Q, являющегося еёсуффиксом (т.е.

значение префикс-функции),не превосходит длины PДопустимый сдвиг обнаруживается в тот момент, когдаочередное вычисленное значение префикс-функциисовпадает с длиной подстроки P (условие if (q == m))В явном виде объединенная строка не строится!Теорема 2. Функция kmp работает правильно.Формальное доказательство осуществляется по аналогиис доказательством Теоремы 1, где множества, подобныеEq-1, строятся для строки-текста, а не строки-образца.Свойства префикс-функции часто используются и в другихзадачах (кроме поиска подстроки в строке)Полезной оказывается Лемма 1: итерированиемпрефикс-функции можно найти все префиксы строки, 19являющиеся ее суффиксамиАлгоритм Кнута – Морриса – Пратта.

Время работыФункция prefix_func выполняет ≤ (m – 1) итераций цикла for.Стоимость каждой итерации можно считать равной O(1),а стоимость всей процедуры O(m).Каждая итерация цикла while (строки 7-8) уменьшает kУвеличивается k только в строке 10 не более одного разана итерацию цикла for (строки 6-11)Следовательно, операций уменьшения не больше, чемитераций цикла for, то есть ≤ (m – 1) на весь цикл иO(1) на итерацию в среднемАналогично, функция kmp выполняет ≤ (n – 1) итераций, и еестоимость (без учета вызова prefix_func) есть O(n).Следовательно, время выполнения всей процедуры O(m + n).20.

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов лекций