Código de Huffman

• (a) com o código (0,10,110,1110,1111), que precisa de 1x 3 + 2x 2 + 3x 1 + 4x 1 + 4x 4 = 30 bits.
• (b) (00,010,0110,0111,1), que tem tamanho (custo) 2x 3 + 3x 2 + 4x 1 + 4x 1 + 1x 4 = 24 bits; ou ainda
• (c) com o código (00,10,110,111,01), com 2x 3 + 3x 2 + 4x 1 + 4x 1 + 1x 4 = 24 bits;

Esse texto é uma tradução, com algumas modificações, do texto extraido da seguinte página da Universidade de Waterloo:
http://www.student.math.uwaterloo.ca/~cs240/slides/class/L17.pdf

Preparado por: Sérgio Haruo Nakanishi

DEFINIÇÕES
profundidade(ni) - o tamanho do caminho do nó ni até a raiz da árvore.
peso(ni)         - se ni for uma folha, o peso de ni é a frequência com que aparece
                   a informação (letra) da folha ni, caso não seja uma folha o peso de
                   ni é a soma dos pesos dos seus filhos.
WPL(T) = somatória de (peso(ni) * profundidade(ni)), para cada FOLHA ni de uma árovre 
         binária T (weighted path length)
WPL(T) = função custo dado em aula.

Árvore binária completa (ou cheia) - árvore binária onde todos seus nós tem 
                                     2 filhos, exceto as folhas que não tem filho.


LEMA
Seja qualquer árvore binária completa (ou cheia) com seus pesos associados
às suas folhas. Suponha que n1 e n2 sejam as folhas com os menores pesos.
Então podemos construir uma árvore T´ a partir de T tal que:
1. T´ possue as mesmas folhas que T exceto por n1 e n2, e T´ tem uma nova
folha n3.
2. O peso de n3 é a soma de n1 e n2. O peso das outras folhas não mudam.
3. WPL(T´) <= WPL(T) - peso(n3).
4. WPL(T´) = WPL(T) - peso(n3), se n1 e n2 são irmãos em T.

Agora pra provar que Huffman é ótimo:

Seja T a árvore codificadora construida pelo algoritmo de Huffman a partir
de um conjunto de nós (folhas).

Se X é qualquer outra árvore codificadora com os mesmos nós, então WPL(T) <=
WPL(X).

A prova é feita por indução sobre o número de folhas de T:

Caso base: T tem apenas duas folhas. A prova é trivial.
Caso geral:
 Seja n1 e n2 os dois primeiros nós escolhidos pelo algoritmo de Huffman na
 construção de T. Aplique o lema em T e X para produzir T´ e X´.
 Como T foi construida pelo algoritmo de Huffman, n1 e n2 são
 nescessariamente irmãos em T.
 Então:
    (1) WPL(T´) = WPL(T) - peso(n1) - peso(n2).
 O Lema também garante que:
   (2) WPL(X´) <= WPL(X) - peso(n1) - peso(n2).
 Usando a indução, podemos afirmar que:
   (3) WPL(T´) <= WPL(X´)
 Pois:
   . T´ e X´ tem um nó a menos que T. (Lembrando indução: supondo
     que para n elementos é verdadeiro, provar que para n+1 elementos é verdadeiro.
     T tem n+1 elementos.)
   . T´ é equivalente à árvore construida pelo algoritmo de Huffman usando as
     folhas de T´.
   . T´ e X´ tem o mesmo número de folhas.
 Essas três inequações (1, 2 e 3) combinadas nos permite concluir que:

   WPL(T) <= WPL(X)
 
O que completa nossa prova.                                                       []

(substituir a igualdade (1) pela parte da esquerda da desigualdade (3) e
substituir a parte direita da desigualdade (2) pela parte da direita da
desigualdade 3 não afeta a desigualdade (3))