Quarto Exercício-Programa - HUFF
MAC122 - Princípios de Desenvolvimento de Algoritmos
BCC - 2o. Semestre de 1998
Introdução
Este quarto exercício-programa é um exercício sobre compactação ou compressão
de arquivos. Ele consiste de duas partes: (a) um compressor de arquivos
básico (b) descompressor para acompanhar o compressor. O algoritmo de
compressão será baseado no código de Huffman.
Voce deve escrever dois programas, digamos ep4a e ep4b. Os
programas devem ser em C (preferencial), C++, ou,
excepcionalmente, Java.
Compressão
Basicamente falando, o seu ep4a deve receber como entrada um arquivo
texto texto.txt e deve produzir um arquivo binário
texto.txt.huff, que é a versão compactada do arquivo de entrada.
Código de Huffman. Vimos como funciona o código de Huffman na
aula de 26/11/98. Para mais detalhes, veja Sedgewick, Algorithms in
C (capítulo 22 na primeira edição). Veja também Knuth, vol. 3 (seção
6.2.2). Voce também pode ver a página dos EPs
da disciplina MAC323, Estruturas de Dados (veja o EP4 daquela
página). [Ou veja este diretorio.]
Você pode pegar uma versão bem primitiva da primeira parte do nosso EP aqui:
huff.c. Para escrever este programa, copiei os vários
pedaços de código dados no livro de Sedgewick.
Descompressão
O processo de descompressão é bastante simples, como visto em aula. O seu
ep4b deve ser capaz de descomprimir os arquivos gerados pelo seu
ep4a. Naturalmente, o arquivo reconstituído desta forma deve ser
idêntico ao original.
Alguns detalhes
Arquivos binários. Os arquivos compactados que você gerará
deverão ser binários. Para ver como você pode manipular tais arquivos, você
pode estudar estes exemplos: escreva_bits.c, leia_bits.c.
Formato do arquivo compactado. Como vimos em aula, o arquivo
compactado deve conter a tabela de codificação usada. No programa
huff.c acima (seguindo a implementação de Sedgewick), usam-se dois
vetores: code[] e len[]. Sugiro que o seu ep4a
ponha estes vetores no começo do arquivo compactado, de forma que o processo
de decodificação comece pela leitura destes vetores e então prossiga com a
decodificação propriamente dita.
Exemplos
Aqui estão alguns exemplos de execução do huff.
Compressores populares
O compressor gzip do projeto
GNU é talvez o melhor
compressor em circulação. Há, entretanto, o sério concorrente bzip2.
Prazo de entrega
Sexta-feira, 11 de dezembro de 1998, até as 18:00. Entregue seu EP na
secretaria do MAC, sala 256, bloco A, antes do término do expediente naquele
dia!
Observações
- O EP é estritamente individual. Exercícios semelhantes receberão nota
0.
- Exercícios atrasados não serão aceitos. Inclusive, nem haverá tempo
para corrigi-los até o fim do semestre.
- Exercícios com erros de sintaxe receberão nota 0.
- Endente o seu programa sistematicamente. Uma má apresentação do código
resultará em nota menor.
- Coloque comentários apropriados em seu programa. Programas sem
documentação receberão nota baixa.
- Coloque o cabeçalho usual em seu programa (como em MAC110), com nome,
número USP, curso, data, nome do professor e identificação do EP (EP4). Não
esqueça de indicar que compilador que você usou (Turbo C, Quick C, gcc,
etc).
- Entregue em um envelope (preferencialmente de plástico transparente):
- Um disquete com o código do seu programa. Identifique o disquete
com uma etiqueta.
- Uma listagem do programa.
- As saídas correspondentes aos exemplos no enunciado e quaisquer
outras saídas que você achar importantes (com as respectivas entradas,
em forma eletrônica). A abrangência dos seus testes também será
considerada na nota. Saber testar bem um programa é também muito
importante.
- Guarde uma cópia de seu material até o fim do semestre.
- Importante: entregue o seu material também por correio
eletrônico para o nosso monitor Ricardo Bueno Cordeiro <rbc@linux.ime.usp.br>, com cópias para <yoshi@ime.usp.br> e <armando@ime.usp.br>. Não
entregue executáveis.
Página principal de MAC122 (BCC - 2o. semestre de 1998).
Y. Kohayakawa
<yoshi@ime.usp.br>
Last modified: Wed Dec 9 20:53:01 EDT 1998