Deflación (algoritme)

En informàtica, el algoritme deflación, en anglés denominat DEFLATE, és un algoritme de compressió de senyes sense pèrdues que usa una combinació del algoritme LZ77 i la codificació Huffman. Va ser originalment definit per Phil Katz per a la versió 2 de la seua ferramenta d'archivat PKZIP, i va ser més vesprada especificat com RFC 1951.

L'algoritme original, tal i com va ser definit per Katz, va ser protegit baix l'i assignat a PKWARE, Inc. No obstant, i com es detalla en el RFC, deflate es pot implementar de tal forma que no estiga cobert per cap palesa. Açò ha generalisat enormement el seu us, com per eixemple en archius comprimits gzip, archius d'image PNG i l'omnipresent format ZIP, per al qual va ser dissenyat l'algoritme originalment.

Format de l'archiu

Un archiu deflate consistix en una série de blocs. Cada bloc du una capçalera de 3 bits:

• Primer bit: és el que marca si el bloc és l'últim de l'archiu.
  • 1: est és l'últim bloc de l'archiu.
  • 0: hi ha més blocs que processar despuix d'est.
• Segon i tercer bits: són els que determinen la codificació del bloc.
  • 00: una secció almagasenada, en bruto i lliteral, entre 0 i 65535 bytes de llongitut.
  • 01: un bloc Huffman estàtic comprimit, usant un arbre de Huffman definit de bestreta.
  • 10: un bloc comprimit completat en la taula de Huffman donada.
  • 11: reservat, no està en us.

La major part dels blocs es codifica usant 10, la codificació Huffman dinàmic, que produïx un arbre de Huffman optimisat i adaptat a cada bloc de senyes de forma individual. Les instruccions per a generar l'arbre de Huffman apareixen immediatament despuix del bloc de la capçalera.

La compressió es porta a terme en dos passos:

• Busca de cadenes de bits duplicades, les quals es reemplacen en busques.
• Tongada de símbols en atres nous basats en la freqüència d'us.