Codificação de Huffman


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).
Nosso conteúdo é produzido em colaboração com especialistas em tecnologia da informação sob o comando de Jean-François Pillou, fundador do CCM.net e diretor digital do Grupo Figaro. CCM é um site sobre tecnologia líder em nível internacional e está disponível em 11 idiomas.

Veja também

Última modificação: 30 de junho de 2017 às 13:32 por Pedro Muxfeldt.

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 (https://br.ccm.net/) ao utilizar este artigo.