Kioskea
Pesquisar

Codificação de Huffman

Março 2015

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

Para uma leitura offline, é possível baixar gratuitamente este artigo no formato PDF:
Codificacao-de-huffman.pdf

A ver igualmente


Huffman coding
Huffman coding
Código Huffman
Código Huffman
Huffman-Kodierung
Huffman-Kodierung
Codage de Huffman
Codage de Huffman
Codifica di Huffman
Codifica di Huffman
Este documento, intitulado « Codificação de Huffman »a partir de Kioskea (pt.kioskea.net) está disponibilizado sob a licença Creative Commons. Você pode copiar, modificar cópias desta página, nas condições estipuladas pela licença, como esta nota aparece claramente.