Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 213
Текст из файла (страница 213)
Эти данные предварительно вычисляются и заносятся в массив я, так что я [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 8> Следующий символ совпадает 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. Благодаря ее наличию при каждом выполнении тела цикла 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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
