Теория синтаксического анализа, перевода и компиляции - Том 2 (943929), страница 59
Текст из файла (страница 59)
Тогда индексная ячейка;я ли 2, р ° ис:ак которая па рис. 10.13 указывает на Ои„включается в сщ пересечений своей таблицы, Измененрмя отражены на Р ыс. 10. 14. Дадим теперь алгоритм с помощью которого из тяблищ ;цш Т выбирается свойство индекса р. Зтот а.рлгорнтм используетг тгсм в алгоритме 10.3 для нахождения свойства индексов в саиске, Р ,пересечений, ~с,л ГРАИАЛАтики сзонста Гл ~ь оРглнизАция ииаолмА~гии Р (л! 1 2 1а ббээб Рнс 10.14.
Тлблннн после лереньсл. 315 Э!4 Алгоритм 10 4. Н ах олкдеиие свойства индекса. Вход. Индексная ячейка некоторой таблицы Т. Предполагаем, что таблиды имеют ту же структуру, что н в алгоритме 10.3. Выход. Свойство этого индекса в таблице Т. Мепгад. (1) Проходим по указателям из данной индексной ячейки до корня дерева, в которое она входит. Формируем список асех ячеек, встретившихся на этом пути. (2) Помещаем в каждую ячейку иа этом пути, кроме корня, ссылку прямо на этот корень. (Конечно, ячейка на этом пути, непосредственно предшествующая корню, уже ссыпается на него).
р) Отметим, что наиболее важен шаг 2 алгоритма !0.4, являющийся по существу »побочным эффектом" алгоритма. Именно шаг (2) гарантирует, что общее время, потраченное на обработку таблицы, а целом будет пропорционально длине входа. 10.2.4. Анапнз ангаритма обработки таблиц Оставшаяся часть этой главы посвящена анализу временнбй сложности алгоритмов 10.3 и 10.4. Определим сначала две функции Р и 6, которые нам понадобятся в этой главе.
Определение. Р (и) определим рекуррентно: Г (1)-1 Р (и) =-2ег"-'! Некоторые значения Р(п) приведены в табл. 10.3. Тлб» Чл Ю,З Опредзлиы 0(п) как наименьшее из целых чисел!, для которых Г б) ~ л. Функция 0 растет так медленно, что реально 0 (п) й.:б для всел и, представимых одним машинным словом, даже с плавающей точкой. С другой стороны, 6 (н) можно апре. делить как количество применений !оум к п для того, чтобы получить число, меньшее или равное О.
Оставшаяся часть главы посвящена доказательству того, что алгоритм 10.3 требует 0(п0(п)) шагов вычислительной машины с пронэзолшпым доступом при длине входной цепочки, равной и. Покажем сначала, что, если не считать время, затрачиваемое на алгоритм 10.4, временная сложность алгоритма 10.3 составляет О(п).
Лемма !0.3. Если не считать обращениб к алеоритму 10.4, то илгорипш 10.3 можно реализсвить на вычислительнод машине с произвольным доступом за время 0(п), еде и — длина разбираемой входной цепочки. Д о к а з а т ел ьс т в о. Каждое выполнение части 1 требует фиксированного количества времени, а таких выполнений в точности и. Отметим, что шаги (!) и (а) в части 2 требуют времени, пропорционального длине списка пересечений.
(Напомним еще рав, что время работы алгоритма 10.4 не учитывается.) Но едияственный способ поисиа по индексной ячейке пути в списке пересечений заключается в выполнении части 1. Каждое выполнение части 1 размыцает не более одной индексной ячейки в списке пересечений. Текил! образом, во все списки пересечений всех таблиц помещается не более п индексов. После вмполнепвя части 2 все индексные ячейки удаляются из списка пересечений, гл и орглниззцня янвормхцигг так что общее время, затрачиваемое на шаги (1) и (б) части 2, составляет 0(л).
Легко видеть, что остальные шаги части 2 требуют постоян- ного количества времени на одно выполнение части 2. Поскольку часть 2 выполняется в точности л --1 раз, можно заключить, что общее время, затрачиваемое алгоритмом 10.3, не считая вызонав алгоритма 10.4, составляет 0(л). С) Поставим теперь некоторую абстракткую задачу и дадим ее решение, отражающее идеи алгоритмов 10.3 и 10.4, в терми- нах, более абстрактных и легче полдаюшихся анализу. Определение.
Для оставшейся части главы опрелелим задачу слияния лгяожеслы как (1) набор объектов а„..., а„, (2) набор имея множеств, внлючающнй Ао Л,, ..., А„, (3) последовательность команд Уо ум ..., У„, причем каждая команда у, имеет форму (а) слить (А, В, С) или (б) найти (а), гле А, В и С вЂ” имена множеств, з а — объект. (Илгена многкеств можно мыслить как пары, состоящие из таб- лицы и свойства, а объекты — как индексные ячейки.) Команда слить (Л, В, С) формирует объединение нножеств А и В и получающемуся множеству дает имя С. При этом не генерируется никакого выхода.
Команда найти (а) печатает имя множества, элементом кото- рого является а. Вначале предполагается, что каждый объект а, принадлежит множеству Лг, т. е. А г= (а,) Отлетом лоследооагнсльыости команд зывается последователькость выходов, генери- руемая при последовательнои выполнении команд. Пример 10.12. Пусть заданы объекты а„ а„ ..., а, и после- довательность команд слить (Ао А,, А,) слить(Л„Ли А,) слить(Л,, Аз, Л,) слить(Л„Ао А,) слить(А„А,, Лд найти (а,) После выполнения первой командм множеством А, будет (а„а,). После второй команды А, = (а„, а,). После третьей множествоч А, станет (а„ а,).
Затем после команды слить(А„ А, А ) множестиет (ао ао а„аи. После последней команды слияния згь ш г гглммлтнки свояств А,=(ао а, „аз). Затем команла найти(а,) печатает имя А,, являющееся ответом иа эту пас тедовательность колганд. Теперь дадим алгоритм выполнении любой последователь.
ности команд длины 0(л) за время 0 (иб (л)), где л — число обьсктов. Относительно способа доступа к объентач и многкесгвам будут сделаны некогорые допугцения. Сразу пе очевидно, что реализация гоамматики свойств алгоритмами !О.З и !0.4 этим условиям удовлетворяет. Однако достаточно простых рассуждений, чтобы увидеть, что в действительности при необлодимогти определить свойства объектов (индексных ячеек) или слить мно. жества (заголовки свойств) они (объекты и мншкестаа) б)дуг доступны.
Алгоритм 10 б. Вычислен ие ответа на последов а. тельность команд. Вход. Набор объектов (ао .. а„) и последовательность команд )н ..,, )„описанного выше щша. Выход. Ответ на последовательность 1„ Метод. Мггожество запоминается в виде дерева, каждая вершина которого представляет один элемент множества. Корень дерева имеет метку, даюгцую (1) имя множества, представляемого деревом, и (2) чнсгю вершин этого дерева Уразмер).
Предполагается, что за конечное пгсло шагов можно найти вершину, представляющую объект, нли корень дерева, представляющего множество. Это иожно сделать, например, исгюльэуя два таких вектора ОВ)ЕСТ и 5ЕТ, что ОВ)ЕСТ(а) — указатель на вершину, представляюгцую а, а 5ЕТ (А) — указатель на корень лерева, представляющего множество А. Сначала строим л вершин, по одной для каждого объекта аг Вершина лли а, — это корень дерева с одной вершиной; корень помечен Аг и имеет размер 1. (1) Зля выполнения комаяды слить(А, В, С) определяем местополонсение корней деревьев лля А и В (с помоплью ЗЕТ (А) и ЗЕТ(В)).
Сравниваем размеры деревьев, указываемых с помощью Л и В. Корень меньшего дерева становится прялгылг потомком корня большего дерева (снязн нарушаются произвольно). Большему корто лается имя С, а его размерои становится сумма размеров А и В'). Указатель на корень С помеплается в ячейку 5ЕТ (С). ') Ангшогвя мсхолу згвм шагом н лронзлуров слияния влгорвтмз гаэ очеввдва. Рзззвчве в способе пслсчзгв ззкгю иегов талька в том, сзвгвсгсз ин ксрззь влв нег. В данном случае считается, з азгарнтме га.э нсз.
лгу гл ~о. орглиизлция ииаооылции (2) Для выполнения команды найти (а) определяем с помощью ОВйВСТ(а) вершину, представляющую а. Затем проходиы из вес в парень г этого дерева. Печатаем имя, найденное в г. Все вершины на этан пути, кроме г, делаем прямыми потом- качи г'). С) Пример 10.18. Рассмотрим последовательность кол»вид из примера 10.12. После выполнения первых трех команд слияния Яг Я» Ял ю.х. грлчлытики свояств Рпс 15.15. Деревья после трех команд спеть, получаются три дерева, изображенные на рис. 10.15.
Корни помечены именем множества и размером. (Размер не показан.) Затем, выполнив команду слить(А„ А„ А,), приходим к струк- и» т ре аа рис. 10.!б. П: оспе последней коман») Рпс 10.17. Дерево после по- спепоеэ коилолы спить. Рис 10.1б деревья после очередной ко- »лхлы спеть. получаем рис. 10.!7.
Вынолияя далее команду найти (а,), печатаеч имя А,, а вершины а, и а, делаем прямымн потомками корня (а, уже является прямым потомком). Окончательная структура приведена на рис. 10.18. С) ') Аналогия с гпгорхтиоы 10.4 должна быть очевпдзе. 313 Рпс.
10.18. Дерево пес.те команды лайте. Покажем теперь, что алгориты 10.5 может работать за время 0(пВ(п)) при разумном предположении, что выполнение команды слить требует одной единицы времени, а команды инда найти (а) времени, пропорционального длине пути от вершины, представляюпгей а, до корня. Всс последующие результаты выведены при этоы предположение. Начиная отсюда, будем считать, что число объектов и фиксировано и посдедовательность команд имеет длину 0(п). Определение. Определим Ранг вершины в структуре, вырабатываемой алгоритыом !0.5; (!) лист ил»еет ранг О, (2) если у вершины А» когда-либо появляется прямой потомон ранга л, то А' имеет ранг по крайней мере»+1, (8) ранг вершиаы — зто наименьшее целое число, удовлетворяющее условию (2).
Сразу нс ясно, что зто определение корректно. Однако если вершина М становится прямым потомком вершины М в алгоритме 10.5, то у М уже никогда больше не будет прямых потомков. Таким образом, в этот момент люжво зафиксировахь ранг»И. Например, на рис. 10.17 ранг вершины а, можно за. фиксировать равным 2, поскольку а, имеет одного примого потомка ранга 1, а новых потомков уже больше иметь не будет. Три следующие леммы устанавливают некоторые свойства ранга вершины, Лемма 10.4, Пугпш )х' — корень рины л, еоадаппый оторопи мгм 10.5.
Тогда А» имгепа по крайней мере 2' повомкое. Доказательство. Базис, л--О, очевиден, поскольку вершина тривиально является собственным патомколх. Дпя доказательства шага индукции предположим, что И вЂ” корень ранга х. Тогда в некоторый момент у вершины Ай должен появиться прямой аогомок М ранг໠— 1.
Кроме того, вершина М дол>хна была стать прямым потомком вершины А» иа шаго (1) алгоритма 10.5, поскольку иначе ранг вершины Аг был бы не менее 1-1-1. Ото»ода 31Е Гл )е ОРГАиизхция ииаормАции )е г Грлимлтиьи сван). в следует, что вершина М была корнем и по предположению индукции имела в тот момент по крайней мере 2) ' потомков, а на шаге (1) алгоритма 10.5 в тат момент вершина Л' имела ио крайней мере 2)-' потомков. Таким образам, после слиянии й' имеет по крайней мере 2' потомков.
До тех пор пока Л' остается корнем, ана не может потерять потомков. Г) Лемма 10.5. Если шр)ииии 5( в кикой-тс момент рибо)пм илгаритми 10.5 имеет прямого потолки М, то ранг й) бигыиг ранга М. Доказательство. 11рямая индукция по числу выполняемых номанд. С) Следу)ощая лемма дает гравии) числа вершин ранга 1, Лемма 10.6. Существует яг багге п2 ' гаршин ранга ).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
