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 :
| M | A | C | E | _ | H | O | N | T | R |
| 3 | 2 | 2 | 2 | 2 | 1 | 1 | 1 | 1 | 1 |
Eis a árvore correspondente :
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 :
| M | A | C | E | _ | H | O | N | T | R |
| 00 | 100 | 110 | 010 | 011 | 1110 | 1111 | 1010 | 10110 | 10111 |
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
Última modificação do dia Quinta 1 de Outubro de 2009 às 20:25:36.
A codificação consiste em? Baixaki gratis codificador do windows média player versão 11 Baixar programa para codificar cd e dvd Codificacao Codificacao de chaves Codificar arquivos do office 2007 para o 2003 Codificar modem Codificação ascii Codificação para criar uma pagina de internet Como faço para baixar codificador window media player versão 11? Como traduzir um texto codificado Download de codificador de windows media player Nao pode executar este dvd porque nao ha um codificador Numeros codificar