Depois de dominarmos os conceitos básicos é hora de mergulharmos no que está mais perto do nosso dia-a-dia.

A classe a seguir foi uma grande evolução na forma de compressão de arquivos, e é uma melhoria do algoritmo LZ78, que liderou sua área por mais de trinta anos após ser descoberta, não com a igual implementação, mas sempre com algum tipo de derivação e otimização. É uma solução baseada em dicionários, e funciona da seguinte maneira:

Supondo que temos a simples sequência de caracteres ABFABFABF dizemos então que temos 3 símbolos diferentes, A, B e F e teremos nesse caso que representar cada símbolo três vezes com uma entropia média de 1.59 bits. O que a classe de algoritmos Lampel-Ziv faz é procurar sequências de símbolos que se repitam e transformar essas sequências em símbolos para a partir disso diminuir seu tamanho, no caso à cima temos o seguinte novo símbolo: ABF que se repete 3 vezes com a entropia média de 1 bit. Temos uma média de ganho na casa de 4.77 bits (1.59 x 9 / 1 x 3) vezes nesse caso.

O algoritmo de compressão tem cinco passos:

1. Inicializar o dicionário contendo todas as sequências de tamanho um
2. Procurar na sequência o maior bloco X que está no dicionário
3. Troca a cadeia de símbolos da entrada pelo índice do dicionário
4. Adiciona a sequência mais o próximo símbolo ao dicionário
5. Volte ao segundo passo

O descompressão é mais simples, basta termos o dicionário a sequência de indexação e fazermos a substituição.

O GIF a seguir demonstra de forma bem didática o que acontece o tem duração de cerca de 2 minutos. O gif está originalmente em: http://www.data-compression.com/lempelziv.html

Esse é apenas um de muitos algoritmos que foi gerado nessa família, segue a árvore com a maioria deles. Qual a aplicabilidade real dessa árvore? Pois bem, além de compressão pura, existem programas que usam (usavam no caso do PDF) esses algoritmos diretamente na aplicação:

• Formato GZIP
• Formato TAR
• Arquivos do tipo .TIFF
• Arquivos do tipo .GIF (isso mesmo)
• Arquivos do tipo JPEG
• Arquivos do tipo MPEG
• Alguns formatos menos "glamurosos" como CCITT (modens), ARC, PAK

Fontes:

• A technique for high-performace data compression
• Lempel-Ziv-Welch
• Animation of Lempel-Ziv Encoding Algorithm