Visualizador de Codificação de Huffman

Introduz um texto para veres como a codificação de Huffman atribui códigos mais curtos aos carateres mais frequentes.

Exemplo resolvido — Visualizador de Codificação de Huffman

Original (ASCII de 8 bits)	88
Bits codificados com Huffman	32
Poupança	63.6%
'l' (3×)	10
'␣' (1×)	000
'w' (1×)	001
'r' (1×)	010
'd' (1×)	011

Estes são os valores que a calculadora mostra ao abrir a página. Altere qualquer entrada acima para os recalcular.

A carregar a simulação interativa...

Huffman nunca consegue gastar menos de um bit 🖖

Códigos de Huffman são ótimos, mas apenas dentro de uma regra que lhes custa caro: cada símbolo tem de receber um número inteiro de bits. O limite de Shannon diz que um símbolo que aparece 90% das vezes vale cerca de 0,15 bit, e uma fonte composta por 90% de um caractere e 10% de outro carrega apenas 0,469 bit de entropia por símbolo. Huffman não tem como escrever uma fração de bit, então atribui 1 e 1 — gastando mais do que o dobro do que a informação vale. Essa lacuna é o motivo de dados muito enviesados comprimirem de forma decepcionante aqui, e de existirem os codificadores aritméticos e de intervalo: eles codificam a mensagem inteira como um único número e podem gastar bits fracionários. Huffman é ótimo entre os códigos de bits inteiros, o que é uma afirmação mais estreita que ótimo.

Unir sempre os dois mais raros 🖖

A árvore cresce de baixo para cima: primeiro lista-se cada caractere pela sua frequência e depois unem-se repetidamente os dois elementos menos frequentes numa pequena subárvore, tratando-a como um único pacote. Repete-se até restar uma só árvore; então cada código é lido descendo a partir do topo — a esquerda é 0, a direita é 1. Esse hábito "guloso" de sempre juntar os dois menores parece míope, mas comprovadamente produz os códigos mais curtos possíveis.

Um trabalho que superou o professor 🖖

David Huffman o concebeu em 1951, quando era estudante de pós-graduação no MIT, ao professor Robert Fano dar à turma a escolha entre um exame final e um trabalho sobre como encontrar o código mais eficiente. Fano e Claude Shannon já haviam tentado, construindo suas árvores de cima para baixo. Huffman quase desistiu, mas percebeu que construir de baixo para cima — fundindo primeiro os símbolos mais raros — era ótimo, superando o método de seu próprio professor.

CODIFICAÇÃO DE HUFFMAN — QUANDO AJUDA, E QUÃO PERTO DO ÓTIMO CHEGA?

Em que caso de compressão você está?

Huffman dá códigos curtos aos símbolos frequentes e longos aos raros, e está provado que é o melhor possível enquanto cada símbolo receber um número inteiro de bits. Quanto economiza depende inteiramente de quão desiguais são as frequências. Perfeitamente iguais, e não há o que explorar; muito desiguais, e o ganho é grande — até o ponto em que o limite deixa de ser as frequências e passa a ser o bit inteiro.

Frequências desiguais — exatamente para o que o método serve p_i ↑ ⇒ ℓ_i ↓

Todos os símbolos igualmente comuns — nada a explorar p_i = 1/n ⇒ ℓ = log₂n

Texto comum — a um bit do piso teórico H ≤ ℓ < H + 1

Um único símbolo — o piso que Huffman não consegue furar n = 1 ⇒ ℓ = 1

Frequências desiguais — exatamente para o que o método serve

O que você sabe: Poucos símbolos dominam o texto. São eles que recebem os códigos mais curtos, e o total cai bem abaixo de uma codificação de comprimento fixo.

Custo: p_i ↑ ⇒ ℓ_i ↓

Exemplo resolvido: «mississippi»: 11 caracteres, 4 símbolos distintos, codificados em 21 bits contra 88 com caracteres de 8 bits — uma economia de 76,1%

Abrir este caso: mississippi

Frequências desiguais — exatamente para o que o método serve. Os dois símbolos mais frequentes recebem os códigos mais curtos, e o total cai na mesma medida. Poucos símbolos dominam o texto. São eles que recebem os códigos mais curtos, e o total cai bem abaixo de uma codificação de comprimento fixo. — Os dois símbolos mais frequentes recebem os códigos mais curtos, e o total cai na mesma medida.

Todos os símbolos igualmente comuns — nada a explorar

O que você sabe: Com distribuição plana não há símbolos frequentes a premiar. Huffman degenera em algo bem próximo de um código de comprimento fixo.

Custo: p_i = 1/n ⇒ ℓ = log₂n

Exemplo resolvido: «abcdef»: 6 símbolos distintos, cada um uma vez, codificados em 16 bits. Um código simples de 3 bits para seis símbolos gastaria 18.

Abrir este caso: uniforme

Todos os símbolos igualmente comuns — nada a explorar. Uma distribuição plana dá uma árvore quase uniforme, e todos os códigos têm praticamente o mesmo tamanho. Com distribuição plana não há símbolos frequentes a premiar. Huffman degenera em algo bem próximo de um código de comprimento fixo. — Uma distribuição plana dá uma árvore quase uniforme, e todos os códigos têm praticamente o mesmo tamanho.

Texto comum — a um bit do piso teórico

O que você sabe: Uma mistura realista de símbolos repetidos e únicos. É o caso do dia a dia, e o resultado pousa logo acima do limite de entropia.

Custo: H ≤ ℓ < H + 1

