De Wikipedia, la enciclopedia libre
  (Redirigido desde DEFLATE )
Saltar a navegación Saltar a búsqueda
Este artículo trata sobre el algoritmo de compresión de datos. Para otros usos, consulte Deflación (desambiguación) .

En informática , Deflate es un formato de archivo de compresión de datos sin pérdidas que utiliza una combinación de codificación LZSS y Huffman . Fue diseñado por Phil Katz , para la versión 2 de su herramienta de archivo PKZIP . Deflate se especificó más tarde en RFC 1951 (1996). [1]

Katz también diseñó el algoritmo original utilizado para construir flujos de deflación. Este algoritmo fue patentado como Patente de los Estados Unidos 5.051.745 y asignado a PKWARE, Inc. [2] [3] Como se indica en el documento RFC, se pensaba que un algoritmo que producía archivos Deflate podía implementarse de una manera no cubierta por patentes. [1] Esto llevó a su uso generalizado, por ejemplo, en archivos comprimidos gzip y archivos de imagen PNG , además del formato de archivo ZIP para el que Katz lo diseñó originalmente. Desde entonces, la patente ha expirado.

Formato de transmisión [ editar ]

Una corriente de desinflado consta de una serie de bloques. Cada bloque está precedido por un encabezado de 3 bits :

  • Primer bit: marcador de último bloque en flujo:
    • 1: Este es el último bloque de la secuencia.
    • 0: Hay más bloques para procesar después de este.
  • Segundo y tercer bits: método de codificación utilizado para este tipo de bloque:
    • 00: Una sección almacenada (también conocida como sin formato o literal), entre 0 y 65.535 bytes de longitud
    • 01: Un bloque comprimido estático de Huffman , que utiliza un árbol de Huffman acordado previamente definido en el RFC
    • 10: Un bloque comprimido completo con la mesa Huffman suministrada
    • 11: Reservado, no lo use.

La opción de bloque almacenado agrega una sobrecarga mínima y se usa para datos que son incompresibles.

La mayoría de los datos comprimibles terminarán siendo codificados usando el método 10, la codificación dinámica de Huffman , que produce un árbol de Huffman optimizado personalizado para cada bloque de datos individualmente. Las instrucciones para generar el árbol de Huffman necesario siguen inmediatamente al encabezado del bloque. La opción estática de Huffman se usa para mensajes cortos, donde el ahorro fijo obtenido al omitir el árbol supera el porcentaje de pérdida de compresión debido al uso de un código no óptimo (por lo tanto, técnicamente no es Huffman).

La compresión se logra mediante dos pasos:

  • La coincidencia y sustitución de cadenas duplicadas con punteros.
  • Reemplazo de símbolos con nuevos símbolos ponderados según la frecuencia de uso.

Reducción de bits [ editar ]

Artículo principal: codificación de Huffman

La segunda etapa de compresión consiste en reemplazar los símbolos de uso común con representaciones más cortas y los símbolos de uso menos común con representaciones más largas. El método utilizado es la codificación de Huffman, que crea un árbol sin prefijos de intervalos que no se superponen, donde la longitud de cada secuencia es inversamente proporcional al logaritmo de la probabilidad de que ese símbolo necesite ser codificado. Cuanto más probable sea que un símbolo tenga que codificarse, más corta será su secuencia de bits.

Se crea un árbol que contiene espacio para 288 símbolos:

  • 0-255: representa los bytes / símbolos literales 0-255.
  • 256: fin de bloque: detener el procesamiento si es el último bloque; de ​​lo contrario, comenzar a procesar el siguiente bloque
  • 257–285: combinado con bits adicionales, una longitud de coincidencia de 3–258 bytes.
  • 286, 287: no utilizado, reservado e ilegal, pero sigue siendo parte del árbol.

Un código de longitud de coincidencia siempre irá seguido de un código de distancia. Basándose en el código de distancia leído, se pueden leer más bits "extra" para producir la distancia final. El árbol de distancias contiene espacio para 32 símbolos:

  • 0-3: distancias 1-4
  • 4-5: distancias 5-8, 1 bit extra
  • 6–7: distancias 9–16, 2 bits adicionales
  • 8–9: distancias 17–32, 3 bits adicionales
  • ...
  • 26-27: distancias 8.193-16.384, 12 bits adicionales
  • 28-29: distancias 16.385-32.768, 13 bits adicionales
  • 30–31: no utilizado, reservado e ilegal, pero sigue siendo parte del árbol.

