Рассмотрим любое (не обязательно бинарное) дерево, листьям которого приписаны определенные вероятности, например

(22)

Здесь Pk - вероятности того, что поисковая процедура завершит работу в листе [Т]. Ветвление в каждом внутреннем узле соответствует локальному распределению вероятностей (основанному на сумме вероятностей листьев каждой ветви). Например, первая, вторая и третья ветви узла (а) имеют соответственно вероятности (pi + Р2 + Рз + Р4, Рь, Рв + Рт + Рв + рд); вероятности же в узле (в) равны (р1,Р2,Рз + P4)/(pi + Р2 + Рз + Р4). Мы можем утверждать, что каждый внутренний узел имеет энтропию своего локального распределения вероятностей; таким образом,

Н{А) - (pi+p2+P3+P4)lg--Г--

Pi +Р2+РЗ+Р4

+ P5lg - + (Рб+Р7+Р8+Рв) ig , „ , , . Рь Р6+Р7+Р8+Р9

и IB) = Pi J Р1+Р2+РЗ+Р4 Р2 , Р1+Р2+РЗ+Р4

Р1+Р2+РЗ+Р4 Pi Р1+Р2+РЗ+Р4 Р2

РЗ+Р4 . P1+P2-I-P3+P4

Р1+Р2+РЗ+Р4 РЗ+Р4

n(c7) = lgHa,

»9 V)

HID) = -PlgP

РЗ+Р4 Рз

Н{Е) =

P4 jgP3+P4 РЗ+Р4 Р4

-ГР4 рз РЗ-ГР4 Р4

Рв д Р6+Р7+Р8+Р9 Рт Р6+Р7+Р8+Р9

+Р7+Р8+Р9 Рв Рв+РТ+Р8+Р9 Рт

Р8 jg Р6+Р7+Р8+Р9 Р9 Р6+Р7+Р8+Р9

Р6+Р7+Р8+Р9 Р8 Р6+Р7+Р8+Р9 Р9

Лемма Е. Сумма, р{а)Н(а) по всем внутренним узлам дерева а, гдер{а) - вероятность достижения узла а, а Н{а) - энтропия а, равна энтропии распределения вероятностей листьев.

Доказательство. Это утверждение легко доказывается по индукции снизу вверх. Например, в соответствии с приведенными выше формулами имеем:

Доказательство. Возьмем бинарное дерево стоимости С и назначим вероятности qk его листьям. Добавим к каждому внутреннему узлу среднюю ветвь, на которой будет размещен лист, имеющий вероятность р. Тогда С = Хр(а), где суммирование производится по всем внутренним узлам а полученного тернарного дерева и согласно лемме Е Я = Yp{a)H{a).

Энтропия Н{а) соответствует распределению вероятности для трех событий, где одна из вероятностей (в случае, когда q - внутренний узел (J)) равна pj/p{a). В упр. 35 доказывается, что

Я(р,д,г) <plgx + l+lg(l + ) (24)

для всех ж > О, когда р + q + г = 1. Следовательно, для всех положительных х выполняется неравенство

Я = Ер(а)Я(а) < fpjlgx + (l+lg(l + ))-

Выполнив подстановку 2х = Н/Р, получаем требуемый результат, поскольку

1 + ig(i + РЩ)-" + 1 + + р/н) 2Р

так как lg(l + у) <ylge для всех у > 0.

= Pl Ig - +Р2 \g + ---+PQ\g Pl P2 P9

(все множители, включающие lg(pi +P2+P3+P4), lg(p3 +P4) и lg(p6 +p7 +p8 + p9), сокращаются).

Ha основании леммы E мы можем использовать энтропию для определения нижней границы цены любого бинарного дерева.

Теорема В. Пусть {pi, ,Рп,Яо, ,Яп) - неотрицательные веса из алгоритма К,

нормализованные таким образом, что pi +----Н Рп + 9о Н-----К 9п = 1, а Р = pi Н-----1-

Рп - вероятность успешного поиска. Пусть также

Н = H{pi,...,pn,qo,...,qn)

представляет собой энтропию соответствующего распределения вероятностей, а С - минимальную цену (14). Тогда при Н > 2Р/е имеем

с>я-Р1е. (23)

Неравенство (23) может не выполняться для крайне малых значений энтропии; ограничение случаем Н > 2Р/е не слишком строго, поскольку обычно значение энтропии составляет порядка Ign (см. упр. 37). Обратите также внимание на то, что в доказательстве нигде не использовался порядок узлов "слева направо"; таким образом, нижняя граница (23) справедлива для всех бинарных деревьев поиска с вероятностями внутренних узлов pj и внешних qk в любом порядке.

Вычисления энтропии дают нам также верхнюю границу, которая не сильно отличается от (23), даже если мы будем придерживаться порядка "слева направо"

Теорема М. В предположениях теоремы В справедливо тахсже неравенство

С < Я + 2 - Р. (25)

Доказательство. Построим п + 1 сумму So - qo, Si = qo + Pi + qi, «2 = Qo +

Pi + 41 + P2 + 42, Sn - 9o + Pi H-----1- 4n-i + Pn + \qn, согласно упр. 38 мы

можем считать, что so < si < • • • < «п- Записывая каждую как двоичную дробь, получим Sn = (.111 • • • )2 для Sn = 1- Пусть строка Ok представляет собой начальные биты Sk, необходимые для того, чтобы отличать от Sj при j ф к. Например, для п = 3 и приведенных значений s

So = (.0000001)2 ao = 00000

si = (.0000101)2 0-1 = 00001

52 = (.0001011)2 0-2 = 0001

53 = (.1100000)2 аз = 1

Построим бинарное дерево с п +1 листом таким образом, чтобы а соответствовало пути от корня к \Tj для О < к < п, где "О" означает левую, а "1" - правую ветви. Кроме того, если ak-i имеет вид аОРк, а ак - akljk для некоторых а, Рк и jk, то внутренний узе.л (к) соответствует пути ак. Таким образом, дерево

соответствует приведенному ранее примеру. Как видите, у дерева могут остаться безымянные внутренние узлы; заменим каждый из них его единственным дочерним узлом. Цена полученного дерева не будет превышать Yll=.i Pk{\ak\ + l) + J2ko 4kWk\-Поскольку Sk < {.ак)2 +2~°" и Sk-i > (.0:)2, получим

Рк < Чк-1 +Рк + 1% = Sk- Sk-i < 2-i"*l. (26)

Более того, в случае qk > 2~* имеем Sk > Sk-i + 2"" и Sk+i > Sk + 2""; таким образом, \ак\ < t + l. Отсюда следует, что qk < 2~" и мы построили бинарное дерево ценой