AOP_Tom3 (1021738), страница 122
Текст из файла (страница 122)
Обратите внимание на то, что заглавие наподобие "Оп спе воупс1оп оГ ап ецпабоп Гог а сетушп пеъ ргаЫеш" [ "О решении уравнения для некоторой новой задачи ') оказывается настолько неинформативным, что вовсе не попадает в указателуб Идея указателя К%1С описана в работе Н. Р.
1пйп, Атег. 13осишепсабоп 11 (1960), 288 — 295, а сам указатель полностью приведен в работе %. Ж. Ъопе(еп, ЯАСлт 10 (1963), 583-646. При подготовке указателя КЖ1С к сортировке нам, возможно, понадобилось бы воспользоваться бинарным деревом поиска, чтобы проверить, должно ли определенное слово быть внесенным в указатель. Другие слова, попадающие в алфавитном порядке между неиндексируемыми словами, показаны в виде внешних узлов на рис. 15. Так, в заглавиях статей ХАСЫ за 1954 — 1963 годы встретилось ровно 277 слов, расположенных по алфавиту между словами РВОВВЕМЯ и ЯОЬОТ10М.
На рис. 15 показано оптимальное дерево, полученное согласно алгоритму К при и = 35. Вычисленные для у = 1,2,..., 35 значения с[О, у] равны (1, 1,2, 3,3,3,3,8,8,8, 8,8,8, 11, 11,..., 11,21,21,21,21,21,21); значения г(е',35) для 1 = О, 1,...,34 равны (21,21,...,21,25,25,25,25,25,25,26,26,26,30,30,30,30,30,30,30,33,33,33,35,35). а) Ь) Рис. 16. Оптимальные бинарные деревья поиска, основанные на половине данных, которые представлены па рис. 15: (а) без учета внешних частот; (Ь) без учета внутренних частот, "Промежуточные частоты" 0 оказывают существенное влияние на структуру оптимального дерева; на рис. 16, (а) показано оптимальное дерево, которое было бы получено при всех 9, равных нулю. Точно так же важны и внутренние частоты р,; на рис.
16,(Ь) представлено оптимальное дерево прн рн равных нулю. При полном наборе частот дерево, изображенное на рнс. 15, требует в среднем только 4.15 сравнений: деревья на рис. 16 требуют 4.69 и 4.55 сравнений соответственно. Поскольку для алгоритма К необходимы время и пространство, пропорциональные п2, его использование непрактично при больших п. Конечно, при очень больших п мы можем отказаться от использования бинарных деревьев и подумать о других методах поиска, которые будут рассмотрены нами немного позже.
А пока предположим, что надо найти оптимальное (или почти оптимальное) дерево при болыпих значеяиях и, Мы видели, что идея вставки ключей в порядке уменьшения частот приводит к получению в среднем неплохих деревьев; впрочем, они могут оказаться и очень плохими (см.
упр. 20), так как веса о! при таком методе построения пе используются. Еше один подход состоит в выборе карня й таким образом, чтобы максимальный вес поддерева тах(ш(0, /с — 1), 70(к, и)) был настолько мал, насколько зто возможно. Такой подход также может оказаться плохим (при выборе в качестве корня узла с малым значением р!„.). Впрочем, теорема М, приведенная ниже.
показывает, что полученное в результате дерево будет не так уж далеко от оптимального. Более успешная процедура может быть получена путем комбинирования описанных методов, как было предложено В. Л. Волкером ( !*!'. А. '!та11гег) и К. К. Готлибом (С. С. СосйеЬ) (Стар!! Т14еогу агп1 Сотрпг7пя (Асабегп!с Ргезе, 1972), 303 — 323).
Попьпайтесь уравнять "левые" и "правые" веса, однако будьте готовы переместить корень на несколько шагов вправо или влево для поиска узла с относительно большим р!. На рис. 17 показана 'разумность" предложенного метода: если начер- 5. ! а 5.0 х о х 4.9 $ 4.8 4.7 4.6 4.5 5 4.4 х 4.3 $ 4.2 Д 4.! 4.0 3ОО 200 х ь Юо ." й а г! гз 75 !7 г9 2! 23 25 27 29 3! 33 35 Рнс. 17. Поведение цены как функции корня 74.
тить график с(0, Iс — 1) + с(й, и) как функции от !с для данных Кгэт'!С (см. рис. 15), то увидим, что результат весьма чувствителен к величине рг.. Такой метод "сверху вниз" можно использовать при болыпих и для выбора корня и дальнейшей работы с левыми и правыми поддеревьями. При получении достаточна малого поддорева возможно применение алгоритма К. Результирующий метод дает неплохие деревья (по сообщениям отличающиеся от оптимальных на 2 — 3%), требуя при этом пространство 0(м) и время работы — 0(п !обо) единиц. М.
Фредманом (М. Ггейпап) было показано, что на самом деле достаточно 0(п) единиц времени при использовании подходящих структур данных (АТОС 7 (1975), 240-244; см. также К. МеЫЬагп, )унга Вггнсгигеэ апг! А !8оННщгэ 1 (Ярг!пбег, 1984), арест!оп 4.2). Оптимальные деревья и энтропия. Минимальная цена очень близка к друтаму математическому понятию, именуемому энгпропией, которое было введено Клодом Шенноном (С!апс!е ВУгаппоп) в его знаменитой работе по теории информации (Ве!! Яуэ1егп Тес!2.,7.
27 (1948), 379-423, 623 — 656). Если Рг, Рз, ..., Р„представлиют собой вероятности, причем р, + рз + . + Р„= 1, мы определяем энтропию Н(Рэ Рз Рп) как (19) Н(Р1,..., Р„е, п„г, ..., Ро) ) Н(Р„..., Р„...ю Д, О,..., 0) = Н(Р1,",Р« -г,9), (21) где д = 1 — (Р1 + . + Р„а). г Аптор использует для описания агой функции термин соловее. дословно переводимый как еогнртмй. Следует отметить, что в отечественной математике зачастую используются более точные термины емпуклал вниз и емпрклол вверх функции (Бронштейн Н. Н,, Гемендяев К. А. Справочник по математике для инженеров иучашикся втуэов. — Мс Наука, 1981. 720 с.]. Здесь и далее под еогнргпой функцией подразумевается емпуклая вверх функция. —.
Прим. перев. и 1 Н(Р1 Рз - Рп) — х~' Ре !8 (18) 1=1 Интуитивно понятно, что если происходит !с-е событие (с вероятностью рь) из и возможных, мы получаем !8(1/Рь) бит информации (так, событие, вероятность ко7!враго равна з— '., дает нам 5 бит информации).
Значит, Н(рэ, рз,...,Р„) представляет собой ожидаемое чнщю битов информации при наступлении случайного события. Если рь = О, то определим Ре !8(1/Рг) = О, поскольку 1пп,,о е !8 — = !!щ,„,оо 1 !8т = О. Такое соглашение позволяет нам пользоваться формулой (18) даже в случае, когда некоторые вероятности равны нулю. Функция х !8(1/х) вогнута, т. е.
ее вторая производная, — 1/(х !и 2), отрицательНа*. ТаКИМ ОбРаЗОМ, ПРИ Р, = Рз —... =. Рп = 1/П ДОСтИГагтСЯ ЛэаКСИМаЛЬНаЕ значение энтропии Н(Р1, рз,...,Рп), равное 1 1 1 Н( —. —,..., — ) = !8п. В общем случае, когда мы фиксируем значения рэ, ..., Рп е и позволяем изменяться заачениЯм Рп в~.э, ..., Р„, спРавеДливы неРавеиства 9 9) Н(Р1, ,Рп-юрп-аьг, ,Рп) Н(Р1 -:Рп -1 (, ~7 ) =Н(Р„..„„, 9)+4!8й, (20) Рассмотрим любое (пе обязательно бинарное) дерева, листьям которого приписаны определенные вероятности, например (22) Рг Рз Ра Здесь Рь — — вероятности того, что поисковая процедура завершит работу в листе 1Я .
Ветвление в каждом внутреннем узле соответствует локальному распределению вероятностей (основанному на сумме вероятностей листьев каждой ветви). Например, первая, вторая и третья ветви узла ® имеют соответственно вероятности 1РЗ+Рз+Рз+Р4, Рь Рь+Рг+Рв+рь); вероятности же в узле ОВ Равгзьг (Рг Рг;Рз + Р4)!1РЗ + Рг + Рз + Р4). Мы можем утверждать, что каждый внутренний узел имеет энтропию своего локального распределения вероятностей; таким образом, 1 4рз+Рг+Рз+Р4) 1К Рз+Рг+Рз+Р4 1 1 + Рь 1К + (Рь+Рт+Рв+Рь) 1К Рь Рь+Рг+Рв+Рв Рз 1 Рз+Рг+Рз+Р4 1К + Рг Рз+Рг+Рз+Р4 1К Рз+Рг+Рз+Р4 Рз Рз+Рг+Рз+Р4 Рг Рз+Р4 Рг+Рг+Рз+Р4 + 1К Р1+Рг+Рз+Р4 Рз+Р4 Рг Рг 1К Рз Рг Рз Рз+Р4 Р4 1 Рз+Р4 1К + 1К Рз+Р4 Рз Рз+Р4 Р4 Рь 1 Рь+Рг+Рв+Рв 1К + Рт 1 Рь+Рг+Рв+Рв 1К Рь+Рг+Рв+Рв Рь Рь+Рг+Рв+Рв Рг + Рв Рь+Рг+Рь+Рв 1К + Рв 1 Рь+Рг+Рв+Рь 1К Н(А) = Н1В) = Н(С) = Н(Н) = Н(Е) = Рь+Рг+Рь+рв Рь+Рг+Рв+Рв Рв Доказьгпельсгпео.
Это утверждение легко доказывается по индукции снизу вверх. Например, в соответствии с приведенными выше формуламн имеем: Лемма Е. Сумма р(о) Н(а) по всем внутренним узлам дерева о, где Р(о) — вероятность достижения узла а, а Н1о) — знтропня о, равна энтропии распределения вероятностей листьев. Н(А)+(Рз+ Р +Рз+Рв)Н(В)+РзН(С) + (Рз+Рв)Н(П) + (Рв+Рг+Рв+Рв)Н(Е) 1 1 1 Рз1К вЂ” +Р21К +'''+Р91К— Р! Рз Рв (все множители, включающие 1К(р! +Рз+ рз+рв), 1К(рз+Рв) и 1К(рв+Рг+Рв+Рв): сокращаются). $ На основании леммы Е мы можем использовать знтропию для определения нижней границы цены любого бинарного дерева. Теорема В.
Пусть (рз,..., р„; йо,, .., й„) — неотрицательные веса пз алгоритма К, нормвлшзовзнные такцм образом, чтор, +. +р„+Ко+. +о„=1, аР=Р, + .. + р„— вероятность успешного поиска, Пусть также Н=Н(рз,,р оо .. е ) С > Н-Р1К вЂ”. еН 2Р (23) Доказательство. Возьмем бинарное дерево стоимости С н назначим вероятности !1в его листьям. Добавим к каждому внутреннему. узлу среднюю ветвь, на которой будет размещен лист, имеющий вероятность рв. Тогда С = ~ р(а), где суммирование производится по всем внутренним узлам а полученного тернарного дерева и согласно лемме Е Н = 2 р(а)Н(а).
Энтропия Н(а) соответствует распределению вероятности для трех событий, где одна из вероятностей (в случае, когда а — внутренний узел Оу) равна рз/Р(а). В упр. 35 доказывается, что Н(Р, !1, г) ( Р 1К х + 1 + 1К (1 + — ) (24) для всех х > О, когда р+ й+ г = 1. Следовательно, для всех положительных х выполняется неравенство Н = ~ ~Р(а)Н(а) < ~ ~р 1Кх + (1+ 1К(1+ — ))С. н !' =! Выполнив подстановку 2х = Н/Р, получаем требуемый результат, поскольку 1+ 1К(1+ Р/Н) 1+ !К(1+ Р/Н) 2Р еН 2Р' > Н-Р!К вЂ”, так как 1К(1+ р) < р 1Ке для всех у > О. $ представляет собой энтропию соответствующего распределения вероятностей, а С— минимальную цену (14).
Тогда прн Н > 2Р/е имеем Неравенство (23) может не выполняться для крайне малых значений энтропии; ограничение случаем Н > 2Р(е не слишком строго, поскольку обычно значение энтропии составляет порядка 1кп (см. упр, 37). Обратите также внимание на то, что в доказательстве нигде не использовался порядок узлов "слева направо"; таким обраюм, нижняя граница (23) справедлива для всех бинарных деревьев поиска с вероятностями внутренних узлов Р и внешних»1» в любом порядке.
Вычигления энтропии дают нам также верхнюю границу, которая не сильно отличается от (23), даже если мы будем придерживаться порядка "слева направо". Теорема М. В предположениях теоремы В справедливо также неравенство С < Н+2 — Р. (25) Доказательствоо. ПостРоим п+ 1 сумму во = йчо, з» = »7о+ Р»+ г»1»; вг = »7о+ 1 Р» + й + Рг + зЯг. зч = Чо + Р» + ' ' + Я -» -»- Р + г»7; согласно УпР. 38 мы можем считать, что во < в» « . в„. Записывая каждую з» как двоичную дробь, получим з„= (.111... )г для з„= 1. Пусть строка аз представляет собой начальные биты в», необходимые для того, чтобы отличать в» от в.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