Exemplo resolvido: «hello world»: 11 caracteres em 8 símbolos distintos, codificados em 32 bits contra 88 — 63,6% poupados, com o piso de entropia em 31,3 bits

Abrir este caso: hello world

Uma distribuição mista dá uma árvore desequilibrada, e o total pousa logo acima do limite de entropia.

Um único símbolo — o piso que Huffman não consegue furar

O que você sabe: Um texto sem variedade nenhuma. A entropia dele é zero, mas Huffman ainda precisa emitir pelo menos um bit por símbolo, porque não existe código mais curto que um bit.

Custo: n = 1 ⇒ ℓ = 1

Exemplo resolvido: «aaaaaaaaaa»: 10 caracteres, um símbolo distinto, codificados em 10 bits. A entropia do texto é 0 bit.

Abrir este caso: carácter único

Um único símbolo — o piso que Huffman não consegue furar. Um símbolo, um bit cada: nenhuma distribuição a explorar e nenhum código mais curto disponível. Um texto sem variedade nenhuma. A entropia dele é zero, mas Huffman ainda precisa emitir pelo menos um bit por símbolo, porque não existe código mais curto que um bit. — Um símbolo, um bit cada: nenhuma distribuição a explorar e nenhum código mais curto disponível.

Referências (1)

Insight block 3 — the term paper itself: D. A. Huffman, "A Method for the Construction of Minimum-Redundancy Codes." Proceedings of the IRE 40(9), 1098–1101, 1952.

Problema resolvido na íntegra

A poupança ao codificar "hello world" com a codificação de Huffman 5 passos
Codifique "hello world" com a codificação de Huffman. Encontre a economia — depois encontre o limite que indica o quão melhor qualquer código poderia se sair.
1. O ASCII de largura fixa gasta os mesmos oito bits em cada caractere, independentemente da frequência com que aparece. Esse é o desperdício que o Huffman remove: símbolos frequentes recebem códigos curtos, enquanto os raros recebem códigos longos.
  
  $"hello world" : 11 chars \times 8 bits = 88 bits$
2. Conte os símbolos primeiro, porque o código é construído a partir das contagens. Apenas 'l' e 'o' se repetem; os outros seis caracteres aparecem uma vez cada.
  
  $ℓ = 3, o = 2, others = 1 each (8 distinct symbols)$
3. A entropia de Shannon é a quantidade média de informação por símbolo e constitui um limite inferior absoluto: nenhum código univocamente decodificável consegue, em média, ficar abaixo dela. Todo o cálculo assenta em três probabilidades distintas: 3/11 para «l», 2/11 para «o» e 1/11 para cada uma das outras seis letras; assim, a soma é (3/11)(1,8745) + (2/11)(2,4594) + (6/11)(3,4594).
  
  $H = - i \sum p_{i} lo g_{2} p_{i} = 2.845 bits/symbol$
4. Multiplique pelo comprimento da string para obter o limite mínimo em bits. O Huffman deve resultar neste valor ou acima dele, e geralmente não consegue atingi-lo, porque os comprimentos dos códigos são números inteiros de bits, enquanto a entropia não é.
  
  $11 \times 2.845 = 31.3 bits (entropy floor) \leq 32 (Huffman)$
5. Construa a árvore para obter o comprimento real. Em cada etapa, o algoritmo de Huffman combina os dois pesos mais baixos: 1+1, 1+1, 1+1, depois 2+2, depois 2+2, depois 3+4 e, por fim, 4+7. Cada combinação acrescenta um bit a todos os símbolos que ficam abaixo dela. Por isso, o comprimento da codificação é a soma dos pesos combinados, 2+2+2+4+4+7+11 = 32, exatamente o valor apresentado pelo visualizador.
  
  $Huffman = 32 bits ⟹ saving = 1 - \frac{32}{88} = 63.6%$
Resposta

88 bits reduzidos para 32 — uma economia de 63.6%. O limite de entropia para estas frequências é de 31.3 bits, e o Huffman produziu 32 — 0.7 bits acima do ótimo, gastos ao arredondar oito comprimentos de código para bits inteiros. A garantia é o emparedamento H ≤ comprimento médio < H + 1: o Huffman nunca fica mais de um bit por símbolo acima do ótimo. Essa lacuna de um único bit é exatamente o motivo pelo qual a codificação aritmética existe.

$88 \to 32 bits (63.6%) H \leq \overset{ˉ}{ℓ} < H + 1$

Percurso de aprendizagem

Compressão manual

Conduz a LZ77 códigos de comprimento variável, em que os mais curtos são atribuídos aos símbolos frequentes.

Pela equipa 42Math · Atualizado 2026-07-27

Verificado com fontes publicadas. Correções bem-vindas. Política editorial · Correções

Todas as lições de Computação →

Problemas de exemplo

hello world - 88 bits em ASCII passam a 32, uma redução de 63,6% - apenas 0,7 bits acima do limite inferior de entropia, que é 31,3.
mississippi - Quatro caracteres distintos em onze: de 88 bits para 21, com um código de um só bit para o s. É também o exemplo com a maior distância ao limite inferior de entropia: 0,95 bits.
uniforme - Seis símbolos, cada um presente uma única vez, não oferecem qualquer padrão a explorar. Ainda assim, são 16 bits, contra 18 num código de comprimento fixo, porque seis símbolos não preenchem três bits.
carácter único - Dez caracteres idênticos contêm exatamente 0 bits de informação, mas Huffman ainda usa 10: um por símbolo, pois não pode escrever menos de um.