Алгоритмы - построение и анализ (1021735), страница 214
Текст из файла (страница 214)
Благодаря ее наличию при каждом выполнении тела цикла 1ог значение переменной 7с увеличивается не более чем на 1. Поскольку перед входом в цикл выполняется неравенство Й < д и поскольку значение переменной д увеличивается в каждой итерации цикла 1ог, справедливость неравенства )с < 9 сохраняется (подтверждая тот факт, что соблюдается также неравенство я [д] < д в строке 9). Каждое выполнение тела цикла згп11е в строке 6 можно оплатить соответствующим уменьшением потенциальной функции, поскольку я [)с] < й. В строке 8 потенциальная функция возрастает не более чем на 1, поэтому амортизированная стоимость тела цикла в строках 5 — 9 равна О (1).
Так как количество итераций внешнего цикла равно О (т), и посюльку юнечное значение потенциальной функции по величине не меньше, чем ее начальное значение, полное фактическое время работы процедуры Сомеите Ркенх Рглчстгом в наихудшем случае равно О (т). Аналогичный амортизационный анализ, в котором в качестве потенциальной функции используется значение величины д, показывает, что время выполнения сравнений в процедуре кмР млтснек равно О (и). Глава 32. Поиск подстрок 1041 Благодаря использованию функции я вместо функции 6, которая используется в процедуре ргяте АотомАтон МАтсннк, время предварительной обработки образца уменьшается от 0(гп [Е]) до О (т), в то время как оценка реального времени поиска остается равной 9 (гг).
Корректность вычисления префиксной функции Начнем с рассмотрения важной леммы, в которой показано, что путем итерации префиксной функции я можно перечислить все префиксы Рь, которые являются истинными суффиксами заданного префикса Рс. Введем обозначение []=(.[.], '[.], "[],, "'[]1, где величина сг('1 [д] обозначает (-ю итерацию префиксной функции, т.е. я(о) [г1] = = д и при г > 1 гг('1[гг] = я [я(' 1) [д]]. Кроме того, понятно, что последовательность сг' [гг] обрывается, когда в ней будет достигнуто значение гг('1 [д] = О.
Приведенная ниже лемма, проиллюстрированная на рис. 32.10, характеризует последовательность я'[г1]. Лемма 32.5 (Лемма об итерации префиксной функции). Пусть Р— образец длиной гп с префиксной функцией я. Тогда для всех д = 1, 2,..., т имеем я' [г)] = = ()с: lс < г) и Ря 1 Р ). Доказательства. Сначала докажем, что из г Е сг' [г)] следует Р; 1 Рс.
(32.6) Если(бгг' [д], то г = л(") [г1] для некоторого и > О. Докажем (32.6) по индукции по и. При и = 1 х = гг [д] и сформулированное выше утверждение следует из того, что 1 < г) и Р„[с1 1 Рс. Воспользовавшись соотношениями сг [1] < ( и Р„[г1 1 Р,, а также транзитивностью операций < и 1, можно установить справедливость нашего утверждения для всех г из сг' [д]. Следовательно, сг' [д] С (гс: )с < д и Рь 1 Рс).
То, что (гс: 1с < д и Рь 1 Рс) С сг* [г)], мы докажем методом "от противного". Предположим, что в множестве (lс: lс < гг и Рь 1 Р ) — я' [д] содержатся целые числа и что 3 — наибольшее из них. Поскольку сг [о] — наибольшее значение множества (к: )с < д и Рь 1 Рс), и в силу того„что сг [д] Е гг' [д], должно выполняться неравенство 3 < гг [г)]. Обозначим через ~' наименьший целый элемент множества х* [а], превышающий г'. (Если в множестве гг' [д] не содержится других значений, превышающих т', можно выбрать с' = я [гг].) В силу того, что у й (гс: К < д и Рь 1 Рс), Ру 1 Рс, а кроме того, Р' 1 Рс, поскольку 3' Е гг' [0].
Таким образом, согласно лемме 32.1, справедливо соотношение Р Л Р' и у— наибольшее из значений, меньших значения 3' и обладающих этим свойством. Поэтому должно выполняться равенство гг [)'] = 3' и, поскольку ~' е я' [д], должно выполняться соотношение т' Е гг' [д]. Это противоречие и доказывает лемму. г3 Часть Чй. Избранные темы 1042 На рис. 32.10 лемма 32.5 проиллюстрирована для шаблона Р = аЬаЬаЬаЬса и о = 8. Посюльку гг [8] = 6, я [6] = 4, я [4] = 2 и гг [2] = О, путем итерации функции гг получим я* [8] = (6, 4, 2, 0).
В части б рис. 32.10 показаны последовательные сдвиги шаблона с образцом Р вправо. Обратите внимание, как после каждого сдвига некоторый префикс Рь образца Р совпадает с некоторым собственным суффиксом строки Рз, это происходит при гг = 6,4,2,0. На этом рисунке в первой строке приведен образец Р, а пунктирная вертикальная линия обозначает конец сгроки Ра. В последовательных строках изображены все сдвиги образца Р, при которых некоторый префикс Рь образца Р совпадает с некоторым суффиксом строки Ра. Совпадающие символы выделены серым цветом.
Вертикальные линии соединают совпадающие символы. Таким обРазом, (к: к < о и Рь 1 Рв) = 16,4, 2,0). В лемме утверждается, что для всех д я' [0] = 1к: гг < о и Рь 1 Рв). Алгоритм Сомвитн Ркннх Рггнстюм по порядку вычисляет гг[д] для о = = 1,2,..., га. Корректность вычисления значения ~г [Ц = 0 во второй строке этой процедуры не вызывает сомнений, посюльку при всех о выполняется неравенство зг [о] < о. Приведенная ниже лемма и следствие из нее будут использованы для доказательства того факта, что в процедуре Сомкни Ркннх Рглчстюм функция я [д] вычисляется юрректно при всех о > 1. Лемма 32.6.
Пусть Р— образец длиной га, а гг — префиксная функция этого образца. Тогда я [о] — 1Ея' [д — Ц для всех о = 1,2,..., та, для которых гг [о] > О. Доказательство. Если т = я [о] > О, то т < о и Рт ] Рв, таким образом, т— — 1 < д — 1 и Р„1 1 Рч г (отбрасывая последний символ в строках Р„и Рв). Поэтому, согласно лемме 32.5, зг [з] — 1 = т — 1 Е я' [д — Ц. ы Для о = 2,3,..., т определим подмножество Ев 1 С я* [д — Ц следующим образом: Ев 1 =(3сЕгг" [о — Ц:Р[й+Ц= Р[д]) = = (й: Ь < о — 1 и Рь л Рв г и Р [Ь + Ц = Р [о]) = (гг ' Ь < о 1 н Рь.~.1 3 Рд) где предпоследнее равенство следует из леммы 32.5. Итак, множество Ев 1 состоит из таких значений lс < о-1, что Рь ' ) Рв г и Рь+1 ~ Рв (последнее следует из того, что Р [й+ Ц = Р [о]). Таким образом, множество Ев 1 состоит из тех значений Ь е я' [о — Ц, для которых строку Рь можно расширить до строки Рь+и получив в результате истинный суффикс строки Рв.
Глава 32. Поиск подстрок 1043 Следствие 32.7. Пусть Р— образец длиной т, а я — префиксная функция этого образца. Тогда при д = 2, 8,..., т 0 если Ес 1 = 9, ] 1+ шах[ 1с Е Ес 1) если Ес г ф 9. я[9] > 1+шах(й е Ес 1'). (32.7) Заметим, что я [д] > О. Обозначим г = я [д] — 1, так что г + 1 = я [9]. Поскольку г+ 1 > О, имеем Р [г + 1] = Р [9]. Кроме того, согласно лемме 32.6, г Е л' [д — 1]. Таким обРазом, г Е Ес ы так что г < гпах(к Е Ес 1') или, что эквивалентно, сг [д] < 1 + шах (1с е Ес 1) . (32.8) Объединение уравнений (32.7) и (32.8) завершает доказательство. Теперь завершим доказательство того, что процедура Сомготе Ркев~х Р~л~с'пои корректно вычисляет функцию я. В этой процедуре в начале каждой итерации цикла 1ог в строках 4 — 9 выполняется равенство lс = я. [9 — 1].
Это условие обеспечивается строками 2 и 3 во время первого вхождения в цикл и остается справедливым в каждой успешной итерации благодаря строке 9. В строках 5-8 значение переменной lс изменяется таким образом, что становится корректным значение сг [9]. В цикле в строках 5-б выполняется поиск по всем значениям lс Е Е я' [д — 1], пока не будет найдено такое значение, для юторого Р [lс + 1] = Р [9]. В этот момент й является наибольшим значением в множестве Ес м поэтому, согласно следствию 32.7, величину я [9] можно положить равной 1с + 1.
Если же искомое значение lс не найдено, в строке 7 выполняется присваивание й = = О. Если Р [1] = Р [д], то мы должны присвоить значение 1 как й, так и я [д]; в противном случае переменную Й следует оставить неизменной, а величине сг [д] присвоить значение О. В любом случае в строках 7-9 величинам lс и я [д] присваиваются правильные значения. На этом доказательство корректности процедуры Сомготе Ридах Рглчспон можно считать завершенным. Корректность алгоритма Кнута-Морриса-Пратта Процедуру КМР МАтснлк можно рассматривать как видоизмененную реализацию процедуры Рппте Аитомлтон МАтснек.
В частности, мы докажем, Доказалсельслгво. Если множество Ес 1 пустое, то не существует значений гс Е е сг' [д — Ц (включая Й = О), для юторых строку Рь можно расширить до строки Рь+1 и получить собственный суффикс Рс, Следовательно, сг [д] = О. Если множество Е 1 не пустое, то для каждого значения й е Е 1 справедливы соотношения гс+ 1 < 9 и Рь+1 ~ Рс. Следовательно, из определения сг [9] мы имеем 1044 Часть ЧП.
Избранные темы что код в строках 6-9 процедуры КМР Млтснек эквивалентен строке 4 процедуры Рмтк АитомАтон МАтснек, в которой переменной д присваивается значение б(д, Т [1]). Однако вместо того, чтобы использовать сохраненную величину 6(д,Т [1]), она вычисляется по мере необходимости с помощью функции я. Поскольку ранее было показано, по процедура КМР МАтСнен имитирует поведение процедуры Р!%те АБтОМАтОН МАтснек, корректность процедуры КМР МАтснек следует из корректности процедуры Р1н1те АитомАтон МАтснек (и вскоре станет понятно, почему в процедуре КМР МАтснен необходима строка 12). Корректность процедуры КМР Млтснеи следует из утверждения, что должно выполняться либо соотношение Б (д, Т [1]) = О, либо соотношение 6 (д, Т [1]) — 1 Е Е к" [д].
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