Tenga en cuenta que para los símbolos de distancia de coincidencia 2–29, el número de bits adicionales se puede calcular como .

Los dos códigos (el árbol de longitud / literal de 288 símbolos y el árbol de distancia de 32 símbolos) se codifican en sí mismos como códigos de Huffman canónicos dando la longitud de bits del código para cada símbolo. Las longitudes de bits están codificadas en longitud de ejecución para producir una representación lo más compacta posible. Como alternativa a la inclusión de la representación del árbol, la opción "árbol estático" proporciona árboles de Huffman fijos estándar. El tamaño comprimido utilizando los árboles estáticos se puede calcular utilizando las mismas estadísticas (el número de veces que aparece cada símbolo) que se utilizan para generar los árboles dinámicos, por lo que es fácil para un compresor elegir el que sea más pequeño.

Eliminación de cadenas duplicadas [ editar ]

Artículos principales: LZ77 y LZ78 y LZSS

Dentro de los bloques comprimidos, si se detecta una serie duplicada de bytes (una cadena repetida), se inserta una referencia inversa, enlazándose a la ubicación anterior de esa cadena idéntica. Una coincidencia codificada con una cadena anterior consta de una longitud de 8 bits (3–258 bytes) y una distancia de 15 bits (1–32,768 bytes) hasta el comienzo del duplicado. Se pueden hacer referencias hacia atrás relativas en cualquier número de bloques, siempre que la distancia aparezca dentro de los últimos 32  KiB de datos descodificados sin comprimir (denominada ventana deslizante ).

Si la distancia es menor que la longitud, el duplicado se superpone a sí mismo, lo que indica repetición. Por ejemplo, una ejecución de 10 bytes idénticos se puede codificar como un byte, seguido de un duplicado de longitud 9, comenzando con el byte anterior.

Buscar en el texto anterior subcadenas duplicadas es la parte más costosa desde el punto de vista computacional del algoritmo DEFLATE, y la operación a la que afectan los ajustes del nivel de compresión.

Codificador / compresor [ editar ]

Durante la etapa de compresión, es el codificador el que elige la cantidad de tiempo que se dedica a buscar cadenas coincidentes. La implementación de referencia zlib / gzip permite al usuario seleccionar de una escala móvil el nivel de compresión resultante frente a la velocidad de codificación. Las opciones van desde 0(no intentar la compresión, simplemente almacenar sin comprimir) hasta 9representar la capacidad máxima de la implementación de referencia en zlib / gzip.

Se han producido otros codificadores Deflate, todos los cuales también producirán un flujo de bits compatible capaz de ser descomprimido por cualquier decodificador Deflate existente. Las diferentes implementaciones probablemente producirán variaciones en el tren de bits codificado final producido. El enfoque de las versiones no zlib de un codificador normalmente ha sido producir una secuencia codificada más pequeña y comprimida de manera más eficiente.

Deflate64 / Deflate mejorado [ editar ]

Deflate64, especificado por PKWARE, es una variante patentada de Deflate. Es fundamentalmente el mismo algoritmo. Lo que ha cambiado es el aumento del tamaño del diccionario de 32 KB a 64 KB, una extensión de los códigos de distancia a 16 bits para que puedan abordar un rango de 64 KB, y el código de longitud, que se amplía a 16 bits para que puede definir longitudes de tres a 65.538 bytes. [4] Esto lleva a que Deflate64 tenga un tiempo de compresión más largo y, potencialmente, una relación de compresión ligeramente más alta que Deflate. [5] Varios proyectos gratuitos y / o de código abierto admiten Deflate64, como 7-Zip , [6] mientras que otros, como zlib , no lo hacen, debido a la naturaleza patentada del procedimiento [7]y el muy modesto aumento de rendimiento sobre Deflate. [8]

Uso de Deflate en un nuevo software [ editar ]

