Deflación (algoritmo)

En informática, el algoritmo deflación, en inglés denominado DEFLATE, es un algoritmo de compresión de datos sin pérdidas que usa una combinación del algoritmo LZ77 y la codificación Huffman. Fue originalmente definido por Phil Katz para la versión 2 de su herramienta de archivado PKZIP, y fue más tarde especificado como RFC 1951.

El algoritmo original, tal y como fue definido por Katz, fue protegido bajo la y asignado a PKWARE, Inc.[1] Sin embargo, y como se detalla en el RFC, deflate se puede implementar de tal forma que no esté cubierto por ninguna patente. Esto ha generalizado enormemente su uso, como por ejemplo en archivos comprimidos gzip, archivos de imagen PNG y el omnipresente formato ZIP, para el cual fue diseñado el algoritmo originalmente.

Formato del archivo

Un archivo deflate consiste en una serie de bloques. Cada bloque lleva una cabecera de 3 bits:

  • Primer bit: es el que marca si el bloque es el último del archivo.
    • 1: este es el último bloque del archivo.
    • 0: hay más bloques que procesar después de este.
  • Segundo y tercer bits: son los que determinan la codificación del bloque.
    • 00: una sección almacenada, en bruto y literal, entre 0 y 65535 bytes de longitud.
    • 01: un bloque Huffman estático comprimido, usando un árbol de Huffman definido de antemano.
    • 10: un bloque comprimido completado con la tabla de Huffman dada.
    • 11: reservado, no está en uso.

La mayor parte de los bloques se codifica usando 10, la codificación Huffman dinámico, que produce un árbol de Huffman optimizado y adaptado a cada bloque de datos de forma individual. Las instrucciones para generar el árbol de Huffman aparecen inmediatamente después del bloque de la cabecera.

La compresión se lleva a cabo en dos pasos:

  • Búsqueda de cadenas de bits duplicadas, las cuales se reemplazan con punteros.
  • Reemplazo de símbolos con otros nuevos basados en la frecuencia de uso.

Referencias
  1. David, Salomon (2007). Data Compression: The Complete Reference (4 edición). Springer. p. 241. ISBN 978-1-84628-602-5.

Enlaces externos
Este artículo ha sido escrito por Wikipedia. El texto está disponible bajo la licencia Creative Commons - Atribución - CompartirIgual. Pueden aplicarse cláusulas adicionales a los archivos multimedia.