Temas Glossário

Multimédia > Componentes > Técnicas de Compressão > Huffman Encoding

Huffman Encoding

Esta técnica de compressão foi criada por D. A. Huffman em 1950 e assenta sobre a assumpção de que 96% dos ficheiros texto consistem de apenas 31 caracteres: as letras minúsculas, o espaço, a vírgula, o ponto final e o enter. Esta observação pode ser usada para criar um esquema apropriado para os ficheiros texto.

Para isso, substituem-se os 31 caracteres em códigos de 5 bits: 00000='a', 00001='b', 00010='c', etc. Assim, consegue-se uma redução do tamanho de 96% do ficheiro para 5/8. O último dos cinco códigos de 5 bits (11111) é um indicador que mostra que o caracter não é um dos 31 caracteres normais. Os próximos 8 bits indicam qual é, então, o caracter ASCII. Assim, os 4% dos caracteres requerem 5+8=13 bits. A ideia é a de substituir caracteres frequentemente utilizados em menos bits, enquanto que os mais raros ocupam mais.

A característica interessante da codificação de Huffman é a maneira que armazena os códigos de tamanho variável. Por exemplo, se se receber uma sequência de bits (a 1 ou a 0) e cada caracter tiver 8 bits, basta partir a sequência em blocos de 8 bits. O problema está nos caracteres de tamanho variável, pois não se pode saber como os partir. A resposta a este dilema está na maneira como se selecciona os códigos binários dos caracteres.

Como se viu no exemplo anterior, a tem a maior probabilidade de aparecer, pelo que se substitui por um código com menos bits (1). O próximo caracter mais comum é o b, pelo que tem um código pequeno (01). E assim por diante.

Como se mostra no exemplo anterior, os bits são, então, agrupados em conjunto de 8 bits. É de reparar que a seguir a uma sequência de 0 vem um 1 e um código opcional. Isto permite que as sequências binárias sejam separadas em códigos sem a necessidade de delimitadores.

Uma sofisticação deste algoritmo é a codificação aritmética. Neste esquema, as sequências dos caracters são representadas por códigos individuais, de acordo com sua probabilidade de ocorrência. A vantagem deste método é uma melhor compressão (de 5 a 10%). Normalmente, é utilizado em conjunção com o run length encoding.

A implementação da codificação de huffman ou da codificação aritmética implica a existência de um acordo sobre os códigos utilizados para representar cada caracter ou grupo de caracteres. Isto pode ser feito de duas maneiras. A primeira é a de usar uma tabela de tradução pré-definida, apesar do tipo de informação que está a ser codificada. A alternativa mais complexa é a de incluir a tabela de tradução nos dados comprimidos.

eMail | Teste os seus conhecimentos | Ajuda

© Departamento de Engenharia Informática
Faculdade de Ciências e Tecnologia
Universidade de Coimbra