Instituto de Computação - UNICAMP

MC202 - Estruturas de Dados

Primeiro Semestre de 2007

Laboratório 4 - Peso 2

Compactação de Arquivos e Algoritmo de Huffman

Códigos de Huffman

Uma das aplicações interesantes de árvores binárias é a compactação de arquivos usando os chamados códigos de Huffman. Os códigos de Huffman são códigos binários (atribuídos, por exemplo, a caracteres em um texto) de comprimentos variados que são determinados a partir da frequência de uso de um determinado caracter. A idéia central é associar números binários com menos bits aos caracteres mais usados num texto, possibilitando a sua compactação. O algoritmo de compactação usando os códigos de Huffman tem três fases:
  1. Cálculo da freqüência de cada caracter no texto.
  2. Execução do algoritmo de Huffman para construção de uma árvore binária (árvore de Huffman).
  3. Codificação propriamente dita.
O algoritmo de descompactação usando os códigos de Huffman têm duas fases:
  1. Leitura e reconstrução da árvore de Huffman.
  2. Decodificação propriamente dita.
O objetivo deste laboratório será apenas simular o comportamento do algoritmo de Huffman. Para facilitar os testes, serão usados pseudo-bits (caracteres 0s e 1s em vez de bits 0s e 1s).

Algoritmo de Huffman

O algoritmo de Huffman tem por objetivo a construção de uma árvore binária baseada na frequência do uso destas letras em um texto. Considere a frase abaixo (todos os arquivos para teste usados neste laboratório foram extraídos de http://www.gnu.org). 
GNU's Not Unix
As freqüências dos caracteres no texto são: 
'\n': 1
' ': 2
''': 1
'G': 1
'N': 2
'U': 2
'i': 1
'n': 1
'o': 1
's': 1
't': 1
'x': 1
A árvore binária de Huffman será construída de baixo para cima (das folhas para raiz), começando a partir das letras menos usadas até atingir a raiz. Em cada passo do algoritmo, existe uma coleção de árvores de Huffman. No início, cada uma das letras forma uma árvore que é composta apenas pela raiz e cujo conteúdo é a frequência com que esta letra ocorre no texto. Em seguida, são escolhidas as duas árvores com as menores freqûencias associadas a elas são transformadas em uma só árvore cujo valor é a soma do valor destas duas. Este processo é repetido até a existência de uma única árvore (veja o algoritmo abaixo). 
Entrada: Conjunto C com n caracteres
Saída:   Árvore de Huffman

   Q <- Conjunto de n árvores formadas por nós com os caracteres em C
        e suas respectivas freqüencias;
   para i <- 1 até n-1 faça
      z <- nova raiz
      árvore esquerda de z = Árvore arv1 com freqüência mínima em Q,
                             sendo que arv1 deve ser removida de Q; 
      árvore direita de z  = Árvore arv2 com freqüência mínima em Q;
                             sendo que arv2 deve ser removida de Q; 
      freqüência de z = soma das freqüências de arv1 e arv2.
   Retorna árvore final em Q.

A codificação dos caracteres é feita, associando-se 0 às arestas da árvore de Huffman que ligam um nó com seu filho esquerdo e 1, às arestas que ligam um nó com seu filho direito. O código correspondente a cada letra será formado pelo número binário associado ao caminho da raiz até a folha correspondente. Desta forma, a tabela de códigos resultantes desta árvore de Huffman é: 

'x': 000
'\n': 0010
''': 0011
' ': 010
'G': 0110
'i': 0111
'N': 100
'U': 101
'n': 1100
'o': 1101
's': 1110
't': 1111
O arquivo "compactado" ficaria: 
01101001010011111001010011011111010101110001110000010
Para descompactar, basta percorrer a árvore da raiz até uma folha, obtendo os caracteres.

Arquivo de Entrada

O arquivo de entrada terá uma seqüência de comandos. Os seguintes comandos são válidos:

f arq.txt Exibe os caracteres presentes em arq.txt e suas respectivas freqüências no texto.
a arq.txt Exibe a árvore de Huffman correspondente ao arquivo arq.txt (percurso in-order).
c arq.txt Lê o arquivo arq.txt e exibe o resultado "compactado" em uma cadeia contendo apenas caracteres '0's e '1's
t arq.zip Lê a tabela de conversão de um arquivo arq.zip e exibe sua árvore de huffman (percurso in-order))
d arq.zip Descompacta o arquivo arq.zip exibindo seu conteúdo original