Compactação - Parte 1

Semana passada eu estava alterando um código que usa a Zlib (sobre a qual vou falar mais nesta série de posts) e resolvi relembrar um pouco sobre compactação de dados.

Compactação de dados sempre foi algo muito interessante, e teve um certo boom nos anos 80, quando os microcomputadores tinham discos pequenos e um modem rápido comunicava a 2400bps.

Princípios Básicos

A compactação de dados se baseia em reduzir a redundância contida nos dados. Existem vários tipos de redundância, que fazem com a mesma informação (ou algo bem próximo) possa ser codificada em menos bits. Alguns exemplos de redundância:

• limitações dos valores possíveis: imagine que você está usando um byte para guardar o resultado de um dado. Um byte é capaz de armazenar 256 combinações e você está usando somente 6.
• caracteres repetidos: em arquivos texto é comum termos sequências de zeros ou espaços.
• valor fixo em posições periódicas: como em um arquivo texto de colunas fixas, em uma coluna possui sempre o mesmo valor.
• probabilidade diferente dos valores: por exemplo, em um texto é bem mais comum as vogais que determinadas consoantes, porém usamos a mesma quantidade de bits para armazenar os dois.
• trechos repetidos: ainda considerando um texto, determinadas palavras se repetem várias vezes.

Do ponto de vista da Teoria da Informação, costuma se dizer que a compactação mede quanto de informação realmente existe nos dados. No livro Fundação, de Isac Asimov, tem um trecho onde os cientistas desenvolvem uma forma de extrair o conteúdo essencial de um texto; quando eles resolvem processar várias horas de discurso de um político, o resultado é nada! Curiosamente, dados aleatórios são pouco compactáveis, pois os seus valores são praticamente imprevisíveis.

Quando estamos falando em compactação de arquivos, normalmente estamos falando em compactação sem perdas (lossless), na qual os dados originais podem ser fielmente recuperados do arquivo compactado. Uma outra modalidade importante são as compactações com perda; exemplos diários são a compactação de imagens (JPEG), vídeo (DivX, etc) e áudio (MP3). A compactação com perda faz sentido nestes casos pois a nossa vista e audição são limitados e consideram como iguais coisas diferentes. Nesta série vou falar somente da compactação sem perdas.

Uma besteira que se ouve com frequência é que determinado programa ou algorítimo reduz o tamanho dos dados de x%, sem perda. Na verdade, a taxa de compactação depende sempre da entrada. Uma vez compactado um arquivo, a redundância diminui e a capacidade de compactação dele se reduz. Se existisse um algorítimo que sempre reduzisse de x%, independente dos dados, poderíamos passar por ele um arquivo, pegar a saída e passar de novo, assim por diante, até ficar com um único byte (que obviamente não é capaz de representar toda a gama de arquivos possíveis).

Aliás, isto mostra que se um algorítimo sem perda é capaz de reduzir o tamanho de determinado tipo de arquivos, ele deve aumentar o tamanho de outros.

Algorítimos de Compactação

A forma mais eficiente de compactar um determinado tipo de arquivo é um algorítimo específico, feito por quem sabe o que pode estar no arquivo. Um exemplo clássico americano é o código usado por Paul Revere para ser avisado por onde as tropas britânicas estavam vindo: uma lanterna se por terra e duas se por água. Uma informação complexa foi reduzida a um bit, graças ao conhecimento da situação. Uma outra forma que pode ser eficiente é o uso de tabelas de código, ou dicionários.

Os algorítimos que vamos ver aqui, entretanto, se propõem a ser genéricos e não depender de tabelas ou dicionários mantidos externamente.

Codificação de Huffman

Normalmente usamos o mesmo número de bits para cada unidade de informação ou símbolo (como um caractere ou par de caracteres), independente da sua probabilidade. A Codificação de Huffman utiliza códigos de tamanho variável, atribuindo códigos menores para os símbolos mais frequentes. Desta forma o tamanho médio (bits por símbolo) é reduzido.

A codificação de Huffman apresenta alguns problemas práticos:

