Mónica Neves

Um algoritmo guloso faz sempre  a melhor escolha no momento actual, e o que vamos descrever de seguida é uma importante aplicação desta mesma técnica: comprimir dados - Huffman code.

O código de Huffman é usado para comprimir dados e temos exemplos muito conhecidos  tais como: compress, pkzip , winzip. 

O algoritmo usa uma tabela de frequências de ocorrências de cada caracter, em que cada caracter é representado por um conjunto de bits . 

Se usarmos um comprimento fixo para cada caracter , dependendo do numero de caracteres assim calculamos o numero de bits que são necessários.

Exemplo : Temos 5 caracteres e as frequências são dadas na tabela seguinte o que dá um total de 205000 caracteres, utilizando um comprimento fixo são precisos (2ⁿ=8 ) n=3 bits .

Mas podemos fazer melhor, utilizando um comprimento variável, em que atribuímos um menor código ao caracter que tem uma maior frequência (e um maior código ao caracter que tem uma menor frequência ), utilizando assim uma técnica "gulosa".

Vamos comparar:

Olhando para a tabela , verificamos que:

• para o comprimento fixo são necessários 615000 bits;
• para o comprimento variável são necessários 450000 bits (50*2+25*3+15*3+40*2+75*2)*1000.

Conseguimos diminuir aproximadamente 27% do tamanho inicial, e mostrar que de facto é um código óptimo (e vamos demonstra-lo de seguida como atribuir os respectivos bits a cada caracter).

Como podemos verificar,  no ponto anterior, foi considerado um código de comprimento variável, em que tivemos o cuidado de não atribuir códigos ambíguos ou seja cada um não ser o código do outro , se por exemplo em vez de atribuir 0 a 'a', atribuíssemos 1, 111  não saberíamos se era três a´s ou um d.

Como resolver a ambiguidade?

    É muito simples, nunca atribuir códigos aos caracteres como prefixos de outros códigos de caracteres.

Applet - Exemplo do código prefixo.

Para o utilizar basta introduzir '1' ou '0' o que significa codificar os caracteres "a", "b", "c", "d" e "e".

codigofonte

Este applet foi retirado do seguinte site(mas com algumas alterações em relação ao aspecto do painel):

Sendo um código binário pode ser representado numa arvore binaria, os caracteres são as respectivas folhas na arvore , o ramo esquerdo corresponde a 0 e o ramo direito corresponde a 1. 

Para descodificar, que é muito simples, atravessamos a arvore da raiz até á folha para obter um caracter.

Um código óptimo é sempre representado por uma árvore completa , em que cada nó tem sempre 2 filhos excepto  as folhas, assim o nosso exemplo do código de comprimento fixo não é óptimo(figura 1), e o de comprimento variável (figura 2) é óptimo como podemos verificar nas seguintes figuras:

Para construir a respectiva arvore é necessário:

• ordenar as frequências numa fila de espera
• juntar as duas menores frequências dando a origem a duas folhas em que o no pai é a soma das frequências , que por sua vez esse valor (nova frequência)  vai ser inserido por ordem na mesma lista (ver figura 3).

Algoritmo do código Huffman:

 Huffman(c)                        
      n = |c|                        
      Q = c                          
      for i = 1 to n-1              
         z = Allocate-Node()
         x = Extract-Min(Q)          
         y = Extract-Min(Q)         
         left(z) = x
         right(z) = y
         f(z) = f(x) + f(y)
         Insert(Q,z)                 
      return Extract-Min(Q)      

• Q é uma lista de espera ordenada com as frequências de cada caracter.
• x e y são os filhos esquerdo e direito respectivamente da raiz z.
• Extract-Min serve para obter o menor elemento da lista Q.
• Insert insere o novo elemento z na lista.

Mónica Neves