AOP_Tom3 (1021738), страница 138
Текст из файла (страница 138)
Заметим, однако, что среднее число проверок битов при случайном неудачном поиске ие так просто связано с длиной внешнего пути дерева, поскольку неудачный поиск с большей вероятностью оканчивается во внешнем узле недалеко от корня. Так, вероятность достижения левой ветви узла 0075 на рис. 35 равна -' (при рассмотрении ключей с бесконечной точностью), а вероятность попадания в левую ветвь узла ОЯУЯ составляет лишь †'. Из-за этого деревья цифрового поиска при равномерном распределении ключей в целом лучше сбалансированы, чем бинарные деревья поиска из алгоритма 5.2.2Т. Рнс. 35.
Дерево случайного цифрового поиска, построенное по алгоритму 11. Для описания соответствующих характеристик деревьев цифрового поиска можно воспользоваться производящей функцией. Пусть на уровне 1 находится ся внутренних узлов. Рассмотрим производящую функцию а(з) = 2 ', а~ "'. Допустим, что производящая функция, соответствующая рис. 35, — а(г) = 1 + 2г + 4вв + 5гз + 4г'.
Если на уровне 1 находится 6~ внешних узлов и 6(г) = ~,6~в', то согласно упр. 5.2.1 — 25 получаем 6(г) = 1 + (2г — 1) а(з). (7) Например, 1 + (2т — 1)(1 + 2т + 4гз -~- 5гз + 4гх) = Ззз + бзэ + Явь. Среднее количество проверок битов при случайном успешном поиске равно а'(1)/и(1), так как а'(1) — длина внутреннего пути дерева, а а(1) — количество внутренних узлов. Среднее количество проверок битов при случайном неудачном поиске составляет ~ ~16|2 ' = -'6'(-') = а(-'), поскольку мы достигаем данного внешнего узла уровня 1 с вероятностью 2 '. Количество сравнений совпадает с количеством проверок битов (плюс 1 при успешном завершении поиска).
Например, на рис. 35 при успешном поиске будет выполнено в среднем 2Д проверок битов и 3 —,"е сравнений, в то время как в случае неудачного поиска обе эти величины будут равны 31. Обозначим через дм(з) усредненную по всем деревьям с Х узлами функцию а(г); другими словами, дм(г) представляет собой сумму 2 ртат(-) по всем бинар- Ул~+1(з) Ул (з) + 1 + (з 1)Ул (уэ)~ Уо(з) О. С соответствующей производящей функцией для внешних узлов, (8) Ьм(з) = 1+ (2з — 1)дл(з), работать несколько легче в связи с тем, что (8) эквивалентно формуле ЛлЧ-з(г) = Ьл(в)+ (2з — 1)йл (зз); Ьо(з) = 1 Многократно применяя это правило, находим, что Ьл+1(г) = Ьл 1(э) + 2(2з — 1)бм 1(~1з) + (2г — 1)(г — 1)бл 1Яг) = Ьм з(в) +3(2г — 1)бм з(ув) +3(2з — 1)(з — 1)бл з(-'г) + (2э — 1)(г — 1) ($г — 1) бл з Яг) и т.
д, В результате имеем следующее: ь-1 6 ( ) = Е ( „) П(2' ' — ); э ";=о ь-1 ( ) =к(~,) й(2 ' — 1). ь>о у=о (10) Например, У4(з) = 4+6(г — 1) +4(г — 1)(1э — 1) + (г — 1)Яз — 1)(фз — 1). Эти формулы позволяют выразить искомые величины в виде сумм произведений: ь Сю =дл(1) = Е (~. 21 П(2 1)' ьйо 1=1 дл(з1) = ~ ~( ) П(2 ' — 1) =Си+1 — Сл. ь>о (12) (13) Совершенно неочевидно, что этн формулы для Сл удовлетворяют (6)! К сожалению, данные выражения непригодны для вычислений или поиска асимптотических зависимостей, поскольку 2 э — 1 отрицательно; мы получим большие ным деревьям цифрового поиска Т с Ж внутренними узлами, где ат(т) — производящая функция для внутренних узлов дерева Т, а рт — вероятность того, что Т образуется при вставке Ж случайных чисел согласно алгоритму В.
Тогда среднее количество проверок битов будет равно дл (1)/Х в случае успешного и ум(1) — в случае неудачного поиска. Можно вычислить дм(л) при помощи имитации процесса построения дерева следующим образом. Если а(з) представляет собой производящую функцию для дерева с Х узлами, можно сформировать из него Л'+ 1 дерево методом вставки в позицию любого внешнего узла. Эта вставка производится в данный внешний узел уровня 1 с веронтностью 2 ', следовательно, сумма производящих функций для Х+! нового дерева, умноженная на вероятность ее появления, равна а(з) + 6(з г) = а(з) + 1 + (э — 1) а(-'г). Усреднение по всем деревьям с Л узлами дает члены, многие из которых сократятся. Более полезная формула для См может быть получена в результате применения тождеств из упр.
5.1.1-15: = Ц( — ')~Е(,' )(-)" Е( " ')™Ц(1 — 2")' ~>1 ~ ь>е гойе г=1 = ~ г"*(~ ~"„)(-2- )' — 1+2-"Х) Ц(1-2- -'"-') >о 2-~(~-1)/2 2 ((1-2 ) — 1+2 Х) ~~~ ( — 2 '" ')" . (14) . >о п>а Г(,",( — -") На первый взгляд, никакого улучшения по сравнению с (12) не произошло, однако очень большое достоинство полученного результата заключается в том, что сумма по т довольно быстро сходится для любого фиксированного и. Аналогичная ситуация возникает и в случае луча в формулах 5.2.2 — (38) и 5.2.2 — (39); в самом деле, при рассмотрении только членов с и = 0 из (14) получается в точности Л вЂ” 1 плюс количество проверок битов в бинарном луче.
Теперь можно получить асимптотическое значение так же, как и ранее (см. упр. 27). (Приведенный вывод базируется, в основном, на подходе, предложенном в работе А. 3. Коппеип, О. Я. 1четлпап, Ргзсгесе Маепешас1св 4 (1973), о7 — 63). М М с Рис. 36. Дерево, которое строится алгоритмом "Патриция" вместо луча, приведенного на рис. 34. И, наконец, бросим на метод "Патриция" "математический" взгляд. В таком случае бинарное дерево похоже на соответствующий луч с теми же ключами, но сжатыми вместе (поля ЯК1Р позволяют устранить однопутевые ветвления), так что всегда имеется ровно Ьт — 1 внутренних узлов и Н внешних узлов.
На рис. 36 показано дерево метода "Патриция", соответствующее шестнадцати ключам луча, представленного на рис. 34. Число, показанное в каждом узле ветви, представляет собой значение ЯК1Р; ключи расположены у внешних узлов, хотя они и не присутствуют в дереве явно (в действительности на месте каждого внешнего узла имеется ссылка на внутренний узел, который, в свою очередь, ссылается на массив ТЕХТ). Впрочем, для целей анализа будем считать, что внешние узлы имеют именно такой вид, как показано на рисунке, Поскольку успешный поиск с использованием метода 'Патриция" завершается во внешних узлах, среднее количество проверок битов, выполненных при случайном успешном поиске, будет равно длине внешнего пути, деленной на Х Если сформировать, как и ранее, производящую функцию Ь(г) для внешних узлов, то эта величина может быть представлена как Ь'(1)/Ь(1).
Неудачный поиск с использованием метода "Патриция" также заканчивается во внешнем узле уровня 1 с вероятностью 2 ', так что среднее количество проверок битов составляет -'Ь'(1). Например, для случая, представленного на рис. 36, мы имеем Ь(г) = Згз + 8г + Згз+ 2ге; таким образом, среднее число проверок битов при успешном поиске равно 4-' и при неудачном — Зы. Обозначим через Ь„(г) "среднюю" производящую функцию Ь(г), т.
е. функцию, усредненную по всем деревьям метода "Патриция' с и внешними узлами и равномерно распределенными ключами. Рекуррентное соотношение Ь„(г) =2' "~~ ( )Ьь(г)(г+бь„(1 — г)), Ье(г) =О, Ь|(г) =1, (15) по-видимому, не имеет простого решения; но, к счастью, существует простое рекур- рентное соотношение для средней длины внешнего пути Ь'„(1), поскольку Ь'„(1) = 2з " ~ ( ) Ь'„(1) + 2' " ~~~ ( ) й(1 — бь„) (16) Так как оно имеет вид (6), для поиска Ь'„(1) можно использовать ранее разработанные методы. Оказывается, Ь'„(1) ровно на и меньше соответствующего числа проверок битов в случайном бинарном луче. Следовательно, поле ЯК1Р позволяет сэкономить около одной проверки бита при удачном поиске случайных данных (см.
упр, 31). Избыточность же типичных реальных данных приведет к еще большей экономии. Если попытаться найти среднее количество проверок битов в случае неудачного поиска методом "Патриция", получится рекуррентное соотношение 1 /п~ а„= 1+ — ~~~ ~ ~аь для и > 2; ае = а~ — — О 2" — 2 1Ь! (17) ьк» (здесь а„ = 1Ь'„(г)). Это соотношение не похоже ни на одно из РассмотРенных выше рекуррентных соотношений н не сводится к ним каким-либо более или менее простым способом.
Однако теория преобразований Меллина, приведенная в разделе 5.2.2, обеспечивает возможность работы с такого рода рекуррентными соотношениями. Оказывается, решение (17) содержит числа Бернулли: н — ! †и+2= ( ) „, дляп>2. (18) Эта формула, вероятно, представляет собой самый твердый агимптотический оре- шек, который был разгрызен в данной книге. Решение, представленное в упр. 34, является поучительным обзором многих ранее встречавшихся задач (с некоторыми нюансами). УПРАЖНЕНИЯ 1. [00] Если дерево имеет листья, то что имеет луч? 2. [00] Разработайте алгоритм вставки нового ключа в М-арный луч с использованием соглашений алгоритма Т.
3. [01] Разработайте алгоритм удаления ключа из М-ерного луча с использованием соглашений алгоритма Т. 4. [01] Большинство нз 360 элементов, приведенных в табл. 1, представляет собой пустые ссылки. Однако можно сжать таблицу до 49 элементов, перекрыв непустые и пустые Итоги анализа. Следующие результаты сложных математических выкладок этого раздела заслуживают особого ннимания.
а) Количество узлов, которые необходимы для хранения Х случайных ключей в М-арном луче с разветвлениями, прекращающимися по достижении подфайлов из < в ключей, составляет примерно?У/(в !и М). Это приближение справедливо при больших 1У, малых з и малых М. Поскольку узлы луча содержат М полей ссылок., всего при з = ЛХ потребуется около Х/!и ЛХ полей ссылок.
Ь) Количество цифр или символов, проверяемых в ходе слу ~а ного поиска, составляет для всех рассмотренных методов примерно !обм?У. При ЛХ = 2 различные методы анализа дают более точные приближения для количества проверок битон. Успешный Неудачный Поиск по лучу !8 Ж + 1,33275 !к Лт — 0.10995 Цифровой поиск по дереву !8 Х вЂ” 1.71бб5 !я?У вЂ” 0.27395 Поиск методом "Патриция" !8 Лг + 0.33275 ]8 Х вЂ” 0.31875 (Эти приближения могут быть выражены фундаментальными математическими постоянными; например, 0.31875 на самом деле означает (!п я — 7)/1и 2 — 1/2).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
