| [ Principal | ] |
MAC 323 - 2003 |
Esse texto é uma tradução, com algumas modificações, do texto extraido da
seguinte página da Universidade de Aberdeen:
http://www.maths.abdn.ac.uk/~igc/tch/mx4002/notes/node59.html#L:weights-and-lengths
Preparado por: Sérgio Haruo Nakanishi
Notações e definições:
.wi (w índice i) = é o peso do nó i, se o nó for uma folha o peso é a frequência da informação (letra)
dessa folha (weight of i);
.li (l índice i) = profundidade da folha i, ou o tamanho do caminho da folha i até a raiz (lenght of i);
.L(T) (função L de T, onde T é uma árvore binária) = é a somatória de wi*li, para cada folha da árvore
(é a função apresentada em aula como função custo - wighted leaf path Lenght);
.Dizemos que uma árvore binária é ÓTIMA se sua L(T) é mínimo.
Teorema 3.7
A árvore de Huffman é ótima. Ou seja, se H é uma árvore de Huffman e T
qualquer outra árvore, temos que L(H) <= L(T).
Prova
Provaremos usando os lemas 3.8 e 3.9 anúnciados a seguir:
Lema 3.8 (em uma árvore ótima, se wi < wj implica em lj <= li)
Suponha que existam duas folhas com pesos (ou frequências) wi e wj que
satisfaçam wi < wj. Então, se uma árvore é ótima, suas respectivas
profundidades, li e lj, satisfazem lj <= li.
Essa afirmação significa que folhas com peso pequeno tem códigos longos
(profundidade maior).
Prova
Suponha (por contradição) que temos uma árvore T associada a um conjunto de
folhas de pesos { wk }, e que para algum par i, j, nós temos wi < wj mas li
< lj (a contadição é que o peso de j é maior e tem profundidade maior).
Então temos:
(wj - wi) * (lj - li) > 0, portanto, (lj * wj) + (li * wi) > (li * wj) +
(lj * wi)
Vamos ver o efeito de trocar a folha i pela folha j:
L(T) - [(lj * wj) + (li * wi)] + [(li * wj) - (lj * wi)] < L(T)
Portanto T não era ótimo, pois conseguimos diminuir L(T).
Lema 3.9
Suponha que as folhas de uma árvore ótima tenham pesos { wi } indexadas (ou
rotuladas) de modo que w1 <= w2 <= ... <= wn. Consequentemente temos que
l1 >= l2 >= ... >= ln.
Prova
Suponha por contadição que i < j mas li < lj. Como i < j, temos wi <= wj.
Entretanto, se wi < wj pelo lema 3.8 teríamos lj <= li (admitindo que a
árvore é ótima). Mas lj > li, mostrando que devemos ter wi = wj.
Assim não há perdas em L(T) se trocarmos a folha i pela folha j (assim teremos
li > lj). Podemos continuar fazendo isso até que consigamos ordenar os rótulos
das profundidades da forma esperada.
Se não entendeu a prova, de valores para i e j. Por exemplo:
1 < 2 mas l1 < l2. Como 1 < 2, temos que w1 <= w2. Entretanto, não não há
possibilidade de w1 < w2 pelo lema 3.8 (em uma árvore ótima, se w1 < w2
então l2 <= l1). Como l2 > l1 então w1 = w2 e podemos trocar a folha 1 pela
folha 2, assim l1 > l2. Podemos continuar a fazer isso até chegarmos que w1
<= w2 <= ... e l1 >= l2 >= ...
Agora podemos provar que a árvore de Huffman é ótima. Faremos isso usando
indução sobre o número n de folhas da árvore. Note que em uma árvore ótima
não há nó com um filho, pois assim podemos substituir o filho pelo seu pai
diminuindo a profundidade e consequentemente diminuindo L(T).
Considere que temos um conjunto de (n+1) folhas com frequências {wi} e (n + 1) >= 2.
Sem perda de generalidade supomos que as frequências estão indexadas de
forma que w1 <= w2 <= ... <= w[n+1], e portando, do lema 3.9, que as profundidades
correspondentes satisfaçam l1 >= l2 >= ... >= l[n+1].
Seja T[n+1] uma árvore ótima para esses nós e com custo L(T[n+1]). Nós escolhemos que w1
seja o nó que tenha a maior profundida, assim como seu irmão wj; como são irmãos temos
l1 = lj. Como l1 >= l2 >= lj, temos l2 = l1.
Assim a nova árvore T´[n+1], obtida trocando a folha 2 pela j, tem o mesmo custo L(T[n+1]).
A seguir construimos uma nova árvore Tn com uma nova folha w = (w1 + w2)
combinando w1 e w2 de T´[n+1] para resultar em uma nova árvore com n folhas.
Seja Hn uma árvore de Huffman com essas folhas, e note que, costruindo a
árvore obtida substituindo w de Hn por w1 e w2, as duas folhas de menor
frequência, temos uma árvore de Huffman H[n+1].
Por indução, temos que L(Tn) >= L(Hn), já que tem as mesmas folhas (caso não tenha entendido,
leia a Observação 3.10 abaixo). Agora calculamos:
L(Tn) + w1 + w2 = L(T[n+1]) e L(Hn) + w1 + w2 = L(H[n+1])
Então L(T[n+1]) >= L(H[n+1]). Mas T[n+1] é ótima, portanto essa inequação é
uma igualdade, como queriamos demonstrar. []
Observação 3.10:
A prova acima tem que ser feita cuidadosamente. A árvore binária com folhas
de frequência 1, 3, 2 e 2 não é uma árvore de Huffman, mas é ótima.
8
/ \
4 4
/ \ / \
1 3 2 2
Entretando se trocarmos a segunda folha pela terceira, não afeta o L(T), e
nos resulta na árvore de Huffman. Na prova, essa mudança é feita ao
construirmos T´[n+1].
|
[ Página inicial | Panda2 | Lista MAC323 | Lista Java | Info ] |