Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 231
Текст из файла (страница 231)
7п]. СОМРОте-ТкА«св«т«О«ч-р!««чст«О«с(Р, Е) 1 га = Р. 1епд!«с 2 Тогу=О!оси 3 аког каждого символа а е Е 4 «с = шш(та+1,9+2) 5 гереа! 6 lс = lс — 1 7 ИПГВРЬ «Рса 8 б(с«,а) = )с 9 гетпгп б В зтой процедуре функция б(д,а) вычисляется непосредственно, исходя из ее определения (32.4). Во вложенных циклах, которые начинаются в строках 2 и 3, рассматриваются все состояния д и все символы а, а в строках 4-8 функции б(д, а) присваивается наибольшее значение «с, такое, что Рь ' «Рса. Код начинается с наибольшего мыслимого значения «с, которое равно ш«п(т, д + 1).
Затем он уменьшает «с до тех пор, пока не будет достигнуто Рь л Р а, что в конечном итоге произойдет, поскольку Ро = в является суффиксом любой строки. Время работы процедуры Сомр!«Тн-ТкА«чз«т«О«ч-РО«чст«О«с равно 0(тз ~Е~), поскольку внешние циклы дают вклад, соответствующий умножению на тп]Е~, внутренний цикл гереат может повториться не более тп + 1 раз, а для выполне- ф(Т; ) = ф(тса) = б(ф(Т;),а) = б(д,а) = а(Рса) = а(Т;а) = а(Тьь«) (согласно (согласно (согласно (согласно (согласно (согласно определению Тьь! и а) определению ф) определению д) определению б (32.4)) лемме 32.3 и гипотезе индукции) определению Т,+!) . 1048 Часть 171.
избранные еьемы ния проверки Рь 1 Ряа в строке 7 может потребоваться сравнить вплоть до т символов. Существуют процедуры, работающие намного быстрее; время, необходимое для вычисления функции б по заданному образцу Р, путем применения некоторых величин, остроумно вычисленных для этого образца (см. упр. 32,4.8), можно улучшить до величины 0(т [Е[). С помощью такой усовершенствованной процедуры вычисления функции б можно найти все вхождения образца длиной т в текст длиной и для алфавита Е, затратив на предварительную обрабопсу время 0(т [Е[), а на сравнение — время 9(п). Упражнения зг.з г Сконструнруйте автомат поиска подстрок для образца Р = ааЬаЬ и проиллюстрируйте его работу при обработке текста Т = аааЬаЬааЬааЬаЬааЬ.
зг.з.г Изобразите диаграмму состояний для автомата поиска подстрок, если образец имеет вид аЬаЬЬаЬЬаЬаЬЬаЬаЬЬаЬЬ, а алфавит — Е = (а, Ь). 32.3.3 Образец Р называется строкой с уникальными префиксами (попочег1арраЫе), если из соотношения Рь 1 Рл следует, что lс = О или )е = д. Как выглядит диаграмма переходов автомата для поиска подстрок с уникальными префиксами? зг.з.4 * Заданы два образца — Р и Р'. Опишите процесс построения конечного автомата, позволяющего найти все вхождения любого из образцов.
Попытайтесь свести к минимуму количество состояний такого автомата. 32.3.5 Задан образец Р, содержащий пробельные символы (см. упр, 32.1.4). Опишите процесс построения конечного автомата, позволяющего найти все вхождения образца Р в текст Т, затратив при этом на сравнение время 0(п), где и = [Т[. * 32.4. Алгоритм Кнута-Морриса — Пра и а Здесь вашему вниманию представим алгоритм сравнения строк, который был предложен Кнутом (Кппйэ), Моррисом (Могпз) и Праттом (Ргап). В нем удается избежать вычисления функции переходов б, а благодаря использованию вспомогательной функции к, которая вычисляется по заданному образцу за время 6(т) и хранится в массиве к[1 ., т[, время сравнения в этом алгоритме оказывается равным 1э(п).
Массив к позволяет эффективно (в амортизированном смысле) вычислять функцию б "на лету", т.е. по мере необходимости. Грубо говоря, для любого состояния д = О, 1,...,т и любого символа а Е Е величина х[д) содер- Глава Зд Поиск лодстрок 1049 жит информацию, необходимую для вычисления величины Б[(), а), но не зависит от а. Поскольку массив и содержит только пз элементов (в то время как в массиве б их бг(т [Е]), вычисляя на этапе предварительной обработки функцию тг вместо функции 6, удается уменышпь время предварительной обработки образца в ]Е] раз. Префиисная функция для образца Префиксная функция тг для некоторого образца инкапсулирует сведения о том, в какой мере образец совладает сам с собой после сдвигов.
Эта информация позволяет избежать ненужных проверок в простейшем алгоритме поиска подстрок и предвычисления фуню(ии Ю при использовании конечных автоматов. Рассмотрим работу обычного алгоритма непосредственного сопоставления. На рис. 32.)0,(а) показан некоторый сдвиг л шаблона с образцом Р = аЬаЬаса вдоль текста Т.
В этом примере г) = 5 символов успешно совпали (они выделены серым цветом и соединены вертикальными линиями), а шестой символ образца отличается от соответствующего символа текста. Информация о количестве сов- 'с'ь,е 'о] (Ь в . ' '",:,- .. т (а) и — 1 — ь. ] е; Ь ГЪ"[)З~~"., Р, ]:а:,[Ф[гау:~ Р, (в) Рис. 32.10. Префиксная функция я. (а) Образец Р = а)заЪасв, адвннугый относительно Т так, что совгщлают первые О = 5 символов. Совпадающие символы выделены серой шгрнховюй и соединены вертикальными линиями. (6) Пальзуась одной лишь информацией о пати совпадыощих символах, манна вывести, что сдвиг в+ 1 недопустим, но сдвиг в' = в + 2 согласуется со всем, что мы знаем о тексте, а значит, потенциально допустим.
(в) Можно предварительно вычислить полезную информмпио для таких выводов, сравнив образец с самим собой. Здесь мы видим, что иандлиннейший префикс Р, жпорый одновременно является истинным суффиксом )Ъ, есть Рз. Представим зту предвычисленную информацию в массиве зг, так что я[5] = 3. Если известно, что при сдвиге в наблквшется соответствие и символов, то следующий потенциально допустимый сдвиг, как показано в части (б), — в' = в + (д — я[9]).
Часть ГЧЛ Избранные згеми 1050 павших символов о позволяет сделать вывод о том, какие символы содержатся в соответствующих местах текста. Эти знания позволяют сразу же определить, что некоторые сдвиги будут недопустимыми. В представленном на рисунке примере сдвиг в + 1 точно недопустим, поскольку первый символ образца (а) находился бы напротив символа текста, для которого известно, что он совпадает со вторым символом образца (Ь). Однако из части (б) рисунка, на которой показан сдвиг в' = в + 2, видно, что первые три символа образца совпадают с тремя последними просмотренными символами текста, так что такой сдвиг априори нельзя отбросить как недопустимый. В общем случае полезно знать ответ на следующий вопрос. Известно, что символы Р[1 ..
о) образца соответствуют символам Т[з + 1 .. в+ д) текста. Каков наименьший сдвиг з' > в, такой, что для некоторого (с < в Р[1.. к] = Т[в'+ 1..в'+ к), (32.б) где в' + гс = з + ду Другими словами, зная, что Рс 1 Т,+с, необходимо найти наидлиннейший истинный префикс Рь строки Р, который одновременно является суффиксом Т,+ . (Поскольку в'+ к = в + д, если заданы в и д, то поиск наименьшего сдвига в' эквивалентен поиску длины наибольшего префикса /с.) Мы добавляем разность о — (с длин этих префиксов Р к сдвигу в, чтобы получить новый сдвиг з', так что в' = з + (д — гс).
В лучшем случае Й = О, так что в' = в + д и мы тут же пропускаем сдвиги в+ 1, з+ 2,..., в + д — 1. В любом случае при новом сдвиге в' не нужно сравнивать первые )с символов Р с соответствующими символами Т, поскольку (32.б) гарантирует, что они совпадают. Необходимую информацию можно вычислить путем сравнения образца с самим собой, как показано на рнс. 32.10,(в). Поскольку Т[вг + 1 .. в'+ 1с) является частью известного фрагмента текста, она является суффиксом строки Р . Поэтому уравнение (32.б) можно рассматривать как запрос о максимальном значении гс < д, таюм, что Рь ~ Рз. Тогда следующий потенциально допустимый сдвиг равен в' = в + (л — к).
Оказывается, что удобнее хранить для каждого значения д количество lс совпадающих при новом сдвиге в' символов, чем, например, величину з' — в. Формализуем предварительно вычисляемую информацию следующим образом. Для заданного образца Р[1 .. т) нрефикеной функцией для Р является функция гг: (1,2,...,гл) -г (0,1,...,пз — 1), такая, что л[д] = глах (гс: гс < в и Рь л Р ) Иначе говоря, я[о] равно длине наибольшего префикса образца Р, который является истинным суффиксом строки Рз.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
