Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 21
Текст из файла (страница 21)
Результирующий метод дает неплохие деревья (по сообщениям отличающиеся от оптимальных на 2-3%), требуя при этом пространство 0(п) и время работы — 0(п!08п) единиц. М. Фредманом (М. Ггейпап) было показано, что иа самом деле достаточно 0(п) единиц времени при использовании подходящих структур данных (8ТОС 7 (1970), 240-244; см.
также К. Ме!гйогп, !уага 8ггпсгигеэ апс! .4!8ог!г!гшэ 1 (8рпп8ег, 1984), Бесс!оп 4.2). Оптимальные деревья и энтропия. Минимальная цена очень близка к другому математическому понятию, именуемому зншропией, которое было введено Клодом Шенноном (С!апбе 8Ьвппоп) в его знаменитой работе по теории информации (Вей ЯУегеш Тесй. Х 27 (1948), 379-423, 623-656). Если Ры Рз, ..., Р пРедставлЯ- ют собой веРоЯтности, пРичем Рг + Рз + + Р„= 1, мы опРеделЯем энтРопию Н(рырз,...,Р„) как 1 Н(Р, Р,..., Р„) = ) Р (8 —. (18) е 1 Интуитивно понятно, что если происходит к-е событие (с вероятностью Ре) нз и возможных, мы получаем !8(1/Ре) бит информации (так, событие, вероятность ковврого Равна — ', дает нам 5 бит инфоРмации).
Значит, Н(рм Рз,..., Р„) пРедсшвлЯет собой ожидаемое число битов информации при наступлении случайного события. Если Ре = О, то определим рь 18(1/Ра) = О, поскольку !пзбг,оь е!8-, '= !пп„,ч, „~, !8т = О. Такое соглашение позволяет нам пользоваться формулой (18) даже в случае, когда некоторые вероятности равны нулю. Функция х!8(1/х) вогнута, т. е.
ее вторая производная, -1/(х !и 2), отрицательна*. Таким образом, при рг -- Ре — — - ° — — Р„= 1/и достигается максимальное значение энтропии Н(уырт,...,р„), равное ~11 1) (19) В общем случае, когда мы фиксируем значения ры..., Рп я и позволяем изменяться значениям рп ььы .. Р„, справедливы неравенства д д! Н(ры .~рп-е~рп-е+г гРп) ~ Н(ры.
~рк-а~ йг..1 ! / = Н(1ь,...,р„а,д) +д!85, (20) Н(1„...,р„е Р„„„...,Р„) >Н(р,,...,рп а д,О,...,О) = Н(ры ",Р -е д). (21) где д = 1 — (Рг + . + Р„ь), * Автор использует лля описания втой функции термин со»саге, дословно переводимый как еог»упгмя. Слецует отметить, что в отечеетвенной математике зачастукг испольтуытсе более точные термины е»пуклел е»иг и выпуклел евере функции (Вронпгтейн и.
и., семендяев к. А. Справочник по математике для иигкенеров и учагцнкся втузое. — М» Наука, ГЭ81. — гго с.). Здесь и далее под еог»ригой функпией подразумевается выпуклая веере функция. — ггрпм, перев. Рассмотрим любое (не обязательно бинарное) дерево, листьям которого приписаны определенные вероятности, например (22) Рт Рз Р» Здесь Рз — вероятности того, что поисковая процедура завершит работу в листе Б). Ветвление в каждом внутреннем узле соответствует локальному распределению вероятностей (основанному на сумме вероятностей листьев каждой ветви). Например, первая, вторая н третья ветви узла ® имеют соответственно вероятности (Р1 + РЗ + Рз + Р», Рь, Рв + Рт + Рз + Рв); вероятности же в узле ® равны (Рырз,рз + Р»)т(Р1 + РЗ + Рз + Р4).
мы можем утверждать, что каждый внутренний узел имеет энтропию своего локального распределения вероятностей; таким образом, 1 Н(-4) = (Рт+Р +Рз+Р») )а Р1 +Р2+ Рз+Р» 1 1 + Рь 1а — + (Рь+т +Рз+Рв) ~К Рз Рь+Рт+Рв+Рв Р1 Р1+РЗ+рз+р» Рг Р1+Рз+Рз+р» 1к + 1я Н Р1+Р2+Рз+Р4 Р1 Р1+РЗ+Рз+Р» РЗ Рз+Р» 1 Р1+РЗ+Рз+Р» + )к Р1+Р2+Рз+Р4 Рз+Р4 Н(С) = — )й —, Р2 Р2 Р2 Р2 Н(Ю) = — 1к — + — 1к —, Рз Рз+Р» Р» Рз+Р» Рз+Р» Рз Рз+Р» Р» Рь Р +Рт+Рз+Рв Рт Рь+Рт+Рь+Рв 1и + 1й Рь+рт+Рв+Рв Рв Рь+Рт+Рв+Рв Рт + Рв Рв+Рт+Рв+Рв Рв 1 Рь+Рт+Рв+Рв (к + 1й Рв+Рт+Рв+Рв Рз Рв+Рт+Рз+Рв Рв Лемма Е. зуммер(о)Н(о) по всем внутренним узламдереиао, где р(а) — вероятность достижения узла о, а Н(о) — энтропия о, равна эитрошш распределения вероятностей листьев. Доказаизельстпео. Это утверждение легко доказывается по индукции снизу вверх.
Например, в соответствии с приведенными выше формулами имеем: Н(4) + (Р1 + Р2 + РЗ + Р4) Н(В) + Р2 Н(С) + (Рз + Р4)Н (л>) + (Ре + Р1 + Рк + Р9) Н(Е) 1 1 1 = Р1 13 — + Р1 13 + ' ' ' + Рк 1К— Р1 Р2 Ру (все множители, включающие 13(р1 + рт + рз+ Р4). 16(рз + Р4) " 13(ре + Рт + Рк+ Рл): сокращаются). $ На основании леммы Е мы можем использовать энтропию для определения нижней границы цены любого бинарного дерева. Теорема В. Пусть (р1,...,Р„; до,...,о„) — неотрицательные веса пз алгоритма Е, нормализованные таким образом, что рл+" +Р„+ос+ ° ° +о„=1, а Р=рл+ + Є— вероятность успешного поиска. Пусть также Н = Н(Р!,...,р„,ов,...,о„) еН С > Н вЂ” Р1й —.
2Р (23) Докаванлельсплео. Возьмем бинарное дерево стоимости С и назначим вероятности 41 его листьям. Добавим к каждому внутреннему узлу среднюю ветвь, на которой будет размещен лист, имеющий вероятносп. Рм тогда с = 2 р(а), где сумл1ирование производится по всем внутренним узлам а полученного тернарного дерева и согласно лемме Е Н = 2 , 'Р(а) Н(а). Энтропия Н(а) соответствует распределению вероятности для трех событий, где одна нз вероятностей (в случае, когда а — внутренний узел ® ) равна Р;)Р(а).
В упр. 35 доказывается, что 1~ Н(р, д, г) < р 1я я + 1 + 1к ~1 + — ) (24) для всех я > О, когда р+ д+ г = 1, Следовательно, для всех положительных т выполняется неравенство к 1 Н =~~1 Р(а)Н(а) < ~~ Р,1йн + ~1+1й(1+ — ))С. ь >=! Выполнив подстановку 2т = Н/Р, получаем требуемый результат, поскольку 1+ 13(1+ Р)Н) (. 2Р) 1+ 1й(1+ Р)Н) 1+ 1я(1+ Р)Н) 2Р еН >Н Р)й 2Р' так квк 1к(1+ Р) < Р1ке для всех Р > О. $ представляет собой энтропию соотвегттв> ющего распределения верея 2 настей, а С— минимальную цену (14). Тогда прп Н > 2Р/е имеем Неравенство (23) может не выполняться для крайне малых значений энтропии; ограничение случаем Н > 2Р/е не слишком строго, поскольку обычно значение энтропии составляет порядка )яп (см.
упр. 37). Обратите также внимание на то, что в доказательстве нигде не использовался порядок узлов "слева направо"", таким образом, нижняя граница (23) справедлива для всех бинарных деревьев поиска с вероятностямн внутренних узлов рт и внешних о» в любом порядке. Вычисления энтропии дают нам также верхнюю границу, которая не сильно отличается от (23), даже если мы будем придерживаться порядка "слева направо". Теорема М. В предположениях теоремы В справедливо также неравенство С < В+2 — Р.
Докавошельсспво. Построим и + 1 сума|у во оо, в| до + р| + с1|. вт — оо + р| + Ф + рт + вй, зв = Чо + рс + .. + Ч -| + р„+ всй,", согласно упр. 38 мы можем считать, что во < в| « ° ° в„. Записывая каждую вв как двоичную дробь, получим з„= (.Ш, . )т для з„= 1. Пусть строка ов представляет собой начальные биты вы необходимые для того, чтобы отличать зв от зу при т' ~ й. Например, для и = 3 н приведеннь!х значений зв Построим бинарное дерево с и+ 1 листом таким образом, чтобы нв соответствовало пути от корня к (Е для О < )с < и, где "0" означает левую, а "1" — правую ветви.
Кроме того, если сс|,. | имеет вид аьОсзв, а нв — аз1 з для некоторых ав, Вв и Оы то внутренний узел ® соответствует пути аы Таким образом, дерево соответствует приведенному ранее примеру. Как видите, у дерева могут остаться безымянные внутренние узлы; заменим каждый нз них его единственным дочерним узлом, Цена полученного дерева не будет ссревышать Яв с рв()ав)+1)+~ „" ов(нь). Поскольку вв < (,ав)т + 2 |сс" ~ н з| | > (.ав)т, получим р, < 1т„с+ | +|1в — в |„<2-~нв1 (26) Более того, в случае с1в > 2 с имеем зв > зв | + 2 ' ' и зв.с.с > вв + 2 ' |; таким образом, )пь) < 1+ 1. Отсюда следует„что ов < 2 ам|+в и мы построили бинарное дерево ценой во (,0000001)2 з| — — (.0000101) зт = (.0001011)т зз = (.1100000)о = ООООО ст| = 00001 ат = 0001 |тв =1 н н н И 1 < ~ р»(1+)а»))+~ 9»~М < х~~ р»~1+18 — ) +~~~,9»~2+18 — ) »=1 »=о »=о 9» = Р+ 2(1 — Р) + Н = Н+ 2 — Р.
В случае уюгзателя К%1С (см. рис. 15) Р = 1304/3288 = 0.39659 и Н(рм, рзз, до,...,дзз) м 5.00635, Вследствие этого теорема В утверждает, что С > 3.3800 и согласно теореме М С < 6.6098. еАлгоритм Гарсии-Воча. Возможно поразительное улучшение алгоритма К в специальном случае: рз = —— р„= О. Этот случай, когда роль играют только вероятности листьев (9о, щ,...,9„), особенно важен, так как он нередко встречается во многих приложениях, Далее в этом разделе мы предполагаем, что вероятности ру — нулевые. В данном случае теоремы В и М сводятся к неравенствам Н(9о й °,% ) < С(9о, В, ° °,% ) < Н(Чо, Ф," °,Ч~) + 2 (22) и функция цены (14) упрощается до С = ~~~ д»1», 1» = уровень Я.
(28) Ключевое свойство, позволяющее упростить алгоритм, заключается в следующем наблюдении, Лемма %". Если д» ~ > д»тм то и каждом оптимальном дереве 4 < !»+~. Если же 9» з = 9»~.м то в некоторых оптимальных деревьях 1» < !»~,. Доказапзе»»ство. Предположим, что 9» г > д»+и и рассмотрим дерево,. в котором 1» > !»~, Тогда [Я должен быть правым дочерним узлом„а его левый "брат" 5 — поддеревом веса с > д» з. Заменим родительский по отношению к (»: ) узел поддеревом Ь, а узел [»+Д1 — узлом, дочерними узлами которого являются (») и Б+Д1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