Las implementaciones de Deflate están disponibles gratuitamente en muchos idiomas. Los programas C suelen utilizar la biblioteca zlib (con licencia de zlib License , que permite su uso con software gratuito y propietario). Los programas escritos usando los dialectos Borland de Pascal pueden usar paszlib; se incluye una biblioteca C ++ como parte de 7-Zip / AdvanceCOMP . Java incluye soporte como parte de la biblioteca estándar (en java.util.zip). La biblioteca de clases base de Microsoft .NET Framework 2.0 la admite en el espacio de nombres System.IO.Compression . Los programas en Ada pueden usar Zip-Ada (puro) o el enlace grueso ZLib-Ada a zlib.

Implementaciones de codificadores [ editar ]

  • PKZIP : la primera implementación, originalmente realizada por Phil Katz como parte de PKZip .
  • zlib / gzip : implementación de referencia estándar utilizada en una gran cantidad de software, debido a la disponibilidad pública del código fuente y una licencia que permite la inclusión en otro software.
  • Crypto ++ : contiene una implementación de dominio público en C ++ destinada principalmente a reducir las posibles vulnerabilidades de seguridad . El autor, Wei Dai, afirma " Este código es menos inteligente, pero es de esperar que sea más comprensible y fácil de mantener [que zlib] ".
  • 7-Zip / AdvanceCOMP : escrito por Igor Pavlov en C ++ , esta versión tiene licencia gratuita y tiende a lograr una compresión más alta que zlib a expensas del uso de la CPU. Tiene una opción para usar el formato de almacenamiento DEFLATE64.
  • PuTTY 'sshzlib.c': una implementación independiente, capaz de decodificación completa, pero creación de árbol estático, por Simon Tatham. Con licencia del MIT .
  • El plan 9 de libflate del sistema operativo Bell Labs implementa la compresión deflate.
  • Hyperbac : utiliza su propia biblioteca de compresión sin pérdidas (escrita en C ++ y Ensamblador) con una opción para implementar el formato de almacenamiento DEFLATE64.
  • Zopfli : implementación de C de Google que logra la máxima compresión a expensas del uso de la CPU. ZopfliPNG es una variación de Zopfli para su uso con PNG . Apache con licencia .
  • igzip, un codificador escrito en ensamblaje x86 lanzado por Intel bajo la licencia MIT. 3 veces más rápido que zlib -1. Útil para comprimir datos genómicos. [9]

AdvanceCOMP utiliza la versión de relación de compresión más alta de Deflate implementada por 7-Zip (u opcionalmente Zopfli en versiones recientes) para permitir la recompresión de archivos gzip , PNG , MNG y ZIP con la posibilidad de lograr tamaños de archivo más pequeños que los que zlib puede lograr al máximo. ajustes.

