Deflación (algoritmo)

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

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.[1]

El algoritmo original, tal y como fue definido por Katz, fue protegido bajo la Patente USPTO nº 5051745 y asignado a PKWARE, Inc.[2] [3] Sin embargo, y como se detalla en el RFC, deflate se puede implementar de tal forma que no esté cubierto por ninguna patente.[1] 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[editar]

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.

Enlaces externos[editar]

Referencias[editar]

  1. a b Plantilla:Cite IETF
  2. Plantilla:Cite patent
  3. David, Salomon (2007). Data Compression: The Complete Reference (4 edición). Springer. p. 241. ISBN 978-1-84628-602-5.