un

guest
1 / ?
back to lessons

Por que a Estratégia Ganha-Max é Ótima

O algoritmo de Huffman é um algoritmo ganha-max: em cada etapa, ele faz a escolha ótima local (fusão das duas menores nós) sem olhar para frente. Algoritmos ganha-max não são sempre ótimos globalmente — mas aqui eles são.

A Argumentação de Óptimidade

Suponha um código C com comprimento médio mínimo L. Considere os dois símbolos com probabilidade mais baixa, digamos p_a e p_b. Em qualquer código ótimo, esses dois símbolos devem aparecer como folhas irmãs na camada mais profunda da árvore. Por quê?

Se eles não compartilhassem um pai, você poderia trocar o símbolo mais profundo com um código mais curto — reduzindo L. Portanto, as folhas mais profundas devem ser os símbolos de probabilidade mais baixa.

Agora, se combinar a e b em um símbolo meta 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. A indução completa o argumento.

Visão Geométrica

O algoritmo de Huffman constrói a árvore binária de baixo para cima, colocando os símbolos de probabilidade mais baixa na maior profundidade. Isso minimiza Σ p_i · profundidade(i) = L.

Uma visão equivalente: você está atribuindo rótulos às folhas da árvore para minimizar a distância de caminho ponderada, onde cada folha tem seu peso como sua probabilidade.

Executando os Passos Ganha-Max

Probabilidades: p(A)=0.4, p(B)=0.3, p(C)=0.2, p(D)=0.1. Soma = 1.0 ✓

Step 1: Mais baixos dois: C(0.2), D(0.1). Fusão → CD(0.3). Lista: A(0.4), B(0.3), CD(0.3).

Step 2: Mais baixos dois: B(0.3), CD(0.3) (empate — válido em ambos). Fusão → BCD(0.6). Lista: A(0.4), BCD(0.6).

Step 3: Fusão 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.

H para p={0.4, 0.3, 0.2, 0.1}: compute H = −Σ p_i·log₂(p_i). Use log₂(0.4)≈−1.322, log₂(0.3)≈−1.737, log₂(0.2)≈−2.322, log₂(0.1)≈−3.322. Verify that L = 1.9 ≥ H, and compute L/H.

Variação do comprimento do código

Dois códigos de Huffman podem atingir o mesmo comprimento L, mas ter distribuições de comprimentos de código diferentes. A variação 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².

Comparação de Árvores Longas e Espessas

Por que a variação importa:

1. Requisitos de buffer. Na decodificação em tempo real, cada símbolo leva um número variável de bits. Alta variação 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 de alta variança têm caminhos de decodificação piores. Códigos de baixa variança (espessos) limitam o pior caso mais estreitamente.

3. Robustez. Uma bit perdido em um código de alta variança causa mais dano na sincronização porque os codewords longos devem ser lidos novamente completamente.

Recomendação de Hamming: quando existirem vários códigos de Huffman válidos (escolhas de empate), prefira o que tiver uma menor variança - a árvore espessa.

Computando variança 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

Agora, considere a alternativa espessa: B=00, C=01, A=10, D=11 (todos os comprimentos = 2, L=2). Observe que isso NÃO é um código Huffman (L=2 > H≈1.846), mas serve como uma comparação. Calcule a Var para este código espessura-2. Em seguida, explique: mesmo que o código espesso tenha um L maior do que o Huffman, qual propriedade o torna preferível em aplicações em tempo real?

Exemplo Finalizado de 3-Símbolos de Huffman

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.

Construir Huffman:

Etapa 1: Ordenado: X(0.6), Y(0.3), Z(0.1). Dois mais baixos: Y(0.3), Z(0.1).

Fusão → YZ(0.4). Lista: X(0.6), YZ(0.4).

Etapa 2: Fusão 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.

Variance: 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: Uma Pipeline Completa

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.

Construa um código de Huffman para p(A)=0.5, p(B)=0.375, p(C)=0.125. Mostre etapas de fusão. Calcule L, H, L/H e Var. Declare uma insígnia ao comparar L com H para essa fonte.