Алгоритмы - построение и анализ (1021735), страница 212
Текст из файла (страница 212)
Процесс такого конструирования для образца Р = аЬабаса проиллюстрирован на рис. 32.6. С этого момента предполагается, что образец Р— это заданная фиксированная строка: для краткости мы будем опускать в обозначениях зависимость от Р. Чтобы создать автомат поиска подстрок, соответствующий заданному образцу Р [1..тл], сначала определим вспомогательную функцию о, которая называется суффиксной функцией (зпщх гппспол), отвечающей образцу Р. Функция о является отображением множества Е' на множество (О, 1,..., т), таким что величина о (х) равна длине максимального префикса Р, который является суффиксом строки х: о (х) = шах(к: Рь 1х). Суффиксная функция о вполне определена, поскольку пустая строка Ро —— е является суффиксом любой строки.
В качестве примера рассмотрим образец вида 1031 Глава 32. Поиск подстрок 1 (6'.— '-а ~ ~,' '-' — з Яз~-'-ч; 5 Й-в ( ~~-2; (5',-'=' — з ~'6 5 —."'-в ф вхм: Созмжие а ь 5 4 5 6 5 .'. З '.0 П ГК вЂ” а Ь 4 Ь 4 Ь 4 С,а Ь а Соломлиж54 а ~ " 5 4 5 4 5 6 Я 5 и Рис. 32.6. Процесс конструирования конечного автомата лля образца Р = аЬаЬаса Р = аЬ;тогда сг(е) = 0,4г(ссаса) = 1 но (ссоЬ) = 2. Для образца Рдлиной гправенство и (х) = т выполняется тогда и только то5ца, когда Р Л х.
Из определения суффиксной функции следует, что если х ] у, то 4т (х) с 4т (у). Определим автомат поиска подстрок, соответствующий образцу Р [1..т), следующим образом. ° Множество состояний Я имеет вид (0,1,... тп). В роли начального состояния дс выступает состояние О, а единственным допустимым является состояние т. ° Функция переходов Б определена для любого состояния д и символа а уравнением Б(й,а) = с" (Рва).
Поясним, откуда берется соотношение б (41, а) = ц (Рча). В качестве инварианта цикла этот автомат поддерживает соотношение ф(Т;) = 4т(Т4); (32.4) этот результат доказывается в сформулированной ниже теореме 32.4. На словах это означает, что после сканирования первых 1 символов текстовой строки Т автомат переходит в состояние ф (Т4) = 4Ь где д = 4т (Т;) — длина самого длинного 1032 Часть Ч11.
Избранные темы суффикса Т;, который одновременно является префиксом образца Р. Если следующим сканируемым символом является символ Т [1+ 1] = а, то машина должна осуществить переход в состояние сг (Т+~) = о (Тга). Из доказательства этой теоремы видно, что и (Тга) = <т (Рта). Другими словами, чтобы вычислить количество символов в самом длинном суффиксе Т;а, юторый является префиксом образца Р, можно найти самый длинный суффикс Рца, юторый является префиксом Р.
На каждом этапе машине нужна информация о длине самого длинного префикса Р, который является суффиксом считанной до сих пор строки. Таким образом, если положить 6 (д, а) = и (Рда), то будет поддерживаться нужный инвариант (32.4). Вскоре это неформальное пояснение будет изложено в более строгой форме. Например, в автомате поиска подстрок, представленном на рис. 32.6, 6 (5, Ь) = = 4. Этот переход осуществляется потому, что если автомат считывает символ Ь, находясь в состоянии 11 = 5, то РяЬ = аЬаЬаЬ, и самый длинный префикс образца Р, совпадающий с суффиксом строки аЬаЬаЬ вЂ” Ря = аЬаЬ. Рассмотрим рис.
32.6 подробнее. В части а приведена диаграмма состояний для автомата поиска подстрок, который воспринимает все строки, оканчиваюшиеся строкой аЬаЬаса. Состояние Π— начальное, а состояние 7 (оно выделено черным цветом) — единственное допустимое состояние. Ориентированные ребра, направленные от состояния 1 в состояние 7' и обозначенные меткой а, представляют значение функции б (г, а) = т1 Ребра, направленные вправо, которые образуют "хребет" автомата и выделены на рисунке жирными линиями, соответствуют точным совпадениям образца и входных символов. Ребра, направленные влево, соответствуют несовпадениям.
Некоторые ребра, соответствующие несовпадениям, не показаны; в соответствии с соглашением, если для некоторого символа а Е Е у состояния 4 отсутствуют исходящие ребра с меткой а, то 6 (1, а) = О. В части б представлена соответствующая функция переходов б, а также строка образца Р = аЬаЬаса. Элементы, соответствующие совпадениям между образцом и входными символами, выделены серым цветом.
В части в проиллюстрирована обработка автоматом текста Т = аЬаЬаЬасаЬа. Под каждым символом текста Т [г) указано состояние ф (Т;), в котором находится автомат после обработки префикса Т;. Образец встречается в тексте один раз, причем совпадающая подстрока оканчивается на девятой позиции. Чтобы пояснить работу автомата, предназначенного для поиска подстрок, приведем простую, но эффективную программу для моделирования поведения такого автомата (представленного функцией переходов 6) при поиске образца Р длиной гп во входном тексте Т [1..п[. Как и в любом другом автомате поиска подстрок, предназначенном для образца длиной т, множество состояний Я имеет внд (О, 1,..., тл), начальное состояние имеет индекс О, а единственным допустимым является состояние т.
Глава 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. Ы Рис. 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те Аитомлтох Млтснек работает корректно.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
