|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[257] из этих итераций можно считать равной 0(1). Для этого в качестве потенциала будем рассматривать значение к в момент входа в цикл. Поскольку начальное значение к равно нулю, а последующие равны ir[q] 0, реальная стоимость (время выполнения) всех итераций оценивается суммой учётных стоимостей, если считать учётной стоимостью сумму реальной стоимости и изменения потенциала. Реальная стоимость каждой итерации складывается из стоимости присваиваний в строке 6, присваивания в строке 8 и присваивания в строке 9. Поскольку ir[j] < j для всех j, при каждом присваивании в строке 6 потенциал уменьшается по крайней мере на 1, что компенсирует работу по выполнению действий в цикле while, если умножить потенциал на достаточно большую константу. Поэтому вклад цикла while в учётную стоимость есть 0(1); присваивания же в строках 8 и 9 выполняются не более, чем по разу каждое, и увеличивают потенциал не более чем на две единицы. Поэтому учётная стоимость каждой итерации цикла for есть 0(1), а стоимость всей процедуры есть 0(т). Аналогичное рассуждение, в котором в качестве потенциала выбирается q, показывает, что время выполнения строк 5-12 процедуры KMP-Matcher есть О (га). Стало быть, время выполнения всей процедуры KMP-Matcher есть О (то + га). Это - выигрыш по сравнению с алгоритмом Finite-Automaton-Matcher, который даже при экономном вычислении функции 6 требует времени 0(то£ + га). 34.4.3. Префикс-функция вычисляется правильно Начнем с важной леммы, показывающей, что, итерируя префикс-функцию, можно для данного q найти все такие к, что Pj~ является суффиксом Pq. Именно, для данного q положим 7г°[д] = д, а 7гг[д] = 7т[7Гг-1 [д]]) и 7rf[g] = 0 (такое t найдется, так как ir[j] < j для всех j; на этом месте итерации обрываются). Лемма 34.5 (Лемма об итерациях префикс-функции) Пусть Р - строка длины то с префикс-функцией 7Г. Тогда для всех q = 1, 2,..., то имеем 7г*[д] = { к : Р □ Pq }. Доказательство. Покажем сначала, что вательности Pq, Рж[ч], Pv[-K[q\], является суффиксом предыдущего (и, следовательно, всех предыдущих). есть Рис. 34.10 Подпись: Рис.34.10. К лемме 34.5 (Р = ababababca, q = 8). (а) Функция тг, связанная со строкой Р. Имеем 7г[8] = 6, 7г[6] = 4, 7г[4] = 2, 7г[2] = 0, так что 7Г*[8] = {8,6,4,2,0}. (б) Сдвигая строку Р относительно самой себя слева направо, отмечаем моменты, когда префикс Рк С Р является суффиксом строки Pg (совпадающие символы выделены серым и соединены вертикальными отрезками; пунктирная линия нарисована справа от Pg). Это происходит при к = 8, 6, 4, 2, 0, что совпадает со множеством 7Г*[8]. Покажем теперь, что и наоборот, { к : Рк □ Pq } С 7г*[д]. Рассуждая от противного, обозначим через j наибольший элемент множества {к : Рк □ Pq} \ K*[q]. Очевидно, j < q; раз j не лежит в последовательности 7г*[д], то j попадает между двумя её членами: j > j > 7Г[j] для некоторого j £ тг*[д]. Обе строки Pj и Pji являются суффиксами Рд: первая - по выбору j, вторая - в силу соотношения (34.6). Стало быть, Pj □ Pji по лемме 34.1, и Pj является префиксом строки Р, который является (собственным) суффиксом строки Pji и имеет длину больше тгЦ], что противоречит определению функции тг. Рис. 34.10 иллюстрирует доказанную лемму. Лемма 34.6 Пусть Р - строка длины то с префикс-функцией тг. Тогда n[q] - 1 £ TT*[q - 1] для всех q = 1, 2,..., то. для которых n[q] > 0. Доказательство. Если к = n[q] > 0, то Р □ Pq, откуда, отбрасывая последний символ, получаем, что Pk-i □ Pq-i- По лемме 34.5 это означает, что 7r[g] - 1 £ K*[q - 1]. Для q = 2, 3,..., то определим множества Eq-\ формулой (словами: Eq-\ состоит из таких к, что Pk - суффикс Pq-i, и за ними идут одинаковые буквы Р[/г + 1] и P[q], так что Pk+i - суффикс Следствие 34.7 Пусть Р - строка длины то с префикс-функцией тг. Тогда для всех q = 2, 3,..., то имеем: Доказательство. Если г = 7r[g] 1, то P[r] = P[q]; кроме того (лемма 34.6), г - 1 £ n*[q - 1], так что г - 1 £ Eq-\. Отсюда ясно, что если Eq-\ пусто, = { к : к £ тг*[д - 1] и Р[к + 1] = P[q] } 0,если Eq-i = 0; 1 + max{ к £ Eq-i }, если Eq-\ ф 0. то ir[q] = 0, и что если Eq \ непусто, то 7r[g] 1 + max{, k £ Eq \ }. Осталось показать, что если к £ Eq-i, то ir[q] к-\-1 - но это ясно, поскольку в этом случае Pk+i есть суффикс Pq (как мы отмечали после определения Eq \. Теперь мы можем завершить доказательство правильности процедуры Compute-Prefix-Function, всех q. Докажем индукцией по q следующее утверждение: при входе в цикл, начинающийся в строке 4, выполнено равенство к = ir[q - 1]. При q = 2 это обеспечивается присваиваниями в строках 2 и 3. Шаг индукции: пусть к = ir[q - 1] при входе в цикл, тогда нам достаточно доказать, что при выходе из цикла будет к = ir[q]. В самом деле, в строках 5-6 ищется наибольший элемент множества Eq-\; если это множество непусто (это равносильно тому, что Р[к + 1] = P[q] при выходе из цикла в строках 5-6), то после присваивания в строке 9 число к оказывается равным ir[q] ввиду следствия 34.7. Если же это множество пусто (по выходе из цикла в строках 5-6 оказалось к = 0 и Р[к + 1] ф -Р[д]), то оказывается 7г[д] = 0, что также верно (следствие 34.7). 34.4.4. Алгоритм КМР правилен Доказательство правильности процедуры KMP-Matcher проходит по той же схеме, что и для процедуры Compute-Prefix-Function. Достаточно (индукцией по г) доказать такие утверждения: • В момент исполнения строк 10-12 выполнено равенство q = • Перед каждым исполнением тела цикла (строки 6-12) выполнено равенство (здесь cr(Tj) - длина наибольшего префикса Р, являющегося суффиксом Tj). Заметим, что при г = 1 второе утверждение верно. Покажем теперь, что при каждом г из второго утверждения следует первое. В самом деле, пусть при некотором г второе утверждение верно. Лемма 34.5 показывает, что в строках 6-7 перебираются в убывающем порядке элементы множества S = {к < т : Р □ Pq}, причем перебор обрывается либо при нахождении наибольшего к £ S, для которого Р[к + 1] = Г [г], либо при к = 0 и Р[1] ф Т[г\. В первом случае по выходе из цикла в строках 6-7 q равняется наибольшему к, для которого Pk □ Ti-i и Pk+i □ Гг-; ясно, что к + 1 = ст(Гг-), и после исполнения строки 9 значение к + 1 присваивается переменной q. Во втором случае по выходе из цикла в строках 6-7 имеем, 7Г[ТО], если <t(T8 i) < тп; если <t(T8 i) = тп. |
Среды: Smalltalk80 MicroCap Local bus Bios Pci 12С ML Микроконтроллеры: Atmel Intel Holtek AVR MSP430 Microchip Книги: Емкостный датчик 500 схем для радиолюбителей часть 2 (4) Структура компьютерных программ Автоматическая коммутация Кондиционирование и вентиляция Ошибки при монтаже Схемы звуковоспроизведения Дроссели для питания Блоки питания Детекторы перемещения Теория электропривода Адаптивное управление Измерение параметров Печатная плата pcad pcb Физика цвета Управлении софтверными проектами Математический аппарат Битовые строки Микроконтроллер nios Команды управления выполнением программы Перехода от ahdl к vhdl Холодный спай Усилители hi-fi Электронные часы Сердечники из распылённого железа Анализ алгоритмов 8-разрядные КМОП Классификация МПК История Устройства автоматики Системы и сети Частотность Справочник микросхем Вторичного электропитания Типы видеомониторов Радиобиблиотека Электронные системы Бесконтекстный язык Управление техническими системами Монтаж печатных плат Работа с коммуникациями Создание библиотечного компонента Нейрокомпьютерная техника Parser Пи-регулятор ч.1 ПИ-регулятор ч.2 Обработка списков Интегральные схемы Шина ISAВ Шина PCI Прикладная криптография Нетематическое: Взрывной автогидролиз Нечеткая логика Бытовые установки (укр) Автоматизация проектирования Сбор и защита Дискретная математика Kb радиостанция Энергетика Ретро: Прием в автомобиле Управление шаговым двигателем Магнитная запись Ремонт микроволновки Дискретные системы часть 2 | ||