Compactação - Parte 2

Em 1984 Terry Welch inventou uma implementação aperfeiçoada do algorítimo LZ78 que mencionamos na parte 1. Este algorítimo, o LZW, fez muito sucesso nos final dos anos 80, sendo usado no utilitário compress do Unix, nos programas ARC, PKARQ e PKZIP e nos formatos GIF e PDF.

Um dos motivos do sucesso do LZW foi a publicação por Welch de um artigo detalhado na revista Computer do IEEE (uma imagem digitalizada do artigo, em formato PDF, pode ser baixada daqui). O que pouca gente percebeu é que uma patente também tinha sido solicitada, com a Sperry Corporation como beneficiária. Pouco depois a Sperry se juntou com a Burroughs para formar a Unisys. Esta patente (que pode ser baixada daqui), virou assunto nos anos 90, quando a Unisys decidiu cobrar o licenciamento da Compuserve (criadora do formato GIF) e, mais tarde, dos sites que possuíam imagens no formato GIF. A patente expirou nos EUA em 2003, mas neste ponto o interesse pelo LZW já tinha caído, em parte devido à patente e em parte pelo uso do LZ77 para obter maiores taxas de compactação.

Um ponto curioso é que Welch é engenheiro eletrônico por formação, e a sua descrição original estava bastante voltada para a implementação do LZW em hardware. No artigo ele chega a mencionar que "a implementação do LZW em software é possível mas significativamente mais lenta", o que não o impediu de colocar na solicitação da patente exemplos de implementação em FORTRAN.

O algorítmo LZW se destaca por obter taxas altas de compactação (desde que os dados tenham alta redundância, é claro), processando os dados sequencialmente e uma única vez (isto é, não é preciso analisar todo o arquivo antes de compactar ou ter que ficar "indo e vindo" no arquivo) e sem consumir quantidades exorbitantes de memória (isto na época, hoje a memória necessária para implementar o LZW pode ser considerada minúscula).

O Algorítimo de Compactação

Vamos considerar inicialmente uma forma básica do algorítimo e depois ver alguns aperfeiçoamentos que podem ser feitos. Nesta forma básica, o "compressor" recebe os dados originais codificados em um código de um tamanho fixo (tipicamente bytes com 8 bits, para fins de exemplo vamos considerar que seja um texto codificado em ASCII) e gera os dados compactados codificados em um código com outro tamanho fixo, maior que o de entrada (vamos tomar como exemplo códigos de 12 bits). Note que isto significa que para dados não compactáveis pode ocorrer um aumento de tamanho (como vimos na parte 1, isto é inevitável).

O objetivo do algorítimo é ir associando aos códigos de saída sequências de caracteres consecutivos encontrados na entrada. Estas associações são armazenadas em uma tabela (que funciona como um dicionário para traduzir sequências de caracteres da entrada em códigos da saída). Isto é feito da seguinte forma:

1. Os primeiros códigos da tabela correspondem aos códigos de entrada. No meu exemplo, as primeiras 256 posições teriam os códigos da tabela ASCII. O resto das combinações do código de saída (no meu caso, 4096 - 256 códigos) vão ser usados para representar sequências.
2. Começamos com uma sequência vazia.
3. Lemos um caracter da entrada e o concatenamos à sequência atual.
4. Procuramos a sequência na tabela. Se ela já estiver lá, voltamos ao passo 3.
5. Se a sequência atual não está na tabela, colocamos na saída o código da última sequência reconhecida, colocamos a sequência atual na tabela, usamos o último caracter lido como a nova sequência atual e voltamos ao passo 3.

Simples, não?

Na descrição acima deixei de fora dois pontos triviais:

• No passo 3, se chegamos ao fim da entrada colocamos na saída o código da última sequência reconhecida e encerramos o algorítimo.
• No passo 5 pode ocorrer que a tabela esteja cheia. Neste caso (por enquanto) basta não colocar a sequência atual na tabela.

Um ponto não trivial é não guardar na tabela a sequência codificada com o código de entrada. A sequência a ser colocada é sempre composta de uma parte inicial que já está na tabela (e portanto tem um código de compactação já associado) seguido de um caracter. Portanto podemos compactar as sequência na tabela para a forma wc onde w é um código de compactação e c é um código de entrada.

Codificando de uma forma livre em C:

int prox;  // proximo código de saída
int w;     // código da sequência atualmente conhecida
int nw;    // código da nova sequência
char c;    // caracter sendo examinado

prox = 256;
w = LeEntrada();
while (! Eof())
{
c = LeEntrada();
nw = Procura (c, w);
if (nw != 0)
{
// achou na tabela
w = nw;
}
else
{
// não está na tabela
EscreveSaida (w);
if (prox < 4096)
{
  Guarda (c, w, prox);
  prox++;
}
w = c;
}
}
EscreveSaida (w);

No pseudo-código acima, LeEntrada obtem o próximo byte dos dados a compactar e EscreveSaida escreve um código de compactação na saída (o que exige uma pequena "sambadinha", já que estamos falando em código de 12 bits que corresponde a 1,5 bytes).

