Алгоритмы - построение и анализ (1021735), страница 213
Текст из файла (страница 213)
Вычисление функции переходов Приведенная ниже процедура вычисляет функцию переходов б по заданному образцу Р [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, видно, что первые три символа образца совпадают с тремя последними просмотренными символами текста, так что такой сдвиг априори нельзя отбросить как недопустимый.
Полезную информацию, позволяющую сделать такой вывод, можно получить путем сравнения образца с самим собой. В части в рисунка изображен самый длинный префикс образца Р, который также является собственным суффиксом строк Рв и Рз. Эти данные предварительно вычисляются и заносятся в массив я, так что я [5] = 3. Если первые 9 символов совпали при сдвиге в, то следующий сдвиг, который может оказаться допустимым, равен в' = в + (д — сг [9]). Словом, в общем случае полезно знать ответ на сформулированный ниже вопрос. Часть Ч1!. Избранные темы 1038 у — — — 1 — — ~(а. ь в~ь.в~.,:а~ Р [ь ~а ~с ге'а [ь ~а[ь~к!к ~ь [с ге!а[а! г ю'=я, ~ — ь — э [ ю [ ь 1т а' ] ъ~'ь ) гт Гк ~ЬЯ Рз Рис.
32.9. Префнксная функция к Необходимую информацию об образце можно получить, сдвигая его вдоль самого себя (см. рис.32.9с). Поскольку Т [а' + 1..а' + й] — известная часть текста, она является суффиксом строки Рч. Поэтому уравнение (32.5) можно рассматривать как запрос о максимальном значении й < 9, таком что Рь л Ря.
Тогда следующий потенциально допустимый сдвиг равен з' = а+ (д — 1с). Оказывается, что удобнее хранить количество й совпадающих при новом сдвиге а' символов, чем, например, величину з' — з. С помощью этой информации можно ускорить и простейший алгоритм поиска подстроки, и работу конечного автомата.
Теперь дадим формальное определение. Префиксной функцией (ргебх Йпсбоп) заданного образца Р [1..тп] называется функция к: (1, 2,..., т) -+ (О, 1,..., тл — 1), такая что к [9] = шах (lс: к < д и Рь ) Рч) . Другими словами, и [у] равно длине наибольшего префикса образца Р, который является истинным суффиксом строки Рч. В качестве другого примера на рис. 32.10а приведена полная префиксная функция к для образца абабабаЬса. Алгоритм поиска подстрок Кнута-Морриса-Пратта приведен ниже в виде псевдокода процедуры КМР МАтсннв.
В процедуре КМР МАтсннк вызывается вспомогательная процедура Сомгитн Ркнщх Римспон, в которой вычисляется функция и. Глава 32. Поиск подстрок 1039 а) )б [Ь!а ~Ь[а [Ь,а[Ьт[с а ~а'[Ьса[Ьза[Ь*'а Ь с а [а]Ь[а Ь а Ь а Ь с а )в я[8[ 6 )б я[6] = 4 я[4[ 2 в ,'а Ь а Ь а Ь а Ь с а я[2[ О Рв б) Рис. 32.10.
Иллюстрация к лемме 32.5 лля образца Р = аЬаЬаЬаЬса ид= 8 Г~Мр МАтОнек(Т, Р) 1 тв - [епд8[в[Т] 2 т — [епд8[в[Р] 3 К б- СОМРОТЕ РКЕР)Х я'[)Ь[СТ1ОЫ(Р) 4 д — О с Число совпавших символов 5 Гоге -18отв с Сканирование текста слева направо б б[о вап[[е д ) О и Р[д + 1] ф Т[в] 7 до д б — к[д] с Следующий символ не совпадает 8 [Г Р[д + 1) = Т[в) 9 8[вен д — д+ 1 с Следующий символ совпадает 1О [Г д = т [> Совпали ли все символы образца Рд 11 8[вен рпп1 "Образец обнаружен при сдвиге" в — т 12 д - вг[д) 8 Поиск следующего совпадения Часть ЧП.
Избранные темы 1040 СОмгцте Ркее|х Рглчстюн(Р) 1 т — 1егг911г [Р] 2 я[Ц» — О 3 )с» — О 4 аког»7 — 21от 5 бо иИ!е 1с ) О и Р[1с+ Ц ф Р[г1] 6 бо )с я[/с] 7 !Г Р[гс+ Ц = р[»7] 8 1'пеп й — 1с+ 1 9 7г[9] — »с 1О гегпгп к Сначала проанализируем время работы этой процедуры. Доказательство ее кор- ректности окажется более сложным. Анализ времени работы С помощью метода потенциалов амортизационного анализа (см.
раздел 17.3) можно показать, что время работы процедуры Сомгите Ркее1Х Рглчст1он равно О (т). Потенциал величины й связывается с текущим ее значением в алгоритме. Как видно из строки 3, начальное значение этого потенциала равно О. В строке 6 значение величины 1с уменьшается при каждом его вычислении, поскольку я [»с] < )с. Однако в силу неравенства я [гс] > О, которое справедливо при всех 1с, значение этой переменной никогда не бывает отрицательным. Единственная другая строка, юторая тоже оказывает влияние на значение переменной Й,— строка 8.