члены, многие из которых сократятся. Более полезная формула для Сn может быть получена в результате применения тождеств из упр. 5.1.1-16:

Cn = ( П(1 - 2-)) е Ll2y- П(1 - ---Г

\j>i J к>0 1>0

Vj>l /)fc>0 + m>0 r=l

m>0 V / j>0

= J2 2"((l-2-")- 1 +

•\ - m - l\n

m>0

n>0

2-„(„ l)/2

n"=i(l-2-0

(14)

Ha первый взгляд, никакого улучшения по сравнению с (12) не произошло, однако очень большое достоинство полученного результата заключается в том, что сумма по т довольно быстро сходится для любого фиксированного п. Аналогичная ситуация возникает и в случае луча в формулах 5.2.2-(38) и 5.2.2-(39); в самом деле, при рассмотрении только членов с п = О из (14) получается в точности iV - 1 плюс количество проверок битов в бинарном луче. Теперь можно получить асимптотическое значение так же, как и ранее (см. упр. 27). [Приведенный вывод базируется, в основном, на подходе, предложенном в работе А. J. Konheim, D. J. Newman, Discrete AfatAematics 4 (1973), 57-63].

Рис. 36. Дерево, которое строится алгоритмом "Патриция" вместо луча, приведенного на рис. 34.

И, наконец, бросим на метод "Патриция" "математический" взгляд. В таком случае бинарное дерево похоже на соответствующий луч с теми же ключами, но

сжатыми вместе (поля SKIP позволяют устранить однопутевые ветвления), так что всегда имеется ровно iV - 1 внутренних узлов и N внешних узлов. На рис. 36 показано дерево метода "Патриция" соответствующее шестнадцати ключам луча, представленного на рис. 34. Число, показанное в каждом узле ветви, представляет собой значение SKIP; ключи расположены у внешних узлов, хотя они и не присутствуют в дереве явно (в действительности на месте каждого внешнего узла имеется ссылка на внутренний узел, который, в свою очередь, ссылается на массив TEXT). Впрочем, для целей анализа будем считать, что внешние узлы имеют именно такой вид, как показано на рисунке.

Поскольку успешный поиск с использованием метода "Патриция" завершается во внешних узлах, среднее количество проверок битов, выполненных при случайном успешном поиске, будет равно длине внешнего пути, деленной на N. Если сформировать, как и ранее, производящую функцию b{z) для внешних узлов, то эта величина может быть представлена как 6(1)/6(1). Неудачный поиск с использованием метода "Патриция" также заканчивается во внешнем узле уровня I с вероятностью 2"", так что среднее количество проверок битов составляет б(1)-Например, для случая, представленного на рис. 36, мы имеем b{z) = Zz + 82"-I-3z + 2z; таким образом, среднее число проверок битов при успешном поиске равно 4j и при неудачном - ЗЦ.

Обозначим через hn{z) "среднюю" производящую функцию 6(2), т. е. функцию, усредненную по всем деревьям метода "Патриция" с п внешними узлами и равномерно распределенными ключами. Рекуррентное соотношение

/1„(2) = 21-"()/1,(2)(2 + <5,„(1-2)), /10(2) = О, /11(2) = 1, (15)

по-видимому, не имеет простого решения; но, к счастью, существует простое рекуррентное соотношение для средней длины внешнего пути h„{l), поскольку

= "-2-"п + 21-"5;()ли1). (16)

Так как оно имеет вид (6), для поиска /г(,(1) можно использовать ранее разработанные методы. Оказывается, /г„(1) ровно на п меньше соответствующего числа проверок битов в случайном бинарном луче. Следовательно, поле SKIP позволяет сэкономить около одной проверки бита при удачном поиске случайных данных (см. упр. 31). Избыточность же типичных реальных данных приведет к еще большей экономии.

Если попытаться найти среднее количество проверок битов в случае неудачного поиска методом "Патриция; получится рекуррентное соотношение

(n = + 2 Е (fc)"* п>2; оо = oj = О (17)

к<п

(здесь а„ = Л„())- Это соотношение не похоже ни на одно из рассмотренных выше рекуррентных соотношений и не сводится к ним каким-либо более или

менее простым способом. Однако теория преобразований Меллина, приведенная в разделе 5.2.2, обеспечивает возможность работы с такого рода рекуррентными соотношениями. Оказывается, решение (17) содержит числа Бернулли:

Эта формула, вероятно, представляет собой самый твердый асимптотический орешек, который был разгрызен в данной книге. Решение, представленное в упр. 34, является поучительным обзором многих ранее встречавшихся задач (с некоторыми нюансами).

Итоги анализа. Следующие результаты сложных математических выкладок этого раздела заслуживают особого внимания.

a) Количество узлов, которые необходимы для хранения N случайных ключей в М-арном луче с разветвлениями, прекращающимися по достижении подфайлов из < 5 ключей, составляет примерно N/{slnM). Это приближение справедливо при больших N, малых s и малых М. Поскольку узлы луча содержат М полей ссылок, всего при S = М потребуется около N/\nM полей ссылок.

b) Количество цифр или символов, проверяемых в ходе случайного поиска, составляет для всех рассмотренных методов примерно \ogf N. При М = 2 различные методы анализа дают более точные приближения для количества проверок битов.

Успешный Неудачный

Поиск по лучу IgN + 1.33275 IgiV - 0.10995

Цифровой поиск по дереву Ig Л - 1.71665 Ig - 0.27395

Поиск методом "Патриция" ig iV + 0.33275 Ig iV - 0.31875

(Эти приближения могут быть выражены фундаментальными математическими постоянными; например, 0.31875 на самом деле означает (1п7г - 7)/In 2 - 1/2).

c) "Случайные данные" в нашем случае означают, что iW-ичные цифры равномерно распределены, как если бы ключи были действительными числами между О и 1, записанными в iW-ичной системе счисления. Методы цифрового поиска не зависят от псфядка, в котором ключи введены в файл (за исключением алгоритма D, который слабо чувствителен к порядку); однако они весьма чувствительны к распределению цифр. Например, если нулевые биты встречаются гораздо чаще единичных, деревья будут существенно более асимметричными по сравнению с деревьями, полученными для случайных данных (в упр. 5.2.2-53 приведен пример того, что может случиться при таком смещении данных).

УПРАЖНЕНИЯ

1. [00] Если дерево имеет листья, то что имеет луч?

2. [20] Разработайте алгоритм вставки нового ключа в М-арный луч с использованием соглашений алгоритма Т.

3. [21] Разработайте алгоритм удаления ключа из il/-apHoro луча с использованием соглашений алгоритма Т.

► 4. [21] Большинство из 360 элементов, приведенных в табл. 1, представляет собой пустые ссылки. Однако можно сжать таблицу до 49 элементов, перекрыв непустые и пустые