O último ponto de interesse é como implementar de forma eficiente as rotinas Procura e Guarda usadas acima. A forma mais tradicional é usar uma tabela com hash. Uma função de hash converte o para (c, w) em um índice para a tabela. Na hora de guardar, verificamos primeiro se esta posição está livre; se sim é só guardar o para nela. Se a posição estiver ocupada, somos obrigados a fazer um rehash (o mais simples é usar a posição seguinte, circularmente) até acharmos uma posição livre. Na hora de procurar, calculamos o hash e verificamos esta posição. Se ela estiver vazia, o para não está na tabela. Se a posição estiver ocupada, precisamos conferir se contém o para desejado; se sim achamos. Se a posição está ocupada por outro par, somos obrigados a ir fazendo o rehash até achar o par ou posição vazia. Para reduzir as colisões, além de uma boa função de hash, usamos uma tabela maior que o mínimo necessário. Por exemplo, para guardar as 4096 combinações do código de 12 bits podemos usar uma tabela de 5021 posições (sugere-se pelo menos 20% maior e um tamanho primo).

Cada entrada na tabela vai conter o código que está sendo armazenado, o código do prefixo e o caracter final. Reparar que a tabela vai ocupar 5021*4 = 20084 bytes. No tempo em que um PC básico tinha 256K e era preciso trabalhar com segmentos limitados a 64K isto era uma memória razoável. Nos dias de hoje, mesmo se dando ao luxo de usar 2 bytes para cada código na tabela e consumir 25K, isto é (como diria o Patolino) desprezível.

O Algorítimo de Descompactação

A descompactação consiste basicamente em ir construindo uma tabela com os códigos que o compactador criou e ir obtendo dela as sequências a serem gravadas na saída. Existe, porém, um caso patológico (previsto corretamente pelo Welch) em que o descompactador recebe um código que ainda não está na sua tabela. Para enter isto, vamos examinar em paralelo a compactação e descompactação da sequência XabXaXk (como se os códigos de saída do compactador entrassem diretamente no descompactador):

No passo final acima, o compactador emitiu o código 259 que ainda não é conhecido pelo descompactador. Felizmente este caso é único: sempre que o descompactador receber um código desconhecido basta considerar que ele equivale ao código anterior recebido (no caso 256) mais o primeiro caracter deste código (no caso X).

Indo direto ao código:

int prox;  // proximo código na tabela
int w;     // código a descompactar
int lw;    // último código a descompactar
char c, nc;

prox = 256;
w = LeEntrada();
EscreveSaída (w);
lw = w;
while (! Eof())
{
w = LeEntrada();
if (w >= prox)
{
  // caso especial
  nc = EscreveSeqSaida(lw);
  EscreveSaida (c);
  c = nc;
}
else
  c = EscreveSeqSaida (w);
if (prox < 4096)
{
  tab[prox].w = w;
  tab[prox].c = c;
  prox++;
}
lw = w;
}

char EscreveSeqSaida (int w)
{
  while (w >= 256)
  {
      push(tab[w].car);
      w = tab[w].w;
  }
  push (w);
  while (PilhaNaoVazia())
      EscreveSaida (pop());
  return w;
}

Apesar de eu ter usado os mesmos nomes da parte anterior, aqui LeEntrada lê um código compactado e EscreveSaída escreve um código descompactado.

A parte interessante está em EscreveSeqSaída. Ao converter um código compactado na sequência de caracteres descompactados, os caracteres são obtidos na sequência contrária e portanto é preciso uma pilha para gravá-los na ordem correta.

A tabela para o descompactador é mais simples, pois não precisamos fazer uma procura por prefixo + caracter. O código pode ser usado diretamente como índice e cada entrada contém apenas o código do prefixo e o caracter final.

Aperfeiçoamentos

Os algorítimos acima são supreendentemente razoáveis. Além disso existem alguns aperfeiçoamentos que podem melhorá-lo ainda mais:

• O uso de códigos de compactação maiores, como 16 bits, possibilita armazenar um número maior de sequências, aumentando a probabilidade de codificação das sequências na entrada.
• O uso de um tamanho fixo nos códigos de saída é um desperdício, já que os códigos gerados vão crescendo de tamanho à medida em que a tabela é preenchida (no nosso exemplo, começamos gerando códigos de 9 bits mas os estamos gravando com 12 bits). O usao de códigos de tamanho variável complica a parte de entrada e saída mas permite uma compactação maior.
• Parar de atualizar a tabela quando ela enche é ruim no caso dos dados não serem uniformes ao longo de toda a entrada. Para melhorar isto, a tabela pode ser limpa (total ou parcialmente) quando encher e/ou quando for detectado que a taxa de compactação está caindo.

Referência Adicional

Além do livro do Mark Nelson (mencionado na parte 1) e dos textos de Welch (linkados no início desta parte) usei o artigo "Lossless Data Compression" de Steve Apiki, da revista BYTE de março de 1991 (do bom tempo em que as revistas de informática publicavam artigos técnicos e código).

A Seguir

Um exemplo mais real de LZW em C.


Atualizado em 30/07/09 para acertar a descrição das tabelas.