Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 230
Текст из файла (страница 230)
Точнее говоря, строка к принимается тогда и только тогда, котла к = уз, гле у = е или строка д оканчивается символом Ь, а з = а", где л — нечетное. Например, последовательность состояний, которые проходит этот автомат для ююдной строки аЬааа (включал начальное состояние), имеет аид (О, 1, О, 1, О, 1), так что входная строка принимается, Если входлал строка имеет вид аЬЬаа, автомат проходит последоаательносп состояний (О, 1,0,0, 1, О), так что юсаднаа строка отвергается. глава 32.
Павел лодсмрол 1043 Автоматы поиска поцстрок Для казкдого образца Р строится свой автомат поиска подстрок; его необходимо сконструировать по образцу на этапе предварительной обработки, чтобы впоследствии использовать для поиска текстовой подстроки. Процесс такого конструирования для образца Р = аЬаЬаса проиллюстрирован на рис. 32.7. С этого момента предполагается, что образец Р— это заданная фиксированная строка: ддя краткости мы будем опускать в обозначениях зависимость от Р. Чтобы создвзь автомат поиска подстрок, соответствующий заданному образцу Р[1 ..
т], сначала определим вспомогательную функцию о, которая называется с7гффиисной функцией (ац(бх йлсбоп), соответствующей образцу Р. Функция а (в) — 1 2 3 4 5 6 7 8 91011 — в Ь в,'' Ь 'а Ь',''а:"С л: Ь а 0 1 2 3 4 5 4 5 6 2 3 с 1 а Т(1) Состояние ф(Тг) (в) (6) Рвс. 32.7. (в) Диаграмма состояний автомата поиска подстрок, который воспринимает все строки, оканчивающиеся строкой нЬиЬвса. Соспмние 0 — начальное, я состояние 7 (оно выделено черным цвегом) — единственное допусквюшее. Функши переходов Б определяется уравнением (32.4), а ориентироввннме ребра, направленные из состояния г в соспание у и обознвченные меткой о, представляют значение функции 6(г,о) = 71 Ребра, направленные впраю, которые образуют "хребет" автомата и выделены нв рисунке мирными линиями, соответствуют точным совпвдениям образца и входных символов.
Зв исключением ребер из состояния 7 в состояния 1 и 2, ребра, няпрввленные влево, соответствуют несовпадением. Некоторые ребра, соответствующие несовпялениям, не повязаны; в соответсшии с соглашением, если для неипорого символа о 6 Е у состояния з отсутствуют исхсдяшие ребра с меткой о, то б(з, о) = О. (6) Соотвегствуюшвя функция переходов 6, в глюке строка образца Р = вЬвЬвсв. Элементы, соответствующие совпядениям мекку образцам и входными символами, выделены серым цветом. (в) Обработка автоматом текста Т = вЬвЬаЬасвЬа.
Под квжлым символом текста ТЯ уквзвио состояние ф(Т,), в котором нююдигся автомат после обработки префикса Т,. Образец всгречвется в тексте один ряз, причем совпядвюшля подстрока оканчивается в девятой позиции. Состояние 0 1 2 3 4 5 6 7 Вхцл в Ь е ~11::"О,:0 ' .1'2';0 7,) 0 ~ 0 ) ,1~2 О", !044 Часть П!. Избраниие теми сг является отображением множества Е' на множество (О, 1,..., т), таким, что величина сг(х) равна длине максимального префикса Р, который является суффиксом строки х: сг(х) = швх(lс: Рь з х), (32.3) Суффиксная функция сг вполне определена, поскольку пустая строка Ро = е является суффиксом любой строки. В качестве примера рассмотрим образец Р = аЬ; тогда сг(е) = О, а(ссаса) = 1 и а(ссаЬ) = 2. Для образца Р длиной т равенство а(х) = т выполняется тогда и только тогда, когда Р л х.
Из определения суффиксной функции следует, что если х Л у, то сг(х) < а(у). Определим автомат поиска подстрок, соответствующий образцу Р(1 .. т], следующим образом. ° Множество состояний Я имеет внд (О, 1,..., т). Начальным состоянием де является состояние О, а состояние т является единственным принимающим состоянием. Функция переходов б определена для любого состояния д и символа а уравнением б(д,а) = о(Рта) .
(32.4) Мы определяем б(д, а) = а(Раа), потому что хотим отследить самый длинный префикс образца Р, который до сих пор соответствовал текстовой строке Т. Чтобы подстрока Т вЂ” скажем, подстрока, заканчивающаяся в Т[г] — соответствовала некоторому префиксу Р, образца Р, этот префикс Р, должен быть суффиксом Т,. Предположим, что д = ф(Т;), так что после чтения Т, автомат находится в состоянии д. Разработаем функцию переходов б таким образом, чтобы этот номер состояния, д, указывал длину наибольшего префикса Р, который соответствует суффиксу Т,, т.е.
чтобы в состоянии д выполнялись соотношения Ра л Т, и д = сг(Т;). (Когда д = т, все т символов Р соответствуют суффиксу Т„так что мы находим искомую подстроку.) Таким образом, поскольку и ф(Т,), и а(Т,) равны д, мы увидим (ниже, в теореме 32.4), что автомат поддерживает следующий инвариант: ф(Т,) = а(Т,) . (32.5) Если автомат находится в состоянии д и считывает очередной символ Т~г'+1] = а, то необходимо, чтобы переход вел в состояние, соответствующее наибольшему префиксу Р, который одновременно является суффиксом Т,а, а этим состоянием является а(Т,а). Поскольку Ре представляет собой наибольший префикс Р, являющийся суффиксом Та наибольший префикс Р, который является суффиксом Т,а, не только а(Та), но и сг(Раа).
(Лемма 32.3 на с. 1046 доказывает, что а(Теа) = а(Раа).) Таким образом, необходимо, чтобы, когда автомат находится в состоянии д, функция переходов для символа а переводила автомат в состояние а(Рта). Следует рассмотреть два случая. В первом случае а = Р]д + 1], так что символ а продолжает соответствие образцу; при этом, поскольку б(д, а) = д + 1, переход продолжает выполняться вдоль "хребта" автомата (полужирные ребра на рис.
32.7). Во втором случае а ~ Р]д+1], так что а не соответствует образцу. Здесь Глава 52. Поиск лодснрок !о45 нужно найти меньший префикс Р, который одновременно является суффиксом Т1. Поскольку на этапе предварительной обработки при создании автомата образец сопоставляется с самим собой, функция переходов быстро находит наибольший среди таких меньших префиксов Р. Давайте обратимся к конкретному примеру. Автомат на рис.32.7 имеет б(5, с) = 6, что иллюстрируег первый случай, когда продолжается соответствие. Чтобы проиллюстрировать второй случай, заметим, что автомат на рис.
32.7 имеет б(5, Ь) = 4. Мы выполняем такой переход, посюльку, если автомат считывает Ь в состоянии д = 5, то Р,Ь = аЬаЬаЬ, и наибольшим префиксом Р, одновременно являющимся суффиксом аЬаЬаЬ, является Рл = аЬаЬ. Чтобы пояснить работу автомата, предназначенного для поиска подстрок, приведем простую, но эффективную программу для моделирования поведения такого автомата (представленного функцией переходов б) при поиске образца Р длиной т во входном тексте Т[1 ..
и[. Как и в любом другом автомате поиска подстрок, предназначенном для образца длиной т, множество состояний Я имеет вид (О, 1,..., т), начальным состоянием является состояние О, а единственным принимающим является состояние т. Р!х!те-АнтОмАтон-МАтснек(Т, б, т) 1 и = ТЛеидй г !=О 3 Тог1 = 11ои 4 1 = б(!1,Т[1[) 5 Ыда=т 6 рпп! "Образец найден со сдвигом" 1 — т Из простой циклической структуры процедуры Р!н!те-АнтомАтон-МАтснек можно легко увидеть, что время поиска совпадений с его помощью в тексте длиной и равно Е1(и).
Однако сюда не входит время предварительной обработки, которое необходимо для вычисления функции переходов б. К этой задаче мы обратимся позже, после доказательства корректности работы процедуры Р1н1теА15тОмАтО!ч-МАтснек. Рассмотрим, как автомат обрабатывает входной текст Т[1 .. и]. Докажем, что после сканирования символа ТЯ автомат окажется в состоянии о(Т;). Поскольку соотношение о(Т;) = т справедливо тогда и только тогда, когда Р:! Т1, машина окажется в принимающем состоянии т тогда и только тогда, югда она только что считает образец Р. Чтобы доказать этот результат, воспользуемся двумя приведенными ниже леммами, в которых идет речь о суффиксной функции о. Лемма 32.2 (Неравенство суффнксной функции) Для любой строки х и символа а выполняется неравенство о(ха) ( сс(х) + 1.
Доказательство. Введем обозначение г = о(ха) (рис.32.8). Если г = О, то неравенство о(ха) = т ( о(х) + 1 тривиальным образом следует из того, что величина о(х) неотрицательна. Теперь предположим, что г ) О. Тогда Рг ':! ха согласно определению функции о. Если в юнце строк Р, и ха отбросить по символу 104б Часмь и/. 14збранлые ьзеиы Рнс. 32.8. Иллюстрация к доказательству леммы 32.2. На рисунке показано, что т < о(к) + 1, где г = о(ко).
Рис. 323Х Иллюстрапил к доказательству леммы 32.3. На рисунке показано, что т = о(рте), где о = е (я) и з = о(ко). а, то получим Р, 1 1 х. Следовательно, справедливо неравенспю т — 1 < о(х), так как о(х) — наибольшее значение к, при юзтором выполняется соотношение Рь 1 х, и, таким образом, а(ха) = т < о(х) + 1. Лемма 32.3 (Ламма о рекурсии су(рчзиксной 4ункции) Если для произвольной строки х н символа а выполняется д = о(х), то о(ха) = о(Рта).
Доаизаазельсизвза Ре ~ х нз определения т. Как показано на рис. 32.9, выполняется также Реа 1 ха. Если обозначить т = о(ха), то Р„л ха и, согласно лемме 32.2, т < Ч+ 1. Таким образом, имеем [Р,[ = г < д+ 1 = [Реа[. Посизльку Рса )ха, Р„:1 ха и [Р,[ < [Рта[, из леммы 32.1 следует, что Р, з Реа.
Следовательно, т < о(Р а), т.е. о(ха) < о(Реа). Но, кроме того, а(Рса) < а(ха), поскольку Р,а ~ ха. Таким образом, т(ха) = о(Реа). Теперь мы готовы доказать основную теорему, характеризуюшую поведение автомата поиска подстрок при обработке входного текста. Как уже упоминалось, в зтой теореме показано, что автомат на квкдом шагу просто отслеживает, какой самый длинный префикс образца совпадает с суффиксом части текста, считанной до сих пор. Другими словами, в автомате поддерживается инвариант (32.5). Теорема 32.4 Если ф — функция конечного состояния автомата поиска подстрок для заданного образца Р, а Т[1 ., и[ — входной текст автомата, то ф(Т;) = о(Т,) !047 Глава 32 Поиск водсгирос Доказаисельствв.
Доказательство выполняется по индукции по с. Для с = О теорема тривиально истинна, поскольку То = с. Таким образом, ф(То) = О = сг(То). Теперь предположим, по ф(Т!) = а(Т,) и докажем, что ф(Те!) = а(Т! ь!). Обозначим ф(Т!) как с«, а Т]с'+ 1] — как а. Тогда В соответствии с теоремой 32.4, если автомат попадает в состояние д в строке 4, то д — наибольшее значение, такое, что Р:«Т,. Таким образом, в строке 5 равенство д = т выполняется тогда и только тогда, когда только что был считан образец Р. Итак, мы приходим к выводу, что процедура р!«ч«тк-АитомАТО«ч- МАТСНКК работает корректно. Вычисление функции переходов Приведенная ниже процедура вычисляет функцию переходов б по заданному образцу Р[1 ..
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
