Orientador: |
CHRISTINE VIEIRA SCARPATO  |
Resumo: |
A área de compactação de dados é uma das áreas mais antigas da computação, em 1950 já se estudavam métodos para isso. Nas décadas de 80 e 90 essa área teve um grande crescimento com o desenvolvimento de algoritmos que utilizamos até hoje como Huffman, LEMPEL-ZIV & WELCH LZW, Burrows-Wheeler Transform BWT e Prediction by Partial Matching PPM. Após ler sobre o assunto, e descobrir que compressores atuais como WinZip e WinRar utilizam esses algoritmos nos interessamos a conhecer melhor seu funcionamento, e através de técnicas de análise de desempenho, como a taxa de compactação, velocidade de compactação e uso da memória, descobrir o melhor algoritmo para cada tipo de arquivo. Neste trabalho implementamos uma ferramenta chamada FADA-CHL que implementa o algoritmo de HUFFMAN e o algoritmo de LZW, essa ferramenta analisa os resultados para os arquivos do benchmark da Canterbury Corpus desenvolvido pela universidade de CanterBury da Nova Zelandia. Durante o desenvolvimento da ferramenta obtivemos problemas com dois arquivos para analise por causa do tamanho desses arquivos. Após a execução da ferramenta podemos obter os resultados mais favoráveis para o algoritmo de HUFFMAN quando aplicado a tabela de CanterBury Corpus por termos em geral arquivos de texto onde o algoritmo de HUFFMAN possui uma taxa de compactação e tempo de execução bem melhor, essas taxas maiores se dão pela utilização de arvores binárias. Os tempos de execução de HUFFMAN são muito melhores que os tempos do algoritmo de LZW, em média o algoritmo de HUFFMAN é 200 vezes mais rápido que o algoritmo de LZW. Quanto a utilização de memória os dois algoritmos possuem uma utilização parecida. Como uma conclusão podemos dizer que quando aplicados a tabela CanterBury o algoritmo de HUFFMAN é mais eficiente em todos os parâmetros abordados e a ferramenta desenvolvida atende os requisitos e funcionalidades para a qual foi desenvolvida. Como trabalhos futuros sugerimos a implementação de análise estatística sobre os resultados obtidos e fazer com que a própria ferramenta possa gerar esses resultados. |