Demonstrador de compressão
Como pode um ficheiro ficar mais pequeno sem perder uma única letra? Reparando que se repete. Cole um texto ou escolha um exemplo e veja três métodos clássicos a funcionar: o LZ77 aponta para trás, para texto que apareceu antes, o LZW aprende um dicionário de sequências à medida que lê, e a codificação por comprimento de sequência conta sequências do mesmo carácter. Cada método é descomprimido de novo para mostrar que nada se perdeu, e um gráfico compara-os com o ZIP e com o limite da entropia. Escreva ou cole um texto, ou escolha um exemplo, e escolha um método. O LZ77 substitui as repetições por referências a texto anterior: clique numa parte destacada para ver o que copia. O LZW constrói um dicionário de sequências à medida que lê e envia os respetivos números. O RLE condensa sequências do mesmo carácter. O gráfico compara cada método com o ZIP e com o limite da entropia, e a aplicação volta a descomprimir o resultado para verificar que nada se perdeu.
Como funciona
- Escreva ou cole um texto, ou escolha um exemplo: um parágrafo, uma canção com refrão, uma linha de píxeis, uma tabela de dados, letras aleatórias ou ADN.
- Escolha LZ77, LZW ou RLE. No LZ77, defina até onde pode recuar e clique numa referência destacada para ver o texto anterior que copia.
- Compare os tamanhos nos painéis e no gráfico com o ZIP e com o limite da entropia; a verificação por baixo do texto confirma que a descompressão devolve o original.
As repetições são a chave
A compressão sem perdas funciona porque os dados reais se repetem. O LZ77 guarda uma janela com o texto que acabou de ler; sempre que os caracteres seguintes já ocorreram nessa janela, escreve uma referência curta, recuar tanto e copiar tantos caracteres, em vez dos próprios caracteres. Uma referência custa um número fixo de bits, seja qual for o comprimento da cópia, por isso as repetições longas e frequentes são as que mais poupam. O LZW obtém o mesmo efeito de outra forma: constrói um dicionário com cada nova sequência que encontra e, a partir daí, envia o número dessa sequência.
Porque é que alguns dados não encolhem
Um método que torna alguns ficheiros mais pequenos tem de tornar outros maiores: há menos ficheiros curtos do que longos, por isso não podem ficar todos mais curtos. A compressão ganha com dados que têm padrões, como texto, tabelas e imagens simples, e perde com dados sem eles. Letras aleatórias, dados cifrados e ficheiros já comprimidos não dão aos métodos nada para onde apontar, e a saída fica tão grande como a entrada, ou maior. A codificação por comprimento de sequência mostra-o com mais clareza: num texto sem sequências, duplica o tamanho.
Perguntas frequentes
Qual é a diferença entre compressão sem perdas e com perdas?
A compressão sem perdas devolve exatamente o original, bit a bit; é necessária para texto, programas e dados, e este demonstrador mostra apenas métodos sem perdas. A compressão com perdas, como nas fotografias JPEG, na música MP3 e no vídeo, deita fora pormenores que mal se notam e obtém ficheiros muito mais pequenos, mas o original não pode ser recuperado.
Como é que o ZIP comprime ficheiros?
O ZIP e o gzip usam o deflate, que primeiro aplica o LZ77 com uma janela de 32 KB e depois escreve os literais e as referências com códigos de Huffman, códigos curtos para os valores comuns e longos para os raros. Esse segundo passo é a razão pela qual o ZIP costuma bater o LZ77 simples aqui mostrado, que gasta um número fixo de bits em cada token.
Pode o LZ77 ficar abaixo da entropia?
A entropia mostrada conta os caracteres um de cada vez, sem contexto. O LZ77 e o LZW usam o contexto, porque uma referência copia um troço inteiro de texto anterior, e por isso num texto repetitivo podem bater esse número por muito. Nunca conseguem bater a verdadeira entropia da fonte, que tem em conta todo o contexto.
Porque é que os tamanhos diferem de um ficheiro ZIP real?
O demonstrador conta apenas os bits dos dados codificados. Um ficheiro ZIP real acrescenta cabeçalhos, o nome do ficheiro, uma soma de verificação e as tabelas de Huffman, o que torna os ficheiros muito pequenos maiores em vez de mais pequenos.
O meu texto é enviado para algum lado?
Não. Todos os métodos, incluindo a comparação com o ZIP, são executados no seu navegador, e o seu texto fica no armazenamento local deste navegador.
Pronto para experimentar?
Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.
Ir para o editor