Codificação de Huffman

Fevereiro 2017

A codificação de Huffman

David Huffman propôs em 1952 um método estatístico que permite atribuir uma palavra de código binário aos diferentes símbolos a comprimir (pixéis ou caracteres por exemplo). O comprimento de cada palavra de código não é idêntico para todos os símbolos: os símbolos mais frequentes (que aparecem geralmente) são codificados com pequenas palavras de código, enquanto os símbolos mais raros recebem códigos binários mais longos. Fala-se de codificação de comprimento variável (em inglês VLC, para variable length code ) prefixada para designar este tipo de codificação porque nenhum código é o prefixo de outro. Assim, a sequência final de palavras codificadas com comprimentos variáveis será em média mais pequena do que com uma codificação de dimensão constante.

O codificador de Huffman cria uma árvore ordenada a partir dos símbolos e a sua frequência de aparecimento. Os ramos são construídos recursivamente partindo dos símbolos menos frequentes.

A construção da árvore faz-se ordenando inicialmente os símbolos por frequência de aparecimento. Sucessivamente, os dois símbolos de mais fraca frequência de aparecimento são retirados da lista e unidos a um nó cujo peso vale a soma das frequências dos dois símbolos. O símbolo de mais fraco peso é afectado ao ramo 1, o outro ao ramo 0 e assim sucessivamente, considerando cada nó formado como um novo símbolo, até obter um só nó parente, chamado raiz.
O código de cada símbolo corresponde na sequência dos códigos ao longo do caminho que vai deste carácter à raiz. Assim, quanto mais o símbolo é “profundo” na árvore, mais a palavra de código será longa.

Vejamos a frase seguinte: “COMMENT_CA_MARCHE”. Eis as frequências de aparecimentos das letras :

MACE_HONTR
3222211111



Eis a árvore correspondente :

árvore de huffman



Os códigos correspondentes a cada carácter são tais que os códigos dos caracteres mais frequentes são curtos e os que correspondem aos símbolos menos frequentes são longos :

MACE_HONTR
001001100100111110111110101011010111



As compressões baseadas neste tipo de codificação dão boas taxas de compressão, em especial para as imagens monocromas (os telefaxes, por exemplo). É utilizado nomeadamente nas recomendações T4 e T5 do ITU-T

Veja também


Huffman coding
Huffman coding
Código Huffman
Código Huffman
Codage de Huffman
Codage de Huffman
Codifica di Huffman
Codifica di Huffman
Este documento, intitulado 'Codificação de Huffman', está disponível sob a licença Creative Commons. Você pode copiar e/ou modificar o conteúdo desta página com base nas condições estipuladas pela licença. Não se esqueça de creditar o CCM (br.ccm.net) ao utilizar este artigo.