Codigos de Huffman

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 :

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.

A compactação foi muito usada no início da era dos microcomputadores, pois preservavam espaço nos discos rígidos que eram extremamente pequenos e caros. Os disquetes, muitas vezes, não comportavam totalmente arquivos maiores, principalmente programas de instalação. Isso obrigava a compactar o arquivo de forma dividida em vários disquetes[COM 05].

Hoje, mesmo com grandes discos rígidos e gravadores de CDs a compactação continua sendo usada. A razão disso se explica no fato de o acesso de muitos computadores a redes, tanto públicas quanto privadas, ser feito ainda por meios com baixa largura de banda onde a informação não pode ser muito elevada, como os modens domésticos usados para acessar à internet e chegando a uma taxa de transmissão máxima de 56KBPS [COM 05].

Um código compactado é considerado ótimo quando as palavras-código com maior probabilidade possuem menor tamanho. Nesse sentido, as duas palavras-código de menor probabilidade possuem o mesmo tamanho e diferem somente no ultimo bit.

A compressão pelo algoritmo de Huffman reduz o tamanho do código usado para representar os símbolos de um alfabeto. Símbolos do alfabeto que ocorrem frequentemente são atribuídos por códigos mais curtos. O principal objetivo é permitir ao tamanho do código variar de caracter para caracter e de assegurar que o codigo utilizado seja menor. O código de Huffman é considerado como um código ótimo.

Codificação de huffman

O código de Huffman é uma das melhores técnicas de compressão atualmente utilizadas. É uma forma de compressão de dados em que se representa cada um dos caracteres de um texto com códigos binários de comprimento variável. O tamanho do código varia conforme a freqüência com que ocorre no texto, atribuindo-se códigos menores aos caracteres mais freqüentes e maiores aos menos freqüentes [MIL 02]. Este procedimento faz com que o código resultante seja menor. Consideramos a seguinte freqüência de símbolos um um arquivo: 10 vezes o simbolo “a”, 5 vezes o símbolo “b” e 1 vez o símbolo “e”. Neste caso o código de Huffman seria a=1, b=01 e e=00 o qual resultaria no tamanho total de 22 bits (10x1 + 5x2 + 1x2 = 22). Caso não usássemos o menor código para o símbolo de maior frequencia o tamanho do arquivo poderia ficar com 32 bits (a=00, b=01 e e=1 => 10x2 + 5x2 + 1x1 = 32), ou seja, haveria um acréscimo de 10 bits.

A compressão de Huffman é feita através da construção de uma árvore binária e é relativamente simples. Consiste em fazer uma varredura no arquivo a fim de determinar a freqüência de ocorrência dos símbolos no arquivo. É criada uma lista ordenada e classificada pela freqüência que os símbolos aparecem. Os dois últimos símbolos da lista são substituídos por um novo símbolo cuja probabilidade é a soma dos dois símbolos usados. Ordena-se a árvore novamente e repete-se a operação de substituição recursivamente até ficar apenas um símbolo. A figura 2.1.1 ilustra este processo. Após, o símbolo com probabilidade de 100% será a raiz da árvore e seus filhos serão os dois símbolos que a formaram. Repete-se este método até que todos os símbolos estejam presentes na árvore, onde os símbolos originais contidos no arquivo serão sempre folhas. A figura 2.1.2 mostra a construção desta árvore. O código do dígito será o caminho percorrido da raiz até a folha.

Figura 2.1.1 – Construção da árvore de Huffman – [ALH 05]

Figura 2.1.2 – Construção da árvore de Huffman – [ALH 05]

Um dos problemas apresentados pelo código de Huffman é que o tamanho da árvore de Huffman é proporcional ao número de símbolos e isto faz crescer o tamanho dos códigos. Uma solução para este problema é eliminar os símbolos pouco freqüentes da árvore. Esses símbolos são inseridos num conjunto chamado “DIVERSOS” e não têm codificação. Quando um desses símbolos aparece, é emitido um símbolo “DIVERSOS” seguido do símbolo propriamente dito, sem compactação.

Outra variante do código de Huffman é a Codificação de Huffman Adaptativa ou Huffman Adaptativo. Essa técnica foi criada para que se pudesse usar a compressão de Huffman em casos em que não se conhecem as freqüências de ocorrência de cada caractere no texto. Neste caso, devemos atualizar constantemente as freqüências (entrada) na árvore. Quando um caracter a ser codificado já existe na árvore ele é codificado de acordo com a seqüência de bits especificada. Quando um caracter é novo, ele é enviado sem compressão para o destino. O codificador então atualiza sua árvore para que seja incrementado o contador de ocorrências do caracter ou criado uma nova entrada na árvore. Este método é utilizado em aplicações que envolvem transmissão de texto.

Decodificação do código de Huffman

A decodificação do código de Huffman é mais simples que sua codificação. Primeiramente, escolhemos o primeiro bit do código como bit corrente e descemos um nível da Árvore de Huffamn, a partir da raiz, de acordo com o valor do bit corrente (0 => filho esquerdo ou 1 => filho direito) e atribuímos ao bit corrente do próximo bit da string de bits do código a decodificar. Quando atingimos uma folha da árvore de Huffman, devemos fazer a substituição dos bits correspondentes à trajetória até a folha pelo caractere contido nessa folha. Repetimos esses passos até que termine a string de bits do código a decodificar.

O código de Huffman com sua simplicidade, rapidez e auto-sincronismo é usado principalmente na compactação onde permanece imbatível, mas também, pode ser usado em outras áreas como criptografia.

Apesar de ser considerado um método de compactação ótimo, o ideal na construção de um software compactador seria a combinação de outros métodos, como a supressão de brancos e nulos e supressão de repetições a fim de melhorar as taxas de compactação.

Fonte: http://www.ebah.com.br/content/ABAAABmZMAC/uso-codigo-huffman-na-compactacao-dados

fonte: http://pt.kioskea.net/contents/video/huffman.php3