Instituto de Computação da UNICAMP
Disciplina MC326: Estruturas de Arquivos

2° Semestre de 2006

Prof. Ricardo da Silva Torres

Laboratório Nº 02 - Compactação de Arquivos e Algoritmo de Huffman


Códigos de Huffman

Uma das aplicações interessantes 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 consiste basicamente de três fases:

  1. Cálculo da frequência de cada caracter no arquivo.
  2. Execução do algoritmo de Huffman para construção de uma árvore binária (árvore de Huffman).
  3. Codificação propriamente dita.

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 de modo que as mais frequentemente usadas apareçam mais perto da raiz.

Esta árvore binária é 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 freqüência (f) com que esta letra ocorre no texto. Em seguida, são escolhidas as duas árvores com as menores freqüências associadas e elas são unidas em uma só árvore cujo valor da raiz é a soma do valor destas duas. Este processo é repetido até a existência de uma única árvore (veja algoritmo da figura abaixo).

Suponha que uma mensagem seja composta pelos caracteres A, C, E e que as frequências destas letras na mensagem sejam, respectivamente, 30, 15 e 45.

Na primeira etapa do algoritmo de Huffman, é construída uma árvore a partir dos nós de menor frequência. Neste laboratório, estamos considerando que sub-árvores de menor frequência ficarão à esquerda do novo nó criado.

O processo é repetido. Agora, temos 2 sub-árvores de mesma frequência. Neste laboratório, estamos considerando que, em caso de empate quanto à frequência, a sub-árvore que contiver o caracter de menor valor na tabela ASCII ficará à esquerda do nó criado. Assim, neste exemplo, o nó referente ao caracter E ficará à direita do nó criado. Note ainda, que para facilitar a comparação entre duas sub-árvores, a informação do caracter de menor valor na tabela ASCII é propagada para níveis superiores da árvore.

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 é:

A 01
C 00
E 1

Objetivo:

O objetivo deste laboratório é implementar um conjunto de funções para a codificação, decodificação, compactação e descompactação de arquivos. Na codificação, os dados comprimidos são representados no formato texto pelos caracteres '1' e '0', e na compactação o formato é binário. Os arquivos comprimidos possuem um cabeçalho no formato texto contendo a tabela de codificação, com a seguinte estrutura:

10
10 1000
32 1001
33 1010
72 1011
87 1100
100 1101
101 1110
108 01
111 00
114 1111
13
T
...

A primeira linha contém o número t de linhas da tabela de codificação. As próximas t linhas representam a tabela de codificação, onde o primeiro número é o valor decimal de um caracter ASCII e o segundo é a codificação desse caracter na árvore de Huffman. A próxima linha contém o tamanho em bytes da informação descomprimida, e a linha seguinte indica se a representação do dado comprimido é no formato texto (T) ou no formato binário (B). A partir deste ponto há uma seqüência de caracteres '1' ou '0', se a representação for no formato texto, ou uma seqüência de bytes se a representação for no formato binário. Não há quebra de linha no fim da seqüência.

Os comandos disponibilizados para o usuário são:

ComandoDescrição
tabela file.txt Abre o arquivo file.txt e imprime a tabela de codificação.
codificar file.txt Abre o arquivo file.txt e imprime o arquivo codificado (formato texto).
compactar file.txt Abre o arquivo file.txt e imprime o arquivo compactado (formato binário).
descomprimir file.huff Abre o arquivo comprimido (formato texto ou binário) file.huff e imprime o arquivo descomprimido.
sair Sai do programa.

Implementação:

O laboratório consiste na implementação de três bibliotecas: heap.c, arvhuff.c e huffman.c. O interpretador de comandos principal.c é fornecido na íntegra e não deve ser modificado.

heap.h e heap.c

O primeiro arquivo contém a interface com as assinaturas das funções que deverão ser implementadas no arquivo heap.c. Não é permitido modificar o arquivo heap.h.

arvhuff.h e arvhuff.c

O primeiro arquivo contém a interface com as assinaturas das funções para a montagem da árvore de Huffman, que deverão ser implementadas no arquivo arvhuff.c. Não é permitido modificar o arquivo arvhuff.h.

huffman.c

O arquivo deverá conter a implementação das funções de compressão e descompressão de dados.

Entrada e saída:

A entrada do programa consiste em uma seqüência de comandos. Espaços em branco serão ignorados. A impressão dos arquivos comprimidos deve conter o cabeçalho mencionado acima. Por exemplo, a seguinte entrada:

tabela hello.txt
sair

Gera a saída:

10
10 1000
32 1001
33 1010
72 1011
87 1100
100 1101
101 1110
108 01
111 00
114 1111

E a entrada:

codificar hello.txt
sair

Gera a saída:

10
10 1000
32 1001
33 1010
72 1011
87 1100
100 1101
101 1110
108 01
111 00
114 1111
13
T
101111100101001001110000111101110110101000

Testes:

Os testes estão classificados em 5 grupos, que testam as funções em ordem crescente de dificuldade.


Observações adicionais:

1. Devem ser submetidos os arquivos heap.c, arvhuff.c e huffman.c.

2. A sua última submissão deve incluir todos os casos.

3. O número máximo de submissões não pode passar de 20.

4. Realize experimentos para verificar a taxa de compressão média obtida pelo método, considerando os diferentes arquivos de entrada.