Codificadores de hardware [ editar ]

  • AHA361-PCIX / AHA362-PCIX de Comtech AHA . Comtech produjo una tarjeta PCI-X (PCI-ID 193f:0001:) capaz de comprimir flujos usando Deflate a una velocidad de hasta 3.0 Gbit / s (375 MB / s) para datos entrantes sin comprimir. Junto al controlador del kernel de Linux para el AHA361-PCIX hay una " " utilidad y personalizada " " capaz de utilizar la compresión de hardware de Apache . El hardware se basa en un FPGA Xilinx Virtex y cuatro ASIC AHA3601 personalizadosahagzipmod_deflate_aha . Las placas AHA361 / AHA362 están limitadas a manejar solo bloques Huffman estáticos y requieren que se modifique el software para agregar soporte; las tarjetas no podían admitir la especificación Deflate completa, lo que significa que solo podían decodificar de manera confiable su propia salida (una secuencia que no lo hizo) contener cualquier bloque dinámico de Huffman tipo 2).
  • StorCompress 300 / MX3 de Indra Networks . Esta es una gama de tarjetas PCI (PCI-ID 17b4:0011:) o PCI-X con entre uno y seis motores de compresión con velocidades de procesamiento declaradas de hasta 3.6 Gbit / s (450 MB / s). Una versión de las tarjetas está disponible con la marca separada WebEnhance diseñada específicamente para uso de servicio web en lugar de SAN o uso de respaldo; una revisión PCIe , también se produce el MX4E .
  • AHA363-PCIe / AHA364-PCIe / AHA367-PCIe . En 2008, Comtech comenzó a producir dos tarjetas PCIe ( PCI-ID: 193f:0363/ 193f:0364) con un nuevo chip codificador de hardware AHA3610. El nuevo chip fue diseñado para ser capaz de alcanzar una velocidad sostenida de 2,5 Gbit / s. Con dos de estos chips, la placa AHA363-PCIe puede procesar Deflate a una velocidad de hasta 5,0 Gbit / s (625 MB / s) utilizando los dos canales (dos de compresión y dos de descompresión). La variante AHA364-PCIe es una versión de solo codificación de la tarjeta diseñada para balanceadores de carga salientes y en su lugar tiene múltiples conjuntos de registros para permitir 32 canales de compresión virtuales independientes que alimentan dos motores de compresión físicos. Linux, Microsoft Windows y OpenSolarisLos controladores de dispositivo del kernel están disponibles para ambas tarjetas nuevas, junto con una biblioteca del sistema zlib modificada para que las aplicaciones vinculadas dinámicamente puedan usar automáticamente el soporte de hardware sin modificaciones internas. La placa AHA367-PCIe ( PCI-ID: 193f:0367) es similar a la AHA363-PCIe pero usa cuatro chips AHA3610 para una tasa de compresión sostenida de 10 Gbit / s (1250 MB / s). A diferencia del AHA362-PCIX, los motores de descompresión de las placas AHA363-PCIe y AHA367-PCIe son totalmente compatibles con desinflado.
  • Los procesadores Nitrox y Octeon [ enlace muerto permanente ] de Cavium, Inc. contienen motores de desinflado e inflado de hardware de alta velocidad compatibles con ZLIB y GZIP con algunos dispositivos capaces de manejar múltiples flujos de datos simultáneos.
  • Implementación HDL-Deflate GPL FPGA.
  • ZipAccel-C de REPARTO Inc . Este es un núcleo IP de silicio que admite la compresión Delfate, Zlib y Gzip . ZipAccel-C se puede implementar en ASIC o FPGA , admite tablas Huffman dinámicas y estáticas y puede proporcionar rendimientos superiores a 100 Gbps. La compañía ofrece diseños de referencia de placas aceleradoras de compresión / descompresión para FPGA Intel ( ZipAccel-RD-INT ) y FPGA Xilinx ( ZipAccel-RD-XIL ).
  • El chipset de comunicaciones Intel serie 89xx (Cave Creek) para las series de procesadores Intel Xeon E5-2600 y E5-2400 (Sandy Bridge-EP / EN) admite la compresión y descompresión de hardware mediante la tecnología QuickAssist. Dependiendo del conjunto de chips, están disponibles tasas de compresión y descompresión de 5 Gbit / s, 10 Gbit / so 20 Gbit / s. [10]

Decodificador / descompresor [ editar ]

Inflar es el proceso de decodificación que toma un flujo de bits Deflate para la descompresión y produce correctamente los datos o archivos originales de tamaño completo.

Implementaciones de solo inflar [ editar ]

La intención normal con una implementación alternativa de Inflate es una velocidad de decodificación altamente optimizada o un uso de RAM extremadamente predecible para sistemas integrados con microcontroladores.

  • Montaje
    • 6502 inflate , escrito por Piotr Fusik en lenguaje ensamblador 6502 .
    • SAMflate , escrito por Andrew Collier en lenguaje ensamblador Z80 con soporte de paginación de memoria opcional para SAM Coupé , y disponible bajo las licencias BSD / GPL / LGPL / DFSG .
    • gunzip , escrito por Laurens Holst en lenguaje ensamblador Z80 para MSX , con licencia BSD .
    • inflate.asm , una implementación rápida y eficiente en lenguaje de máquina M68000 , escrito por Keir Fraser y lanzado al dominio público .
  • C / C ++
    • kunzip de Michael Kohn y no relacionado con "KZIP". Viene con código fuente C bajo la licencia GNU LGPL . Usado en el instalador de GIMP .
    • puff.c ( zlib ), una implementación de referencia de archivo único, pequeña y sin trabas incluida en el directorio / contrib / puff de la distribución zlib.
    • tinf escrito por Jørgen Ibsen en ANSI C y viene con licencia zlib. Agrega aproximadamente 2k de código.
    • tinfl.c ( miniz ), Implementación de Inflar de dominio público contenida por completo en una única función de C.
  • PCDEZIP, Bob Flanders y Michael Holmes, publicado en PC Magazine 1994-01-11.
  • inflate.cl de John Foderaro. Decodificador Common Lisp autónomo distribuido con licencia GNU LGPL .
  • inflate.s7i / gzip.s7i , un puro- Seed7 implementación de desinflado y descompresión gzip, por Thomas Mertes. Disponible bajo la licencia GNU LGPL .
  • pyflate , un decodificador independiente de Python puro Deflate ( gzip ) y bzip2 de Paul Sladen. Escrito para investigación / creación de prototipos y disponible bajo las licencias BSD / GPL / LGPL / DFSG .
  • deflatelua , una implementación pura de Lua de Deflate y descompresión gzip / zlib, por David Manura.
  • inflar una implementación de Javascript puro de Inflate por Chris Dickinson
  • pako : puerto JavaScript optimizado para la velocidad de zlib. Contiene compilación separada con solo inflar.

