Por Que a Estratégia Gulosa é Ótima
O algoritmo de Huffman é um algoritmo guloso: em cada passo, ele faz a escolha localmente ótima (mesclar os dois nós mais baratos) sem olhar para frente. Algoritmos gulosos nem sempre são globalmente ótimos, mas aqui eles são.
O Argumento de Otimalidade
Suponha que um código C tenha comprimento médio mínimo L. Considere os dois símbolos com menor probabilidade, digamos p_a e p_b. Em qualquer código ótimo, esses dois símbolos devem aparecer como folhas irmãs no nível mais profundo da árvore. Por quê?
Se não compartilhassem um pai, você poderia trocar o símbolo mais profundo por um código mais curto, reduzindo L. Portanto, as folhas mais profundas devem ser os símbolos menos prováveis.
Agora, se você combinar a e b em um meta-símbolo ab (com p_ab = p_a + p_b), qualquer código ótimo para o alfabeto reduzido menos um símbolo é precisamente o código de Huffman no problema reduzido. Indução completa o argumento.
Visualização Geométrica
O algoritmo de Huffman constrói a árvore binária de baixo para cima, colocando os símbolos menos prováveis na profundidade máxima. Isto minimiza Σ p_i · depth(i) = L.
Uma visão equivalente: você está atribuindo rótulos às folhas da árvore para minimizar o comprimento do caminho ponderado, em que o peso de cada folha é sua probabilidade.
Executando os Passos Gulosos
Probabilidades: p(A)=0.4, p(B)=0.3, p(C)=0.2, p(D)=0.1. Soma = 1.0 ✓
Passo 1: Dois menores: C(0.2), D(0.1). Mesclar → CD(0.3). Lista: A(0.4), B(0.3), CD(0.3).
Passo 2: Dois menores: B(0.3), CD(0.3) (empate; ambas válidas). Mesclar → BCD(0.6). Lista: A(0.4), BCD(0.6).
Passo 3: Mesclar A(0.4), BCD(0.6) → raiz(1.0). Atribuir A=0, BCD=1.
Para trás: BCD → B=10 (l=2), CD=11 → C=110 (l=3), D=111 (l=3).
L = 0.4·1 + 0.3·2 + 0.2·3 + 0.1·3 = 0.4+0.6+0.6+0.3 = 1.9 bits.
Variância de Comprimento de Código
Dois códigos de Huffman podem atingir o mesmo L mas ter distribuições diferentes de comprimento de código. A variância dos comprimentos de código mede essa dispersão:
Var(l) = E[l²] − (E[l])²
onde E[l] = L (comprimento médio de código) e E[l²] = Σ p_i · l_i².
Por que a variância importa:
1. Requisitos de buffer. Na decodificação em tempo real, cada símbolo leva um número variável de bits. Alta variância significa que alguns símbolos levam muitos bits, você precisa de um buffer de entrada maior para garantir que sempre possa ler um símbolo completo.
2. Latência de decodificação. Códigos com alta variância têm caminhos de decodificação longos no pior caso. Códigos de baixa variância (densos) limitam o pior caso mais rigidamente.
3. Robustez. Um bit perdido em um código de alta variância causa mais dano de sincronização porque palavras de código longas devem ser totalmente relidas.
Recomendação de Hamming: quando existem múltiplos códigos de Huffman válidos (escolhas de desempate), prefira aquele com variância menor, a árvore densa.
Computando a Variância para Duas Árvores
Usando p(A)=0.4, p(B)=0.3, p(C)=0.2, p(D)=0.1 e o código A=0, B=10, C=110, D=111:
E[l] = L = 1.9
E[l²] = 0.4·1² + 0.3·2² + 0.2·3² + 0.1·3² = 0.4+1.2+1.8+0.9 = 4.3
Var = 4.3 − 1.9² = 4.3 − 3.61 = 0.69
Código de Huffman de 3 Símbolos de Ponta a Ponta
Um exemplo completo de ponta a ponta: construir código de Huffman, calcular L, calcular H, verificar L ≥ H, calcular Var.
Fonte: p(X)=0.6, p(Y)=0.3, p(Z)=0.1.
Construção de Huffman:
Passo 1: Ordenado: X(0.6), Y(0.3), Z(0.1). Dois menores: Y(0.3), Z(0.1).
Mesclar → YZ(0.4). Lista: X(0.6), YZ(0.4).
Passo 2: Mesclar X(0.6), YZ(0.4) → raiz(1.0). Atribuir X=0, YZ=1.
YZ → Y=10, Z=11.
Código: X=0 (l=1), Y=10 (l=2), Z=11 (l=2).
L = 0.6·1 + 0.3·2 + 0.1·2 = 0.6 + 0.6 + 0.2 = 1.4 bits.
Entropia: H = −0.6·log₂(0.6) − 0.3·log₂(0.3) − 0.1·log₂(0.1)
log₂(0.6) ≈ −0.737, log₂(0.3) ≈ −1.737, log₂(0.1) ≈ −3.322
H = 0.6·0.737 + 0.3·1.737 + 0.1·3.322 = 0.442 + 0.521 + 0.332 = 1.295 bits.
L = 1.4 ≥ H = 1.295 ✓. L/H = 1.4/1.295 ≈ 1.081. 8.1% acima da entropia.
Variância: E[l²] = 0.6·1 + 0.3·4 + 0.1·4 = 0.6+1.2+0.4 = 2.2. Var = 2.2 − 1.4² = 2.2 − 1.96 = 0.24.
Sua Vez: Um Pipeline Completo
Valores de log₂ para referência: log₂(0.5)=−1.000, log₂(0.25)=−2.000, log₂(0.125)=−3.000, log₂(0.375)≈−1.415, log₂(0.625)≈−0.678.