Algoritmos de compressão

Este artigo faz uma apresentação dos algoritmos de compressão e qual a lógica de funcionamento dos mesmos. É o primeiro de uma série de três artigos que pretendo escrever falando sobre isso, que serão divididos em como começou, o que usamos hoje em dia, e por último a prática com implementação dos mais usados.

[ Hits: 9.682 ]

Por: Pablo Margreff em 23/03/2016 | Blog: https://pmargreff.wordpress.com/


Classe Lempel-Ziv-Welch



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:
Página anterior     Próxima página

Páginas do artigo
   1. Introdução
   2. Códigos de comprimento variável
   3. Árvores de Huffmann
   4. Classe Lempel-Ziv-Welch
   5. Conclusões
Outros artigos deste autor

Manipulação de imagens no formato PPM

Aumentando sua produtividade com o teclado padrão Dvorak

Gerando Números Aleatórios

Leitura recomendada

Instalando automounter e configurando o autofs no Debian Sarge

A tecla mágica SysRQ

Máquinas velhas a todo vapor

Linux (kernel) - A história do seu criador

Que tal criar uma mini-distro em 1 disquete?

  
Comentários
[1] Comentário enviado por ivo_cruz em 29/03/2016 - 08:30h

A saída do Q é 0100


Contribuir com comentário