• Requer que a probabilidade dos símbolos seja conhecida, o que pode ser feita por uma análise prévia dos dados a codificar. Alternativamente pode-se usar uma estimativa ou analisar uma amostra dos dados, mas isto introduzir um erro.
• A codificação usa um número inteiro de bits por símbolo e portanto pode não retratar com precisão as probabilidades.
• A probabilidade dos símbolos pode não ser constante ao longo de um conjunto de dados. Por exemplo, um arquivo pode ter um cabeçalho no início com uma distribuição de probabilidades bem diferente do resto.

Apesar disso, a codificação de Huffman era predominante até o início dos anos 80. Atualmente ainda é usada mas como uma codificação auxiliar.

Run-Length Encoding

Uma forma bastante intuitiva de compactar dados é usar uma notação especial para, por exemplo, representar sequências de zeros ou espaços (por exemplo, passando de um formato de colunas fixas para um de campos separados por delimitadores).

A Run-Length Encoding (RLE) é uma generalização disto. A ideia é substituir repetições consecutivas de um código por uma indicação de repetição, o número de repetições e o código a repetir.

Tomando um exemplo hipotético de compactação de uma sequência de bytes por RLE:

• Uma sequência de um ou dois bytes iguais, diferentes de 0xFE, é copiada inalterada para a saída.
• Uma sequência de três ou mais bytes iguais ou uma sequência de um ou dois 0xFE, é compactada na sequência 0xFE repetições byte.

Por exemplo, a sequência 01 01 02 02 02 02 02 02 02 FE é compactada em 01 01 FE 06 02 FE 01 FE. A descompactação é trivial:

• Bytes diferentes de 0xFE são copiados inalterados para a saída.
• Se for encontrado 0xFE, copiar para a saída n repetições do byte b, onde n e b são os bytes que seguem o 0xFE.

Obviamente esta codificação será eficiente na medida em que a marca 0xFE for pouco frequente e ocorrerem sequências longas do mesmo caracter.

Um exemplo de situação em que a compatação por RLE pode ser vantajosa é em gráficos monocromáticos, principalmente se desenhados à mão.

O MacPaint e o formato TIFF podem utilizar uma compactação deste tipo. A descompactação é feita da seguinte forma:

1. Examina-se o byte seguinte do arquivo compactado (b).
2. Se o bit mais significativo for zero, copiar os b+1 bytes seguintes para a saída (bytes não compactados)
3. Se o bit mais significativo for um, repetir o byte seguinte -b vezes.
4. Voltar ao passo 1.
   

Lempel-Ziv

No final dos anos 70, Jacob Ziv e Abraham Lempel descreveram dois métodos de compactação que são a base das compactações mais comuns hoje, como a dos arquivos ZIP. Os dois métodos se baseiam na ideia de construir dinamicamente um dicionário para codificar os dados.

O primeiro algorítimo (conhecido como LZ77) utiliza uma janela que vai se deslocando por sobre os dados à medida em que são tratados. À medida em que os dados são examinados, verifica-se se eles já apareceram na janela, se sim no lugar dos dados é transmitida a posição e o tamanho da sequência na janela.

O segundo algorítimo (LZ78) vai montando um dicionário incremental à medida que os caracteres são lidos. Por exemplo, suponhamos que a sequência 'Daniel' é encontrada no início. O string 'Da' é colocado no dicionário. Mais adiante encontra-se a sequência 'Dante'; como 'Da' já é conhecido, colocamos 'Dan' no dicionário. Encontrando novamente 'Daniel', coloca-se 'Dani' no dicionário e assim por diante.

À primeira vista estes algorítimos são bastante intensivos em processamento e não parecem ser a melhor forma de montar um dicionário. A prática, entretanto, mostra que consegue-se obter grandes taxas de compactação para arquivos como boa redundância, como textos.

O problema do processamento foi inicialmente resolvido por uma implementação muito elegante de uma variação do LZ78, criada por Terry Welch. É este algorítimo (LZW) que veremos na próxima parte desta série.

Mais para o final dos anos 80, com o aumento da capacidade computacional disponível, o LZ77 passou a ser usado com mais frequência.

Bibliografia

Estes dois livros do começo dos anos 90 foram bastante úteis na época:

• The Data Compression Book, Mark Nelson. A teoria no livro é boa, mas os exemplos no disquete que acompanhava tinham bugs!
• Bit-Mapped Graphics, 2n Edition, Steve Rimmer. Foi aqui que eu aprendi a ler arquivos PCX, TIFF e GIF.