> huffman | codificação | ótima <
// Codificação Huffman - algoritmo de compactação ótimo e sem prefixo
>> recursos
Códigos ótimos
Gera o menor comprimento médio de código possível para as frequências fornecidas.
Sem prefixo
Nenhum código é prefixo de outro, permitindo decodificação sem ambiguidades.
Baseado em frequência
Caracteres mais frequentes recebem automaticamente códigos mais curtos.
>> informações técnicas
Como funciona a codificação Huffman
A codificação Huffman constrói uma árvore binária de baixo para cima. Começando pelas frequências dos caracteres, combina repetidamente os dois nós de menor frequência em um nó pai, até restar apenas a raiz. Ramos à esquerda representam '0' e à direita '1'. Caracteres mais frequentes recebem códigos mais curtos, alcançando uma compressão quase ótima para a distribuição de frequências dada.
Exemplo de codificação Huffman
Text: "AABBBCCCC"
Frequencies:
A: 2
B: 3
C: 4
Tree Building:
1. Combine A(2) + B(3) = AB(5)
2. Combine C(4) + AB(5) = Root(9)
Tree:
Root(9)
/ \
C(4) AB(5)
/ \
A(2) B(3)
Codes:
C: 0
A: 10
B: 11
Encoded: 10 10 11 11 11 0 0 0 0
= 1010111111 0000
Por que usar codificação Huffman?
- Taxa de compactação próxima do ideal
- Implementação simples
- Base da compactação ZIP/JPEG
- Sem perda de dados
- Eficiência comprovada em produção
>> perguntas frequentes
O que é codificação Huffman?
A codificação Huffman é um algoritmo de compressão ótimo e sem prefixo, proposto por David A. Huffman em 1952. Ela atribui códigos de comprimento variável aos caracteres com base na frequência; caracteres mais frequentes recebem códigos mais curtos, minimizando o comprimento médio do código.
Por que ela é chamada de "sem prefixo"?
Um código é sem prefixo quando nenhuma palavra-código é prefixo de outra. Por exemplo, se 'A' é codificado como '01', nenhum outro caractere pode ter um código que comece com '01'. Essa propriedade garante uma decodificação inequívoca — é sempre possível saber onde um código termina e o próximo começa, sem separadores extras.
Quão eficiente é a codificação Huffman?
A codificação Huffman atinge a compressão ideal para uma determinada distribuição de frequências, normalmente ficando a menos de 1 bit do limite teórico de entropia. Para texto em inglês, ela costuma proporcionar 60–70% de compactação e é especialmente eficaz quando as frequências dos caracteres variam bastante.
Onde a codificação Huffman é usada?
A codificação Huffman é usada na compactação de imagens JPEG, na compactação de arquivos ZIP (em conjunto com LZ77 no DEFLATE), em áudio MP3 e em muitos outros formatos. Frequentemente é combinada com outros algoritmos — por exemplo, o JPEG aplica Huffman após a DCT e a quantização, enquanto o ZIP o utiliza depois do LZ77.