Codificação de Huffman

Setembro 2017
Em 1952,David Huffman propôs um método estatístico que permite atribuir um código binário aos diversos símbolos a serem comprimidos (pixels 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 usados são codificados com pequenas palavras de código, enquanto os símbolos mais raros recebem códigos binários mais longos. A expressão Codificação de comprimento variável (VLC -Variable Length Code) é utilizada para designar este tipo de codificação porque nenhum código é o prefixo de outro. Assim sendo, a sequência final de palavras codificadas com comprimentos variáveis será, em média, menor do que a obtida com uma codificação de tamanhos constantes.

O codificador Huffman cria uma árvore ordenada com todos os símbolos e a frequência com que aparecem. Os galhos são construídos recursivamente começando com os símbolos menos frequentes. Sucessivamente, os dois símbolos de mais baixa frequência de aparecimento são retirados da lista e unidos a um núcleo cujo peso vale a soma das frequências dos dois símbolos. O símbolo de mais leve é atribuído à ramificação 1, o outro à ramificação 0 e assim por diante, considerando cada núcleo formado como um novo símbolo, até obter um só núcleo parente, chamado raiz.

O código de cada símbolo corresponde à sucessão de códigos ao longo do caminho, que vai deste o caractere até a raiz. Assim, quanto mais profundo o símbolo na árvore, mais a palavra de código será longa.

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

MACE_HONTR
3222211111

Veja a árvore correspondente:
árvore de Huffman

Os códigos correspondentes a cada caractere 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 produzem boas taxas de compressão, em especial para as imagens monocromáticas (os faxes, por exemplo).

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
Última modificação: 30 de junho de 2017 às 13:32 por Pedro.CCM.
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.