quarta-feira, agosto 12, 2009

Compactação - Parte 5

Concluindo as mexidas com o meu código, implementei as seguintes alterações:

Código de tamanho variável

Ao invés de usar um tamanho fixo de 12 bits, o programa compactador começa gravando códigos de 9 bits e vai aumentando conforme necessário. Para facilitar as coisas no lado da expansão, o compactador grava dois códigos especiais, um para indicar que o tamanho do código foi aumentado e outro para indicar o fim do arquivo.

Códigos de 16 bits

Uma vez que memória não é problema nos dias de hoje (e quase ninguém sabe o quanto era complicado acessar uma tabela com mais de 64Kbytes no PC), é trivial aumentar o tamanho do código de 12 para 16 bits.

Qual o resultado de tudo isto?
  • O meu texto de teste tem 172K.
  • Compactando com códigos fixos de 12 bits, o arquivo compactado tem 74K.
  • Compactando com códigos variáveis de até 12 bits, o arquivo compactado tem 73K. O ganho é pequeno, pois a tabela enche rapidamente e os códigos pequenos são usados por pouco tempo.
  • Compactando com códigos fixos de 16 bits, o arquivo compactado tem 62K. Apesar de cada código ser 1/3 maior, a tabela maior permite guardar mais sequências, propiciando uma compactação melhor.
  • Compactando com códigos variáveis de até 16 bits, o arquivo compactado fica com 54K. Ainda não chegou ao nível do PKKip (38K), mas avançamos bastante do ponto inicial.
O código completo está aqui.

A Seguir

No próximo post desta série vamos examinar uma excelente biblioteca livre para compactação, a zlib.

Nenhum comentário: