Como Huffman Constrói o Código Ótimo
Hamming apresenta a codificação de Huffman como um algoritmo guloso que constrói um código livre de prefixo com comprimento médio mínimo. A ideia chave: construir a árvore de baixo para cima, sempre mesclando os dois símbolos menos prováveis.
A Passagem Progressiva (Construção)
1. Classifique todos os símbolos por probabilidade, do maior para o menor.
2. Pegue os dois símbolos com menor probabilidade. Combine-os em um novo meta-símbolo com probabilidade = soma dos dois.
3. Insira o meta-símbolo em sua posição classificada.
4. Repita até que apenas dois símbolos permaneçam.
5. Atribua 0 e 1 aos dois símbolos restantes.
A Passagem Regressiva (Atribuir Códigos)
Desfaça as mesclagens em reverso: em cada divisão, os dois símbolos que foram mesclados recebem os mesmos bits de prefixo que seu pai combinado, mais um 0 adicional (um filho) ou 1 (outro filho). A atribuição 0/1 é arbitrária — ambas são válidas.
Por que isso é ótimo: se qualquer outro código tivesse um comprimento médio menor L', aplicando a mesma redução progressiva eventualmente produziria dois símbolos com comprimento médio menor que 1 bit — impossível para um código de 2 símbolos. Contradição.
Rastreando o Algoritmo
Exemplo de Hamming: quatro símbolos A, B, C, D com p(A)=0.5, p(B)=0.25, p(C)=0.125, p(D)=0.125.
Passagem progressiva:
Passo 1: Classificado: A(0.5), B(0.25), C(0.125), D(0.125). Os dois menores: C, D.
Passo 2: Mescle CD com p=0.25. Nova lista: A(0.5), B(0.25), CD(0.25).
Passo 3: Os dois menores: B(0.25), CD(0.25). Mescle BCD com p=0.5.
Passo 4: Dois símbolos permanecem: A(0.5), BCD(0.5). Atribua A=0, BCD=1.
Passagem regressiva:
BCD → B recebe 10, CD recebe 11. CD → C recebe 110, D recebe 111.
Código final: A=0 (l=1), B=10 (l=2), C=110 (l=3), D=111 (l=3).
L = 0.5·1 + 0.25·2 + 0.125·3 + 0.125·3 = 1.75 bits.
Múltiplos Códigos Huffman Válidos
Hamming nota duas fontes de não unicidade:
1. Atribuição arbitrária de 0/1. Em cada divisão, você pode dar 0 para qualquer filho. Trocar 0 e 1 em todo o código produz um código diferente com L idêntico.
2. Desempate. Quando dois nós têm probabilidade igual, qualquer um pode ser colocado 'mais alto' (combinado primeiro). Diferentes escolhas de desempate podem produzir árvores estruturalmente diferentes — 'alongadas' vs 'ramificadas' — com o mesmo L mas com distribuições de comprimento de código diferentes.
Árvore Alongada vs Ramificada
Árvore alongada (inclinada): um símbolo em cada nível de profundidade (estrutura semelhante a Fibonacci). Comprimentos de código variam amplamente: um símbolo recebe um código curto, outros cascata para códigos mais longos.
Árvore ramificada (equilibrada): símbolos espalhados uniformemente em todos os níveis de profundidade. Comprimentos de código agrupados perto da média. Variância menor.
A recomendação de Hamming: quando dado uma escolha, prefira a árvore ramificada. Mesmo L, mas menor variância nos comprimentos dos códigos → tempo de decodificação mais uniforme → menores requisitos de buffer em aplicações de tempo real.
Calculando a Variância do Comprimento do Código
Variância dos comprimentos do código: Var = E[l²] − (E[l])²
Para o código {A=0 l=1, B=10 l=2, C=110 l=3, D=111 l=3} com p=[0.5, 0.25, 0.125, 0.125]:
E[l] = L = 1.75
E[l²] = 0.5·1² + 0.25·2² + 0.125·3² + 0.125·3² = 0.5 + 1.0 + 1.125 + 1.125 = 3.75
Var = 3.75 − 1.75² = 3.75 − 3.0625 = 0.6875
Um código ramificado alternativo para símbolos equiprováveis usa todos os códigos de comprimento 2: L=2, Var=0.
Ganhos de Compressão vs Distribuição de Símbolos
Regra de Hamming: a codificação Huffman compensa apenas quando as probabilidades dos símbolos diferem substancialmente.
Probabilidades iguais. Se todos os 2^k símbolos têm probabilidade igual 1/2^k, Huffman produz um código em bloco: cada símbolo recebe comprimento k. L = H = k. Nenhum ganho sobre o código em bloco simples.
Probabilidades inclinadas. Se um símbolo domina (p >> 1/2^k para outros), Huffman atribui a ele um código muito curto (comprimento 1 ou 2), reduzindo drasticamente L.
O código de vírgula (termo de Hamming). Quando cada probabilidade excede 2/3 do total restante, Huffman naturalmente produz: p(s1)→0, p(s2)→10, p(s3)→110, ..., descendendo a dois códigos de comprimento igual no final. Este é um 'código de vírgula': o 0 final após uma sequência de 1s atua como uma vírgula.
Hamming observa: compressão de dados do mundo real (backup, arquivamento de arquivos) pode reduzir o armazenamento em mais de metade quando a fonte tem probabilidades inclinadas — texto em inglês sendo um exemplo primário.
Huffman vs Código em Bloco: Comparação Numérica
Segundo exemplo de Hamming: p(s1)=1/3, p(s2)=1/5, p(s3)=1/6, p(s4)=1/10, p(s5)=1/12, p(s6)=1/20, p(s7)=1/30, p(s8)=1/30.
Código em bloco: 8 símbolos → 3 bits cada → L_block = 3.
Hamming calcula o código Huffman e relata L_Huffman ≈ 2.58 bits.
Economia: (3 − 2.58)/3 ≈ 14% de compressão sobre códigos em bloco.
Quando as probabilidades dos símbolos diferem muito (1/3 vs 1/30 aqui, uma razão de 10:1), a codificação de comprimento variável compensa substancialmente.
Programas Auto-Compiláveis
Hamming termina o Capítulo 11 com uma ideia marcante: um codificador Huffman pode codificar a si mesmo. A árvore de decodificação (que diz ao decodificador como ler a mensagem comprimida) é transmitida junto com os dados comprimidos. O receptor não precisa de conhecimento prévio do código.
O codificador: amostra os dados, estima probabilidades, constrói o código Huffman, codifica a árvore de decodificação como um cabeçalho, depois codifica os dados.
O decodificador: lê o cabeçalho para reconstruir a árvore, depois decodifica os dados usando-a.
O ponto de Hamming: todo este pipeline pode executar como uma função de biblioteca sem envolvimento humano. Você o chama, ele compacta e descompacta automaticamente. Formatos modernos de arquivamento (ZIP, gzip, bzip2) implementam exatamente este padrão.
O princípio mais profundo: a inteligência está no algoritmo, não em uma tabela de código fixa. O algoritmo se adapta a quaisquer dados que receba. Este é o padrão que Hamming vê em todos os grandes sistemas de engenharia: adaptabilidade construída, não acoplada.