Compressão de dados explicada
Cada página web que carrega, cada ficheiro ZIP e cada imagem PNG foram comprimidos: tornados mais pequenos sem perder um único bit, e descompactados de novo à chegada. Os métodos por trás disto são surpreendentemente simples. Procuram coisas que se repetem e dizem «o mesmo de antes» em vez de as dizer outra vez. Até onde vai essa ideia, e onde para, é uma das histórias mais elegantes da informática.
Sem perdas e com perdas
A compressão é de dois tipos. A compressão sem perdas devolve exatamente o original, o que é essencial para texto, programas, folhas de cálculo e tudo aquilo em que um único bit errado importa. A compressão com perdas, usada em fotografias, música e vídeo, deita fora pormenores que as pessoas mal percebem e chega a tamanhos muito mais pequenos, mas o original perde-se para sempre. Esta página e o demonstrador tratam da compressão sem perdas, que funciona encontrando e removendo a redundância: as partes dos dados que podiam ter sido previstas.
Codificação por comprimento de sequência
O método mais simples substitui uma sequência de símbolos idênticos por uma contagem e pelo símbolo: doze píxeis brancos passam a 12W. Usavam-no as máquinas de fax, os primeiros formatos de bitmap e o formato de imagem PCX, porque as páginas digitalizadas e os desenhos simples estão cheios de sequências longas. Num texto comum é inútil, e até prejudicial: as sequências são raras, e escrever uma contagem para cada letra duplica o tamanho. A codificação por comprimento de sequência continua viva dentro de outros métodos, para as sequências de zeros que ficam depois de uma primeira transformação.
LZ77: apontar para trás
Em 1977, Abraham Lempel e Jacob Ziv, dois investigadores do Technion, em Israel, publicaram um método que mudou a área. O codificador guarda uma janela com o texto que acabou de processar. Se os caracteres seguintes já ocorreram na janela, escreve um par: a que distância para trás começa a cópia anterior e qual o seu comprimento. Caso contrário, escreve o próprio carácter. O descodificador não precisa de dicionário nenhum, apenas do texto que já reconstruiu. Uma referência pode até sobrepor-se ao texto que produz, de modo que uma sequência de 100 letras idênticas é uma letra e uma referência.
LZW: aprender um dicionário
O segundo método de Lempel e Ziv, o LZ78, constrói um dicionário em vez de olhar para trás numa janela. O aperfeiçoamento de Terry Welch de 1984, o LZW, começa com os 256 valores de byte e, a cada passo, envia o número da sequência mais longa que já conhece e acrescenta essa sequência mais o carácter seguinte como nova entrada. O descodificador reconstrói o mesmo dicionário apenas a partir dos números. O LZW era rápido e simples, e foi usado no comando compress do Unix, no formato de imagem GIF e nos ficheiros TIFF, até que as patentes sobre ele provocaram uma longa disputa nos anos 1990.
Deflate, ZIP e mais além
O método deflate de Phil Katz, introduzido com o PKZIP 2 em 1993, combina o LZ77 com a codificação de Huffman: depois de encontrar as repetições, dá os códigos de bits mais curtos aos literais, comprimentos e distâncias mais comuns. O deflate é usado no ZIP, no gzip, nas imagens PNG e na compressão de páginas web, e é o método que o demonstrador mede com o compressor do próprio navegador. Métodos mais recentes, como o Zstandard, o Brotli e o xz, usam janelas maiores, uma procura de correspondências mais inteligente e uma codificação de entropia mais precisa, e reduzem os ficheiros típicos mais 10 a 30%.
Porque é que nem tudo pode encolher
Nenhum método consegue tornar todos os ficheiros mais pequenos. Há 2ⁿ ficheiros de n bits, mas apenas 2ⁿ − 1 ficheiros mais curtos do que isso, por isso, se um método os reduzisse a todos, dois acabariam iguais e não poderiam ser ambos restaurados: é o princípio do pombal. Todo o compressor aumenta, portanto, algumas entradas, normalmente dados de aspeto aleatório, como ficheiros cifrados, ficheiros já comprimidos e ruído. É também um teste de aleatoriedade: dados que nenhum compressor consegue reduzir parecem aleatórios.
O limite da entropia
Claude Shannon mostrou em 1948 que a entropia de uma fonte é o menor número médio possível de bits por símbolo para qualquer código sem perdas. Contado letra a letra, um texto inglês tem uma entropia de cerca de 4 bits por letra, metade dos 8 bits em que é armazenado. Os métodos que usam o contexto, como o LZ77, ficam abaixo desse valor por letra isolada num texto repetitivo, porque uma referência representa um troço inteiro de uma só vez. Os melhores compressores modernos, que preveem cada letra a partir de tudo o que veio antes, reduzem o inglês a menos de 2 bits por letra.
Explore
Abra o demonstrador de compressão para aplicar o LZ77, o LZW e a codificação por comprimento de sequência a um parágrafo, a uma canção com refrão, a uma linha de píxeis, a uma tabela de dados, a letras aleatórias ou a ADN, ou ao seu próprio texto. Clique em qualquer referência do LZ77 para ver o que copia, veja o dicionário do LZW crescer e compare todos os métodos com o ZIP e com o limite da entropia.
Perguntas frequentes
O que significa uma taxa de compressão de 3 : 1?
Que o original é três vezes maior do que a versão comprimida, ou seja, o ficheiro comprimido ocupa um terço do espaço e poupa dois terços. Um texto chega tipicamente a 2 : 1 a 4 : 1 com o ZIP; dados com muita repetição, como ficheiros de registo, muitas vezes bem mais.
Porque é que comprimir de novo um ficheiro ZIP não ajuda?
A primeira passagem já removeu as repetições, e a sua saída parece quase aleatória. Uma segunda passagem não encontra nada para onde apontar e só acrescenta a sua própria sobrecarga, por isso o ficheiro fica do mesmo tamanho ou cresce ligeiramente.
Porque é que uma janela do LZ77 maior é melhor?
Uma janela maior permite ao codificador encontrar repetições que estão mais atrás, como um refrão que regressa depois de várias estrofes. O preço é que cada distância precisa de mais bits para ser escrita e que a procura demora mais, e é por isso que o deflate se fica pelos 32 KB e os métodos mais recentes permitem megabytes.
A compressão é o mesmo que a cifragem?
Não. A compressão torna os dados mais pequenos e qualquer pessoa a pode desfazer; a cifragem torna os dados ilegíveis sem uma chave. As duas são muitas vezes combinadas, e então os dados têm de ser comprimidos primeiro: os dados cifrados parecem aleatórios e já não podem ser comprimidos.
Pronto para experimentar?
Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.
Abrir o demonstrador de compressão