gustavooquinteiro/lzw-file-compressor

Implementação do algoritmo LZW para compressão e descompressão de arquivos

Relatório do Segundo Trabalho Prático

Compactador de arquivos desenvolvido por Daniel Lopes dos Santos e Gustavo Oliveira Quinteiro como trabaho da matéria MATA54 - Estrutura de Dados e Algoritmos II, ministrada pelo professor Flávio Morais de Assis Silva.

Decisões da Equipe

• Utilização do algoritmo de compressão e descompressão LZW (Lempel-Ziv-Welch) visto em sala
• Utilização da linguagem C++ para a implementação do algoritmo
• Criação da tabela inicialmente com todos os 255 caracteres ASCII printaveis
• Atribuição do caracter EOF (END OF FILE) à posição 256 da tabela
• Tamanho máximo da tabela igual a 2¹⁵ - 1, ou seja, 32767 posições
• Inicialização de codificação em 9 bits e aumento dessa codificação, se necessário, até alcançar o tamanho máximo da tabela

Quando o programa é iniciado pela primeira vez, o código máximo possível que o programa pode emitir é 256, que precisa apenas de nove bits para codificar. E cada vez que emitimos um novo símbolo, esse valor máximo possível do código aumenta apenas um, o que significa que os primeiros 256 códigos emitidos pelo codificador podem caber em nove bits.

Portanto, o codificador LZW começa a codificar usando larguras de código de nove bits e depois aumenta o valor para dez assim que o código de saída mais alto possível atingir 512. Esse processo continua, incrementando o tamanho do código até que o tamanho máximo da tabela seja atingido. Nesse ponto, o tamanho do código permanece fixo, pois nenhum novo código está sendo adicionado ao dicionário.

O decodificador segue exatamente o mesmo processo - lendo no primeiro código com uma largura de nove bits e depois pulando para dez quando o código de entrada máximo possível atingir 512.

• Daniel foi designado para a codificação da função de compactação¹
• Gustavo foi designado para a codificação da função de descompactação¹

Compilando o Compactador

É fornecido um Makefile para plataformas UNIX a fim de facilitar a compilação dos arquivos. Para compilá-los utilize o comando: make all no diretório corrente ao Makefile.

Testes

Testes realizados pela equipe mostraram uma compressão ótima (arquivo compactado com tamanho 60% a 90% menor o tamanho do arquivo original) para arquivos de texto, executáveis .out e código-fontes; e uma compressão satisfatória (arquivo compactado com tamanho entre 20% a 50% menor que o tamanho do arquivo original) em arquivos de música.

Adicionais

Adote essas convenções para melhor entendimento do texto a seguir:

arquivo_original.ext: qualquer arquivo com qualquer extensão.
arquivo_compactado.cmp: arquivo_original.ext compactado com nosso programa
arquivo_descompactado: arquivo_original.ext compactado e descompactado com nosso programa

Colocando arquivos no caminho tests/compress/ , o Makefile, com o comando make tests, é capaz de automatizar a:

1. execução da compressão: ./mata54comp -c arquivo_original.ext ; para cada arquivo_original.ext em tests/compress/
   • Para correta execução desse passo pelo Makefile e pelo programa é necessário que o nome do arquivo_original.ext não contenha espaços e um único .
2. verificação de taxa de compressão, comparando o tamanho de arquivo_original.ext e o tamanho de arquivo_compactado.cmp
   • Após esses passos todos os arquivos com extensão cmp são movidos para a pasta tests/decompress/
3. execução da descompressão: ./mata54comp -d arquivo_compactado.cmp; para cada arquivo_compactado.cmp em tests/decompress/
4. corretude da descompressão, executando diff -s arquivo_original.ext arquivo_descompactado; para cada arquivo arquivo_descompactado em tests/decompress/

As saídas exibidas em tela são referentes à execução dos passos 2 e 4.

Os arquivo_compactado.cmp e arquivo_descompactado estarão em tests/decompress/

¹ Para maiores detalhes de desenvolvimento vide o log do repositório