Decodificadores de hardware [ editar ]

  • GPU de inflado en serie de BitSim. Implementación de hardware de Inflate. Parte de la oferta de controlador BADGE (Bitsim Accelerated Display Graphics Engine) de BitSim para sistemas integrados.
  • Implementación HDL-Deflate GPL FPGA.
  • ZipAccel-D a partir REPARTO Inc . Este es un núcleo de IP de silicio que admite la descompresión de archivos Delfate, Zlib y Gzip . El núcleo IP ZipAccel-D que se puede implementar en ASIC o FPGA. La compañía ofrece diseños de referencia de placas aceleradoras de compresión / descompresión para FPGA Intel ( ZipAccel-RD-INT ) y FPGA Xilinx ( ZipAccel-RD-XIL ).

Ver también [ editar ]

  • Lista de formatos de archivo
  • Lista de archivadores de archivos
  • Comparación de archivadores de archivos

Referencias [ editar ]

  1. ↑ a b Deutsch, L. Peter (mayo de 1996). DESINFLAR Especificación de formato de datos comprimidos versión 1.3 . IETF . pag. 1 segundo. Resumen. doi : 10.17487 / RFC1951 . RFC 1951 . Consultado el 23 de abril de 2014 .
  2. ^ Patente de EE. UU . 5051745 , Katz, Phillip W. , "Buscador de cadenas y compresor utilizando el mismo", publicada el 24 de septiembre de 1991, publicada el 24 de septiembre de 1991 
  3. ^ David, Salomon (2007). Compresión de datos: la referencia completa (4 ed.). Saltador. pag. 241. ISBN 978-1-84628-602-5.
  4. ^ "Esencia binaria - Deflate64" . Archivado desde el original el 21 de junio de 2017 . Consultado el 22 de mayo de 2011 .CS1 maint: bot: estado de URL original desconocido ( enlace )
  5. ^ "Binary Essence -" Calgary Corpus "comparaciones de compresión" . Archivado desde el original el 27 de diciembre de 2017 . Consultado el 22 de mayo de 2011 .CS1 maint: bot: estado de URL original desconocido ( enlace )
  6. ^ Manual y documentación de 7-Zip - Método de compresión
  7. ^ Historia de algoritmos de compresión de datos sin pérdida - Deflate64
  8. ^ Preguntas frecuentes sobre zlib: ¿admite zlib el nuevo formato "Deflate64" introducido por PKWare?
  9. ^ "Compresión DEFLATE de alto rendimiento con optimizaciones para conjuntos de datos genómicos" . Software de Intel . 1 de octubre de 2019 . Consultado el 18 de enero de 2020 .
  10. ^ "Procesador Intel® Xeon® serie E5-2600 y E5-2400 con chipset de comunicaciones Intel® serie 89xx" . Consultado el 18 de mayo de 2016 .

Enlaces externos [ editar ]

  • PKWARE, Inc. 's appnote.txt, .ZIP especificación de formato de archivo ; Sección 10, X. Desinflado - Método 8 .
  • RFC 1951 - Deflate Compressed Data Format Specification versión 1.3
  • Página de inicio de zlib
  • Una explicación del algoritmo de desinflado - por Antaeus Feldespato
  • Aplicación ampliada de árboles de sufijos a la compresión de datos : un algoritmo excelente para implementar Deflate de Jesper Larsson
  • Archivos Zip: historial, explicación e implementación : recorrido por una implementación de Deflate