AOP_Tom3 (1021738), страница 123
Текст из файла (страница 123)
при г' ф к. Например, для и = 3 и приведенных значений в» Построим бинарное дерево с и+ 1 листом таким образам, чтобы и» соответствовало пути от корня к Я для 0 < й < и, где "0" означает левую, а "1" — правую ветви. Кроме того, если н»» имеет вид а»0»г»,, а»г» — а»17» для некоторых а», В» и у»з то внутренний узел ® соответствует пути а». Таким образом, дерева соответствует приведенному ранее примеру.
Как видите, у дерева могут остаться безымянные внутренние узлы; заменим каждый из них его единственным дочерним узлом. Цена полученного дерева не будет превышать 2,'»» Рь(~а»)+1)+2„» о д»)о»(. Поскольку з» < (.оь)в+2 г'-"~ и в»» > (.а»)г, получим Р» — 22»» + Рв + г»7» (26) Болеетаго,вслучаещ >2»имеемз»>з»»+2 ' 'ив»„»>в»+2 ' ',таким образом, )а»~ < 1+ 1. Отсюда следует, что д». < 2 '""г и мы построили бинарное дерево ценой зо = (.0000001)г з» = (.0000101)г зг = (Л)001011)г зз — — (.1100000) г ао = 00000 а» = 00001 аг = 0001 аз =1 и ь П И 1 < ~~~ рь(1+ ~аь)) + ~~ дь)аь1 < ~~~ рь(1+18 — ) + ~до(2+ 18 — ) о= 1 з=о ь=з рь ь=о дь = Р+ 2(1 — Р) + Н = Н+ 2 — Р.
! В случае указателя КЪ'1С (см. рис. 15) Р = 1304/3288 зе 0.39659 и Н(ры. ~ роз~ до,,дзз) 5.00635. Вследствие этого теорема В утверждает, что С > 3.3800 и согласно теореме М С ( 6.6098. "Алгоритм Гарсия-Вача. Возможно поразительное улучшение алгоритма К в специальном случае: рз = = р„= О. Этот случай, когда роль играют только вероятности листьев (до, ды..., Ч„), особенно важен, так как он нередка встречаетсн во многих приложениях.
Далее в этом разделе мы предполагаем, что вероятности р, — нулевые. В данном случае теоремы В и М сводятся к неравенствам Н(до,дз ° дв) ( С(до дс ° ° ° дп) < Н(до Чз - дв) + 2 (27) и функция цены (14) упрощается до С = гу Чз1зп 1ь = уровень Я). (28) о=о Ключевое свойство, позволяющее упростить алгоритм, заключается в следующем наблюдении. Лемма ЧЧ. Если дь ~ > дв+ы то в каждом оптимальном дереве 1ь < 1ь+ы Еслп же Чь з —— дь+ы та в некоторых онтпмвльных деревьях 1ь < 1ь+и Доказвтельсшоо.
Предположим, что дь з > Чь», и рассмотрим дерево, в котором 1ь > 1з+ы Тогда (к) должен быть правым дочерним узлом, а его левый "брат" ! — поддеревом веса с > Чь .ы Заменим родительский по отношению к [з:) узел поддеревом !., а узел ~~~+1~ — узлом, дочерними узлами которого являются [Я н [й+1~. Такая замена изменит общую стоимость на — г — дь(!ь — 1ььз — 1) + дз+з < дь» — дь м Значит, данное дерево не было оптимальным, если выполнялось условие дь-з > Чь»,' в случае Чз ~ — — Чз» оптимальное дерево было трансформировано в другое оптимальное дерево.
В последнем случае последовательность таких трансформаций приведет к 1ь ( 1дчь $ Более глубокий анализ структуры даст нам значительно больше. Лемма Х. Предположим, что з я к — индексы, такие, что 7 < й и 1) д; з > дз» прн 1 < 1 < Й; й) Чз» < Чь+П 01) ЧЧ <до з+Чь пргз(<1<й — 1; гч) Чу — з > дь-з + Чы Тогда существует оптнмвльнае дерено, в котором 1ь з = 1ь н либо а) 1 = 1ь — 1, либо Ь) 11 —— 1ь и ~у' ) является левым дочерним узлом. Доказательснгво. При замене "левого" "правым" в лемме ггг мы увидим, что (й) означает существование оптимального дерева, в котором 1ь г > 1ы Однако лемма гг' и (г) означают, что1, < 1г « 1ь.
Следовательно,1ь г =1ы Предположим, что 1, < 1ь — 1 < 1гзг для некоторого у' < в < й. Пусть 1 представляет собой наименьший индекс, меньший й, такой, что 1, = 1ы Тогда 1г.гг = = 1г г —— 1д — 1 и (в+1) представляет собой левый дочерний узел. Отсюда вытекает, что 1 — з почетно и узел Я является левым дочерним узлом при г' = з+1, в+3,..., й Заменим родительский узел узла (г) узлом г+1, а узел (г) — узлом (г+1) для в < г' < г.
Кроме того, заменим внешний узел Я внутренним узлом, дочерними узлами которого являются (з) и (з+1). Все эти замены приведут к изменению цены на < о, — ог — ог.гг < о, — дь г — ды т. е. к улучшению дерева при о, < йь г + ох. Следовательно, согласно (гй) 1 ) 1ь — 1. До этого момента мы ни разу не использовали гипотезу (гг). Если 1, = 1ь и У не является левым дочерним узлом, то 1з] должен быть правым "брауом" узла У вЂ” 1 . Заменим их родительский узел узлом (з' — 1), а затем заменим каждый лист листом Гг' — 1) для у < г < Й.
Заменим также внешний узел (гг~ внутренним узлом, являющимся родительским по отношению к (гг-.1~ и (гг~. Эти действия изменят цену на — о, г +ог. г + йь < О, так что мы получим оптимальное дерево, удовлетворяющее условию (Ь). $ Лемма У. Пусть у и к тс жс, что н в лемме Х Рассмотрплг измененные вероятности (г1о,...,д,', г) = (до,...,ч, г дь г+дыг1,,...,дь г,о„,„...,г1„), получсгшые посредством удаления оь. г н оь н вставил г1„г + оь после о .
г. Тогда г'(0о . Я -г) < (Чь-г + Э ) + с'(0о . Ч ). (29) Доказательство. Достаточно показать, что любое оптимальное дерево для (г1о,..., о„) может быть трансформировано в дерево той же цены, в котором (1г —.г~ и (х] являкгтся "братьями", т. е. имеют один и тот же родительский узел, и листья которого появляются в следующем порядке; Ю 033 И И 2 Е~~ Е+Л' " П (30) Мы начнем с дерева, сконструированного в лемме Х.
Если это дерево типа (Ь), просто переименуем листья, сместив (гг-г.) н (г:) влево на й — 1 — з лгест. Если же это дерево типа (а), предположим, что 1, г =1ь — 1 и 1, = 4. В этом случае мы действуем слсдугощим образом: сначала сместим (й--Я и Я влево на к — 1 — в лгест, затем заменим их новый родительский узел узлом, дочерними узлами которого являются [й-Я и (Я, а также заменим узел Я узлом (г' — 1] для всех 1 < г < в. ) Лемма 2.
При выполненно угловпй леммы г' неравенство (29) становится равен- ством. Доказательство. Каждое дерево для (0~о,..., д'„г) соответствует дереву с листьями (30), в котором выпвдающне из общего порядка листья (1г-Я и (к) представляют дочерние узлы одного и того же родительского узла.
Пусть этот родительский узел — Ох. Мы хотим показать, что любое оптимальное дерево этого типа может быть конвертировано в дерево той же цены, но в котором листья располагаются в нормальном порядке — [О) ... (гг). э- О сг а сч Ь с в л х а м Д а Ф и с Ю й 3 ОГ И ) Ю' Ф Ы Х С о Ы о д Ф х а а ы б Р. Ф Ы а ь 5 о Х й Й Если 2 = А — 1, доказывать нечего.
В противном случае мы имеем д,', > д,'+, длау < 1 < Й вЂ” 1, посколькУ4, ~ > дь с+4ь ) дм Следовательно, согласно лемме% < 11 « . )ь-т, где 1 — уровень Сх) и 1, — уровень Е для 1 < 1 < й — 1. Если же 1, = 1ь т, мы просто смещаем узел От нправо, замещая последовательность (т) Дз .. )А — 2 2) последовательностью Я ... )А — 2 2)Я; это расположит листья в требуемом порядке.
В противном случае предположим, что 1, = 1, и 1,э1 > 1,. Сначала заменим Я Ду .. Е на Е ... Дз Я, получим 1 < 1,~1 < .. < 1А з, где 1 = 1, + 1— общий уровень узлов 1к-1~) и А . И, наконец, заменим узлы )А-1) Д/с )э+1] ....)й 222) узлами Я+)~ ... )А-2) ~Я-1) ДА при помощи циклической перестановки. В упр. 40 доказывается, что эти действия приведут к уменьшению цены 1за исключением случая 1ь 2 = 1). Однако поскольку согласно лемме У цена не может уменьшаться, щседовательно, 1ь 2 = 1 и лемма доказана. 1 Эти леммы показывают, что задача для и + 1 несов дв, щ, ..., 4, может быть сведена к задаче для и весов; сначала находим наименьший индекс й, такой, что дь ~ < дь, ы а затем — наибольшее 2 < А, для которого 41 1 > дь 1 + 4ь.
После этого мы удаляем дь 1 и дь и вставляем сумму дь 1+ дь непос;редственно после 4 В специальном случае 2 = 0 или й = и, как вытекает из доказательства, мы должны действовать так, квк если бы у нас были бесконечные веса д, и двч.с слева н справа. Доказательства также показывают, что любое оптимальное дерево Т', полученное на основе новых весов (йе,...,д,',,), может быть персу.порядочено в дерево Т, в котором исходные веса (дш...,д„) находятся в корректном порядке слева направо; более того, каждый вес появляется нв одном и том же уровне как в дереве Т, так и в дереве Т'.
В качестве примера на рис, 18 показано построение дерева для весов дь, представляющих относительные частоты появления букв о, А, В, ..., 2 н английском тексте. Первые веса в этом списке равны 186, 64, 13, 22, 32, 103, и вьсполняются неравенства 186 > 13, 64 ) 22, 13 < 32; следовательно, мы должны заменить 13,22 значением 35.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
