Codigo Deflate LZ77

Multimédia II

Universidade Fernando Pessoa
2012/2013

Método Deflate LZ77 combinado com Huffman para compressão e descompressão sem perdas

Elaborado por:
Fábio Mota, 18887
Duarte Velho, 19829
Miguel Cunha, 20646

Índice
Índice 3
1. Introdução 4
1.1Objectivos do trabalho 4
1.2 Justificação 4
1.3 Áreas de aplicação 5
2. O algoritmo Deflate 6
2.1 Codificação 6
2.1.1 LZ77 6
2.1.2 Huffman 6
2.2 Descodificação 7 2.2.1 LZ77 7 2.2.2 Huffman 7
2.3 Exemplo de aplicação 8
2.3.1 Codificação 8 2.3.1.1 Exemplo Codificação usando o LZ77 8
2.3.1.2 Exemplo Codificação usando o Huffman 9
2.3.2 Descodificação 11
2.3.2.1 Exemplo Descodificação usando LZ77 11
2.3.2.2 Exemplo Descodificação usando Huffman 12
3. Implementação do algoritmo Deflate 13 3.1 Código LZ77 13
3.2 Código Huffman 16
4. Comparação com outros métodos semelhantes 23
5. Conclusão 24
Bibliografia 25

Resumo
O algoritmo designado por Deflate é uma combinação de várias tecnologias de compressão de dados, usadas em ficheiros de texto (.txt). Combinando LZ77 com o método de Huffman e o mesmo vai comprimir o resultado da compressão do LZ77.
1. Introdução A informação multimédia levou ao aparecimento de técnicas de compressão, necessárias para a minimização do espaço de armazenamento assim como o aumento da velocidade de acesso aos mesmos. Neste seguimento foram criados vários métodos e codec’s para esse efeito, sendo o que vamos apresentar, o método deflate.

O deflate é um método de compressão sem perdas e uma técnica de codificação de entropia, baseado na combinação do algoritmo LZ77 com Huffman.
LZ77 foi um dos algoritmos criados em 1977 por Abraham Lempel e Jacob Ziv mas que originalmente foi definido por Phil Katz e posteriormente especificado no RCF 1951.
Huffman foi desenvolvido em 1952 por David A. Huffman enquanto estudante do MIT.
A aparição do deflate só se fez em 2008, sendo utilizado nos