Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 212
Текст из файла (страница 212)
Глава 32. Поиск подстрок 1033 Р1н!те АУтОмАтОН МАтснеи(Т, с, ти) 1 и — 1еидй(Т] 2 й» вЂ” О 3 Тог г — 1 Фо и 4 йо д — 6(д, Т]1]) 5 Ыо=ти б Феи ргш1 "Образец обнаружен при сдвиге" 1 — ти Поскольку структура процедуры Р1н1те Аитомдтон Мдтснен представляет собой простой цикл, время поиска совпадений с его помощью в тексте длиной и равна 9(и). Однако сюда не входит время предварительной обработки, которое необходимо для вычисления функции переходов б. К этой задаче мы обратимся позже, после доказательства корректности работы процедуры Р1- н!те А11тОмАтОН МАтснен. Рассмотрим, как автомат обрабатывает входной текст Т (1..и].
Докажем, что после сканирования символа Т (г] автомат окажется в состоянии о (Т;). Поскольку соотношение о (Т;) = ти справедливо тогда и только тогда, когда Р:1 Ть машина окажется в допустимом состоянии тогда и только тогда, когда она толью что считала образец Р. Чтобы доказать этот результат, воспользуемся двумя приведенными ниже леммами, в которых идет речь о суффиксной функции и. Лемма 32.2 (Неравенство суффиксной функции). Для любой строки х и сим- вола а выполняется неравенство и (ха) < и (х) + 1.
Доказательстиво. Введем обозначение т = г(ха) (рис. 32.7). Если т = О, то неравенство о (ха) = т < о (х) + 1 тривиальным образом следует из того, что величина сг (х) неотрицательна. Теперь предположим, что г ) О. Тогда Р,:1 ха согласно определению функции 1т.
Если в конце строк Р„и ха отбросить по символу а, то мы получим Р„1 1 х. Следовательно, справедливо неравенство т — 1 < о (х), так как ~т (х) — максимальное значение 1с, при ютором выполняется соотношение Рь 1х, и о(ха) = т < п(х) + 1. Ы Р„1 .]а Рис. 32.7. Иллюстрация к доказательству леммы 32.2; из рисунка видно, что выполняется неравенство т < ~т (х) + + 1, где т = и (ха) 1034 Часть ЧП. Избранные темы г- Р, Рис.
32.8. Иллюстрация к доказательству леммы 32.3; из рисунка видно„что выполняется соотношение т = о (Рца), где д = о (х) и т = о (ха) Лемма 32.3 (Лемма а рекурсии суффиксной функции). Если для произвольных строки х и символа а о = о (х), то сг (ха) = о (Ряа). Доказательство. Согласно определению функции ст, Рч 1 х. Как видно из рис. 32.8, наряду с ним выполняется соотношение Рча 1 ха. Если ввести обозначение г = о (ха), то, согласно лемме 32.2, справедливо неравенство т < 4+ 1.
Поскольку Рча 1 ха, Р, 1 ха и ~Рт~ < ~Рда~, из леммы 32.1 следует, что Р„:1 Рза. Поэтому справедливо неравенство т < сг(Рча), те. гт (ха) < гт(Рча). Но, кроме того, сг(Ряа) < о (ха), поскольку Ряа 1 ха. Таким образом, о (ха) = о (Ряа). Теперь все готово для доказательства основной теоремы, характеризующей поведение автомата поиска подстрок при обработке входного текста. Как уже упоминалось, в этой теореме показано, что автомат на каждом шагу просто отслеживает, какой самый длинный префикс образца совпадает с суффиксом части текста, считанной до сих пор.
Другими словами, в автомате поддерживается инвариант (32.4). Теорема 32.4. Если ф — функция конечного состояния, соответствующая автомату поиска подстрок с заданным образцом Р, а Т (1..п] — входной текст этого автомата, то ф(Т) = о (Т) для 1 = О, 1,..., и. Доказаотельсотво. Докажем теорему по индукции по г. Если г = О, то справедливость теоремы очевидна, поскольку То = е. Таким образом, ф (Тс) = 0 = гт(То). Теперь предположим, что выполняется равенство ф (Т;) = гт (Т,), и докажем, что ф (Т;+з) = о (Т1+з).
Обозначим величину ф (Т;) как о, а величину Т [г+ Ц— Глава 32. Поиск подстрок 1035 через а. То1да можно написать цепочку следующих соотношений: В соответствии с теоремой 32.4, если автомат попадает в состояние о в строке 4, то д — наибольшее значение, такое что Ря 1 Т,.
Таким образом, в строке 5 равенство д = т выполняется тогда и только тогда, когда только что был считал образец Р. Итак, мы приходим к выводу, что процедура Р1х1те Аитомлтох Млтснек работает корректно. Вычисление функции переходов Приведенная ниже процедура вычисляет функцию переходов б по заданному образцу Р [1..т]. СомР11те Тило!т!ох рохст!ох(Р, Е) 1 т — 1епдсй[Р] 2 (ог д — О то т 3 до Тог (для) каждого символа а Е Е 4 бо й — пцп(т+ 1,о+ 2) 5 гереа1 1с — Й вЂ” 1 б ппгИ Рь 1 Ряа 7 б(д, а) - )с 8 гетнгн б В зтой процедуре функция б (д, а) вычисляется непосредственно, исходя из ее определения.
Во вложенных циклах, которые начинаются в строках 2 и 3, рассматриваются все состояния о и символы а, а в строках 4-7 функции б(д,а) присваиваются максимальные значения й, при которых справедливо соотношение Рь 1Ряа. Время работы процедуры р1х1те Аотомлтох Млтснек равно О (т [Е[), поскольку внешние циклы дают вклад, соответствующий умножению на т [Е[, внутренний цикл гереа1 может повториться не более т + 1 раз, а для выполнения проверки в строке 6 может понадобиться сравнить вплоть до т символов. Существуют процедуры, работающие намного быстрее; время, необходимое для вычисления функции б по заданному образцу Р, путем применения некоторых величин, ф (Т1+1) = ф(Т,а) = = б(ф(Т,),а) = б(д,а) = = а(Рча) = = о (Т1а) = = о (Т+1) (по определению величин Т1+1 и а) (по определению ф) (по определению д) (по определению б (32.3)) (согласно лемме 32.3 и гипотезе индукции) (по определению Т1+1).
И Часть ЧП. Избранные темы 1036 остроумно вычисленных для этого образца (см. упражнение 32.4-6), можно улучшить до величины 0 (т Д). С помощью такой усовершенствованной процедуры вычисления функции 6 можно найти все вхождения образца длиной т в текст длиной гг для алфавита Е, затратив на предварительную обработку время 0 (т Д), а на сравнение — время 6 (гг). Упражнения 32.3-1. Сконструируйте автомат поиска подстрок для образца Р = ааЬаЬ и проиллюстрируйте его работу при обработке текста Т = аааЬаЬааЬааЬаЬааЬ.
32.3-2. Изобразите диаграмму состояний для автомата поиска подстрок, если образец имеет вид аЬаЬЬаЬЬаЬаЬЬаЬаЬЬа66, а алфавит — Е = 1а, Ь). 32.3-3. Образец Р называют строкой с уникальными префиксами (попочег1арРа61е), если из соотношениЯ Рь Л Рч следУет, что К = О или /с = г1. Как выглядит диаграмма переходов автомата для поиска подстроки с уникальными префиксами7 * 32.3-4. Заданы два образца Р и Р'. Опишите процесс построения конечного автомата, позволяющего найти все вхождения любого из образцов.
Попытайтесь свести к минимуму количество состояний такого автомата. 32.3-5. Задан образец Р, содержащий пробельные символы (см. упражнение 32.1-4). Опишите процесс построения конечного автомата, позволяющего найти все вхождения образца Р в текст Т, затратив при этом на сравнение время 0 (п), где и = ~Т~. * 32.4 Алгоритм Кнута-Морриса-Пратта Теперь представим алгоритм сравнения строк, который был предложен Кнутом (Кпшй), Моррисом (Могпз) и Пратгом (Ргап), и время работы которого линейно зависит от объема входных данных.
В этом алгоритме удается избежать вычисления функции переходов 6, а благодаря использованию вспомогательной функции я 11..гл), которая вычисляется по заданному образцу за время О(пг), время сравнения в этом алгоритме равно Э (гг). Массив я позволяет эффективно (в амортизированном смысле) вычислять функцию Б "на лету", т.е. по мере необходимости. Грубо говоря, для любого состояния д = О, 1,..., гл и любого символа а е Е величина к [у) содержит информацию, которая не зависит от символа а и необходима для вычисления величины б (д, а) (пояснения по поводу этого замечания будут даны ниже).
Поскольку массив я содержит только т элементов (в то время как в массиве 6 их 6 (т1Е~)), вычисляя на этапе предварительной обработки функцию я вместо функции б, удается уменьшить время предварительной обработки образца в )Е! раз. Глава 32. Поиск подстрок 1037 Префикеная функция для образца Пусть символы Р [1..д] образца совпадают с символами текста Т[в + + 1..в + д].
Чему равен наименьший сдвиг в' > в, такой что Р[1..й] = Т [в'+1..в'+ )с], (32.5) где в'+/с = в+ 97 Такой сдвиг в' — первый после сдвига в, недопустимость которого не обязательно следует из наших знаний о подстроке Т [в + 1..в + д]. В лучшем случае в' = в+ д, и все сдвиги в+ 1, в+ 2,..., в+ у-1 немедленно отбрасываются. В любом случае для нового сдвига в' нет необходимости сравнивать первые lс символов образца Р и соответствующие символы текста Т, поскольку их совпадение гарантированно благодаря уравнению (32.5).
Префиксная функция я, предназначенная для какого-нибудь образца, инкапсулирует сведения о том, в какой мере образец совпадает сам с собой после сдвигов. Эта информация позволяет избежать ненужных проверок в простейшем алгоритме поиска подстрок или предвычисления функции б при использовании конечных автоматов. Рассмотрим работу обычного алгоритма сопоставления. На рис. 32.9а показан некоторый сдвиг в шаблона с образцом Р = аЬаЬаса вдоль текста Т. В этом примере д = 5 символов успешно совпали (они выделены серым цветом и соединены вертикальными линиями), а б-й символ образца отличается от соответствующего символа текста. Сведения о количестве совпавших символов д позволяют сделать вывод о том, какие символы содержатся в соответствующих местах текста. Эти знания позволяют сразу же определить, что некоторые сдвиги будут недопустимыми.
В представленном на рисунке примере сдвиг в + 1 точно недопустим, поскольку первый символ образца (а) находился бы напротив символа текста, для которого известно, что он совпадает со вторым символом образца (Ь). Однако из части б рисунка, на которой показан сдвиг в' = в+ 2, видно, что первые три символа образца совпадают с тремя последними просмотренными символами текста, так что такой сдвиг априори нельзя отбросить как недопустимый. Полезную информацию, позволяющую сделать такой вывод, можно получить путем сравнения образца с самим собой. В части в рисунка изображен самый длинный префикс образца Р, который также является собственным суффиксом строк Рв и Рз.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
