DEFLATE
O algoritmo de Phil Katz conhecido como DEFLATE é uma combinação de diversas tecnologias de compressão de dados usada nos arquivos do padrão ZIP e PKZIP
A base do algoritmo é uma compressão usando LZ77 com janela deslizante de 32KB e um buffer de look-ahead de 258 bytes, e a saída deste passo é codificada usando-se codificação de Huffman. O arquivo é dividido em blocos de tamanho arbitrário e a divisão entre os blocos é feita quando o codificador identifica a necessidade de se construir um novo bloco com árvores Huffman diferenciadas. Duas árvores Huffman são usadas, uma para codificar os caracteres literais e o comprimento das cadeias encontradas pelo LZ77 e outra árvore para codificar as distancias entre as cadeias e a posição atual.[1] As árvores são armazenadas no início de cada bloco comprimido.
A identificação de padrões é feita usando-se uma tabela de espalhamento que armazena todos os padrões de tamanho igual ou maior a 3 bytes encontrados, agrupados pelos seus primeiros 3 bytes. Cada padrão do grupo que inicia com os 3 bytes iniciais do buffer de look-ahead é comparado com a sequencia atualmente no buffer para se determinar a maior sequência de casamento. Para evitar o pior caso onde uma busca sequência é feita num único grupo da tabela de espalhamento, as listas encadeadas que armazenam os grupos podem ser truncadas de acordo com as opções definidas no início da execução do algoritmo. Assim o DEFLATE não garante encontrar a melhor sequencia, mas sim uma sequencia razoavelmente longa.
Além disso o algoritmo acrescenta um mecanismo de casamento de padrões deferido com um método "guloso" de avaliação (greedy evaluation): Caso a sequencia encontrada seja muito curta, o DEFLATE tenta casar a próxima sequencia (que começa no segundo byte do buffer) e ver se esta gera uma sequencia melhor. Caso consiga esta sequencia melhor, uma sequencia de tamanho 1 é emitida para o primeiro byte, e a sequencia melhor é usada a partir do segundo byte. O tamanho necessário para se evitar essa avaliação "gulosa" é definida por parâmetros de execução, privilegiando seja a compressão (tamanho menor), seja a velocidade (tamanho maior).
Aplicações[editar | editar código-fonte]
O algoritmo DEFLATE é usado nos utilitários que comprimem ou descomprimem arquivos no padrão ZIP ou no padrão gzip. O formato ZIP se tornou popular através do programa PKZIP, e é hoje usado na maioria dos programas de compressão de dados. Esse algoritmo também é usado para comprimir imagens no formato PNG.
Notas e referências[editar | editar código-fonte]
Bibliografia[editar | editar código-fonte]
- (em inglês) SALOMON, David (2000). Data Compression. The Complete Reference 2 ed. Nova Iorque: Springer. ISBN 0-387-95045-1