Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 232
Текст из файла (страница 232)
В качестве примера на рис. 32.11,(а) приведена полная префиксная функция к для образца аЬаЬаса. Алгоритм поиска подстрок Кнута — Морриса-Прагга приведен ниже в виде псевдокода процедуры КМР-Млтснпк. В основном, как вы увидите, эта процедура вытекает из процедуры Гггсгтп-Аотомлтогч-Млтснлк. В процедуре КМР- Глава 32. Поиск лодсмрок !05! г. Г-з г-~Г Рз Гв:.Ь.)л,т ь а с а Рг [а]Ь а Ь а с а к[5[ = 3 я[3[ = 1 в!а Ь а Ь а с а л[Ц=О (в) (б) Млтсней вызывается вспомогательная процедура Сомрт)те-ркертх-рптчстю)ч, в юторой вычисляется функция и. КМР-МАтснен [Т, Р) 1 п = Т.1епдФ 2 пз = Р.1епд~)г 3 и = СОмрпте-Рйенх-г'тлчст!О)ч [Р) 4 д= О // Количество совпадающих символов 5 Тогз =1топ // Сканирование текста слева направо б зеЫ)е д > О и Р[д + Ц уб Т[з] ? д = зг[д] // Следующий символ не совпадает 8 й' Р[д + 1] == Т[з] 9 д = д+ 1 // Следующий символ совпадает 10 1Тд==т // Совпадает ли весь образец Р? 11 рппт "Образец находится со смещением" з — гп 12 д = л[д] // Ищем следующее совпадение Рнс.
32.П. Иллюстрация леммы 32.5 для образца Р = аЬаЬаса и О = 5. (а) Функция а для указанного образца. Поскольку гг[5[ = 3, к[3[ = 1 и к[Я = О, итернруя гг, получаем гг [5] = 13, 1,0). (б) Мы смещаем образец Р вправо и замечаем, югда некоторый префикс Р» образца Р соответствует немпорому истинному суффиксу Ры мы получаем соответствие при )г = 3, 1 и О, На рисунке в первой строке приведен образец Р, а пущттнрная вертикальная линия проведена после Рб. Последовательные строки показывают все сдвиги Р, юторые приводвт к тому, что некоторый префикс Р» строки Р соответствует некоторому суффиксу Р,.
Совпадающие символы выделены штриховкой и соединены вертикальными линнлми. Таким образом, [тг: )г < 5 и Р» Л Рз) = (3, 1, 0). Лемма 32.5 утверждает, по л'[д[ = [тг: тг < д и Р» ~ Р, ) для всех о. 1052 Часть ГП. Иэбраниые теаы Сомег5те-Ркеегх-Гомстгом(Р) 1 т = Р.1епдй 2 Пусть к[1., т] — новый массив 3 я[1]=О 4 )с=О 5 Когд = 2гот 6 ьгпйе гс > 0 и Р[!с + 1] ~ Р[9] 7 lс = к[ге] 8 Ы Р[к + 1] == Р[9] 9 )с = 1+1 10 к[9] = й 11 гегцгп л Эти две процедуры имеют много общего, поскольку обе сравнивают строки с образцом Р: КМР-МАтснек сопоставляет текст Т с образцом Р, и СОмготеРкеегх-Рг5мстгом — образец Р с самим собой.
Начнем с анализа времени работы этой процедуры. Доказательство ее юрректности окажется более сложным. Анализ времени работы С помощью методов группового анализа (см. раздел ! 7.1) можно показать, что время работы процедуры Сомготе-Ркеегх-Рг5мстюм равно В(т). Единственной тонкостью при этом является показ того, что всего цикл згййе в строках 6 и 7 выполняется 0(т) раз. Покажем, что он делает не более т — 1 итерации. Начнем с некоторых наблюдений над величиной гс. Во-первых, в строке 4 значение к равно О, а единственный путь увеличения )с — операция инкремента в строке 9, выполняемая не более одного раза за итерацию цикла 1ог в строках 5 — 10.
Таким образом, общее увеличение Iс составляет не более т — 1. Во-вторых, поскольку lс < д до входа в цикл Гог и каждая итерация цинка увеличивает д, всегда выполняется к < 9. Следовательно, присваивание в строках 3 н 10 гарантирует, что к[9] < 9 для всех 9 = 1, 2,..., т, что означает, что каждая итерация цикла ьгййе уменьшает к. В-третьих, )с никогда не становится отрицательным. Объединив эти факты, мы видим, что общее уменьшение )с в цикле згййе ограничено сверху общим увеличением )с во всех итерациях цикла 1ог, которое составляет т — 1. Таким образом, общее юличество итераций цикла згййе не превышает гп — 1, и время работы процедуры Сомеоте-Ркеегх-Римст!О!с составляет сз(т).
В упр. 32.4.4 предлагается показать с помощью аналогичного группового анализа, что время сравнения процедуры КМР-МАтснвк равно сг(п). Благодаря использованию функции я вместо функции 6, которая используется в процедуре Р!!с!те-АотомАтогс-МАтснек, время предварительной обработки образца уменьшается с 0(т ]Е[) до сг(т), при том что время фактического сравнения остается ограниченным сг(п). 1033 Глава 32. Поиск коосерок Корректность вычисления префиксной функции Немного позже мы покажем, что префиксная функция л помогает имитировать функцию переходов б в автомате поиска подстрок.
Но сначала докажем, что процедура СОмРОтл-Ркеггх-РО1чст1111ц действительно корректно вычисляет эту функцию. Для этого найдем все префиксы Ры являющиеся истинными суффиксами данного префикса Рц. Значение л[о) дает наибольший такой префикс, но следующая лемма, проиллюстрированная на рис. 32.11, показывает, что, итерируя префиксную функцию л, фактически можно перечислить все префиксы Ры являющиеся истинными суффиксами Р . Положим л" [0] = (л ц, л ~ ) [0), л1 1 [д],..., л1 ) [д] ), где л1О ц определена в терминах функциональной итерации, так что лш) [д] = о и лб)Ц = гг[лб 11[0]] для 1 > 1, и где последовательность л*[д] останавливается по достижении ггр) [0] = О.
Лемма 32.5 1Леима об итерации нрефиксиой функции) Пусть Р— образец длиной т с префиксной функцией л. Тогда для 7 = 1, 2,..., пз имеем л*[д] = (Гс: lс < си Рь 1РД). Доипательство. Сначала докажем, что л*[д) С (гс: lс < о и Рь \ Р ) или, что эквивалентно, из 1 е л*[г1) следует Р; л Рц .
(32.7) Если 1 е я*[о), то г = л~ ~ [0] для некоторого и > О. Докажем уравнение (32.7) по индукции по и. Для и = 1 имеем 1 = л[д), и наше утверждение следует из того, что 1 < о и Р 101 1 Рц по определению л. используя отношения л[1] < 1 и Рку ' 1 Р, и транзитивность < и 1, устанавливаем справедливость утверждения для всех 1 из я*[0].
Следовательно, л*[г7] С (гс: гс < о и Рь 1 Рц). Теперь докажем, что ()с: 3с < д и Рь ~ Рц ) С л*[д), методом от противного. Предположим, что множество (к: и < о и Рь 1 Р ) — к*[о] непустое, и пусть 3 представляет собой наибольшее число этого множества. Поскольку л[о] является наибольшим значением в (к: lс < о и Рь 1Рц) и л[г7) Е л*[д), должно выполняться 3 < я[о), так что пусть 3о обозначает наименьшее целое из л* [о], большее, чем 31 (Можно выбрать 3о = л[о), если никакие другие числа в л*[д) не превышают 31) Имеем Р.
~ Рц, посколькУ 3 Е (гс: lс < си РЬ л Рц), и из 3о б л*[д) и уравнения (32.7) получаем Р ':1 Рц. Таким образом, Р '3 Р согласно лемме 32.1, и 3 является наибольшим значением, меньшим у' и обладающим этим свойством. Следовательно, должны выполняться я[3'] = 3 и, поскольку 3 Е л" [д], 3 Е л' [д). Это противоречие и доказывает лемму.
Алгоритм Сомгптк-Ркенх-Р131чст1О1ц вычисляет л[0] по порядку для о = 1, 2,..., гп. Присвоение л[1] значение О в строке 3 процедуры СомР13ТЕ-РкЕнхРОХСТ10Х, определенно, корректно, поскольку л[д) < г7 для всех о. Воспользуемся для доказательства того, что процедура Сомр13тк-Рквнх-РО1цстго1ц корректно вычисляет лЦ для о > 1, следующей леммой и ее следствием. 1054 Часть т11. Избранные темы Лемма 32.6 Пусть Р является образцом длиной лз и пусть зг представляет собой префиксную функцию для Р.
Если для 0 = 1,2,..., т выполняется л[д] > О, то л[о] — 1 б л' [Ч вЂ” Ц. Доказательство. Пусть т = л[д] > О, так что т < 9 и Р, ~ Рц; таким образом, т — 1 < 0 — 1 и Р, г ~ Рц г (отбРасываапоследниесимволыиз Р, и Р,что можно сделать, поскольку т > О). Таким образом„согласно лемме 32.5 т — 1 б л*[д — Ц. А значит, л[д] — 1 = т — 1 б гг*[9 — Ц. Определим для д = 2, 3,..., т подмножество Ец, С зг" [д — Ц как Ец г — — (й Е л*[Ч вЂ” Ц: Р',)г + Ц = Р[д]) = (й: й < 0 — 1и Рь 1Рц г и Р[й+ Ц = Р[9]) (из леммы 32.5) = (й: й < Ч вЂ” 1 и Рь+г ~ Рц) . Множество Ец г состоит из значений й < 0 — 1, для которых Рь ) Рц г и для которых имеем Рь+г ~ Рц, поскольку Р[1с + Ц = Р[9].
Таким образом, Ец г состоит из значений й Е к*[9 — Ц, таких, что можно расширить Рь до Рььг и получить истинный суффикс Рц. Саедегввие 32. 7 Пусть Р является образцом длиной гп и пусть л представляет собой префиксную функцию для Р. Для ц = 2, 3,..., гп О, если Ец г = й, [ 1+гпах(й е Ец г), если Ец г т-й Доказатеаьеагво. Если Ец г — пустое множество, не существует й е л*[д — Ц (включая й = О), для которого можно расширить Рь до Рьог и получить истинный префикс Рц. Следовательно, л[д] = О. Если множество Ец г непустое, то для каждого й е Е г имеем й + 1 < г) и Рь+г ~ Рц. Следовательно, из определения л[о] имеем л[д] > 1+ шах(й б Е г) (32.
8) Заметим, что зг[0] > О. Пусть т = зги] — 1, так что т + 1 = зг[0] и, следовательно, Р,ц.г З Рц. Поскольку т + 1 > О, имеем Р[т + Ц = Р[г)]. Кроме того, согласно лемме 32.6 имеем т Е л'[0 — Ц. Следовательно, т Е Ец и и, таким образом, т < шах (й б Ец г), или, что эквивалентно, л[9] < 1+ игах(й е Ец г) (32.9) Объединение уравнений (32.8) и (32.9) завершает доказательство. Глава 32.
Поипг ггодстрон Теперь завершим доказательство того, что процедура СОмРБте-Ркег!хРигчстгОгч корректно вычисляет функцию я. В этой процедуре в начале каждой итерации цикла Гог в строках 5-10 выполняется равенство )г = л[ц — 1]. Это условие обеспечивается строками 3 и 4 во время первого вхождения в цикл и остается справедливым в каждой последующей итерации благодаря строке 10. В строках 6 — 9 значение переменной )г изменяется таким образом, что становится равным корректному значению я[ц].
В цикле зчй11е, в строках 6 и 7, выполняется поиск по всем значениям я Е я*[ц — 1), пока не будет найдено такое значение я, для которого Р[)г + 1) = Р[ц]. В этот момент я является наибольшим значением множества Еч г, так что согласно следствию 32.7 величину я [ц] можно положить равной )г + 1. Если же искомое значение к Е л" [ц — 1), такое, что Р[к + 1] = Р[ц), в цикле этййе ие найдено, в строке 8 1г равно нулю. Если Р[1) = Р[ц), то необходимо присвоить значение 1 как Й, так и я[ц]; в противном случае переменную и следует оставить неизменной, а величине л[ц) присвоить значение О, В любом случае в строках 8-10 переменные Е и я[ц) получают правильные значения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
