Desinflar

Algoritmo de compresión de datos

En informática , Deflate (estilizado como DEFLATE y también llamado Flate ^{[1] [2]} ) es un formato de archivo de compresión de datos sin pérdida que utiliza una combinación de codificación LZ77 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). ^[3]

Katz también diseñó el algoritmo original utilizado para construir los flujos Deflate. Este algoritmo fue patentado como patente estadounidense 5.051.745 y asignado a PKWARE, Inc. ^{[4] [5]} Como se indica en el documento RFC, se pensaba ampliamente que un algoritmo que produjera archivos Deflate se podía implementar de una manera no cubierta por las patentes. ^[3] 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

Un flujo de Deflate consta de una serie de bloques. Cada bloque está precedido por un encabezado de 3 bits :

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

La opción de bloque almacenado agrega una sobrecarga mínima y se utiliza para datos que no se pueden comprimir.

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

La compresión se consigue mediante dos pasos:

• La correspondencia y reemplazo de cadenas duplicadas con punteros.
• Reemplazar símbolos por símbolos nuevos y ponderados según la frecuencia de uso.

Eliminación de cadenas duplicadas

Dentro de los bloques comprimidos, si se detecta una serie duplicada de bytes (una cadena repetida), se inserta una referencia inversa que enlaza con 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 realizar referencias inversas relativas a lo largo de cualquier número de bloques, siempre que la distancia aparezca dentro de los últimos 32  KiB de datos sin comprimir decodificados (denominados 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 serie de 10 bytes idénticos se puede codificar como un byte, seguido de un duplicado de longitud 9, comenzando con el byte anterior.

La búsqueda de subcadenas duplicadas en el texto anterior es la parte computacionalmente más costosa del algoritmo DEFLATE y la operación a la que afectan las configuraciones del nivel de compresión.

Reducción de bits

La segunda etapa de compresión consiste en reemplazar los símbolos comúnmente utilizados por representaciones más cortas y los símbolos menos utilizados por representaciones más largas. El método utilizado es la codificación de Huffman , que crea un árbol sin prefijo de intervalos no superpuestos, donde la longitud de cada secuencia es inversamente proporcional al logaritmo de la probabilidad de que ese símbolo deba ser codificado. Cuanto más probable sea que un símbolo deba ser codificado, 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 – detiene el procesamiento si es el último bloque, de lo contrario comienza a procesar el siguiente bloque.
• 257–285: combinado con bits adicionales, una longitud de coincidencia de 3 a 258 bytes.
• 286, 287: no utilizado, reservado e ilegal pero aún así parte del árbol.

Un código de longitud de coincidencia siempre estará seguido de un código de distancia. Según el código de distancia leído, se pueden leer más bits "extra" para generar la distancia final. El árbol de distancia 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 aún así forma parte del árbol.

Tenga en cuenta que para los símbolos de distancia de coincidencia 2 a 29, la cantidad de bits adicionales se puede calcular como . ${\displaystyle \left\lfloor {\frac {n}{2}}\right\rfloor -1}$

Los dos códigos (el árbol literal/de longitud de 288 símbolos y el árbol de distancia de 32 símbolos) se codifican como códigos Huffman canónicos , dando la longitud en bits del código para cada símbolo. Las longitudes en bits se codifican 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 en árbol, la opción "árbol estático" proporciona árboles Huffman fijos estándar. El tamaño comprimido utilizando los árboles estáticos se puede calcular utilizando las mismas estadísticas (la cantidad 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.

Codificador/compresor

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 entre una escala móvil de probable nivel de compresión resultante frente a velocidad de codificación. Las opciones varían desde 0(no intentar la compresión, solo 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. Es probable que las diferentes implementaciones produzcan variaciones en el flujo de bits codificado final producido. El objetivo de las versiones no zlib de un codificador ha sido normalmente producir un flujo codificado más pequeño y comprimido de manera más eficiente.

Deflate64/Desinflado mejorado

Deflate64, especificado por PKWARE, es una variante propietaria 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 extiende a 16 bits para que pueda definir longitudes de tres a 65.538 bytes. ^[6] Esto hace que Deflate64 tenga un tiempo de compresión más largo, y potencialmente una relación de compresión ligeramente superior, que Deflate. ^[7] Varios proyectos libres y/o de código abierto admiten Deflate64, como 7-Zip , ^[8] mientras que otros, como zlib , no lo hacen, como resultado de la naturaleza propietaria del procedimiento ^[9] y el aumento de rendimiento muy modesto sobre Deflate. ^[10]

Uso de Deflate en un nuevo software

Las implementaciones de Deflate están disponibles de forma gratuita en muchos lenguajes. Las aplicaciones escritas en C suelen utilizar la biblioteca zlib (bajo la licencia zlib License ). Las aplicaciones en Borland Pascal (y lenguajes compatibles) pueden utilizar paszlib. Las aplicaciones en C++ pueden aprovechar la biblioteca Deflate mejorada en 7-Zip . Tanto Java como .NET Framework ofrecen compatibilidad inmediata con Deflate en sus bibliotecas (respectivamente, java.util.zipy System.IO.Compression). Las aplicaciones en Ada pueden utilizar Zip-Ada (puro) o ZLib-Ada.

Implementaciones de codificadores

• PKZIP : la primera implementación, realizada originalmente por Phil Katz como parte de PKZip
• zlib : implementación de referencia estándar adoptada en muchas aplicaciones debido a su licencia permisiva de código abierto. Consulte Zlib § Forks para obtener información sobre bifurcaciones de mayor rendimiento.
• Crypto++ : contiene una implementación de dominio público en C++ destinada a reducir posibles vulnerabilidades de seguridad . El autor, Wei Dai, afirma: " Este código es menos inteligente, pero esperamos que sea más comprensible y fácil de mantener [que zlib] ".
• 7-Zip : escrito por Igor Pavlov en C++ , esta versión tiene licencia libre y logra una mayor compresión que zlib a expensas del uso de CPU. Tiene una opción para usar el formato de almacenamiento DEFLATE64.
• PuTTY 'sshzlib.c': una implementación independiente bajo la licencia MIT de Simon Tatham, tiene capacidad de decodificación completa, pero solo admite la creación de árboles estáticos
• libflate: ^[11] parte de Plan 9 de Bell Labs , implementa compresión deflate
• Hyperbac : utiliza su propia biblioteca de compresión patentada (en C++ y Assembly) con una opción para implementar el formato de almacenamiento DEFLATE64
• Zopfli : implementación en C bajo la licencia Apache de Google ; logra una mayor compresión a expensas del uso de la CPU. ZopfliPNG es una variación de Zopfli para usar con archivos PNG .
• igzip: un codificador escrito en lenguaje ensamblador x86 , publicado por Intel bajo la licencia MIT . Es tres veces más rápido que zlib -1. Es útil para comprimir datos genómicos. ^[12]
• libdeflate: ^[13] una biblioteca para compresión y descompresión rápidas de todo el búfer con DEFLATE. Libdeflate está altamente optimizada, especialmente para procesadores x86.

AdvanceCOMP utiliza las versiones de Deflate con mayor relación de compresión en 7-Zip, libdeflate y Zopfli para permitir la recompresión de archivos gzip , PNG , MNG y ZIP con la posibilidad de tamaños de archivo más pequeños que los que zlib puede lograr con las configuraciones máximas. ^[14]

Codificadores de hardware

• AHA361-PCIX/AHA362-PCIX de Comtech AHA Archivado el 8 de diciembre de 2006 en Wayback Machine . Comtech produjo una tarjeta PCI-X193f:0001 (PCI-ID: ) capaz de comprimir flujos utilizando Deflate a una velocidad de hasta 3,0 Gbit/s (375 MB/s) para datos entrantes sin comprimir. Junto con el controlador del núcleo Linux para AHA361-PCIX hay una utilidad " " y una " " personalizada capaz de utilizar la compresión de hardware de Apache . El hardware se basa en un FPGA Xilinx Virtex y cuatro ASIC AHA3601 personalizados . 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 soportar la especificación Deflate completa, lo que significa que solo podían decodificar de manera confiable su propia salida (un flujo que no contenía ningún bloque Huffman dinámico tipo 2).ahagzipmod_deflate_aha
• StorCompress 300/MX3 de Indra Networks. Se trata de una gama de tarjetas PCI (PCI-ID: 17b4:0011) o PCI-X que incorporan entre uno y seis motores de compresión con velocidades de procesamiento declaradas de hasta 3,6 Gbit/s (450 MB/s). Existe una versión de las tarjetas con la marca independiente WebEnhance diseñada específicamente para su uso en servidores web en lugar de SAN o backup; también se fabrica una revisión PCIe , la 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 mantener una velocidad de 2,5 Gbit/s. Usando dos de estos chips, la placa AHA363-PCIe puede procesar Deflate a una velocidad de hasta 5,0 Gbit/s (625 MB/s) usando 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 cambio, tiene múltiples conjuntos de registros para permitir 32 canales de compresión virtuales independientes que alimentan dos motores de compresión físicos. Los controladores de dispositivos del kernel de Linux, Microsoft Windows y OpenSolaris están disponibles para ambas nuevas tarjetas, junto con una biblioteca de 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 utiliza cuatro chips AHA3610 para una tasa de compresión sostenida de 10 Gbit/s (1250 MB/s). A diferencia de la AHA362-PCIX, los motores de descompresión de las placas AHA363-PCIe y AHA367-PCIe son totalmente compatibles con deflate.
• Los procesadores Nitrox y Octeon ^{[ enlace muerto permanente ]} de Cavium, Inc. contienen motores de inflado y desinflado de hardware de alta velocidad compatibles con ZLIB y GZIP y algunos dispositivos pueden manejar múltiples flujos de datos simultáneos.
• Implementación de FPGA GPL HDL-Deflate.
• ZipAccel-C de CAST Inc. Es un núcleo de silicio IP compatible con compresión Deflate, Zlib y Gzip . ZipAccel-C se puede implementar en ASIC o FPGA , admite tablas Huffman tanto dinámicas como estáticas y puede proporcionar rendimientos superiores a 100 Gbps. La empresa 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 los procesadores Intel Xeon de las series E5-2600 y E5-2400 (Sandy Bridge-EP/EN) admite la compresión y descompresión de hardware mediante la tecnología QuickAssist. Según el chipset, están disponibles velocidades de compresión y descompresión de 5 Gbit/s, 10 Gbit/s o 20 Gbit/s. ^[15]
• Las CPU IBM z15 incorporan una versión mejorada de la aceleración de hardware Nest Accelerator Unit (NXU) de las tarjetas de expansión zEDC Express I/O utilizadas en sistemas z14 para la compresión y descompresión de hardware Deflate según lo especificado por RFC1951. ^{[16] [17]}
• A partir de la arquitectura POWER9 , IBM agregó soporte de hardware para comprimir y descomprimir Deflate (como se especifica en RFC 1951) al núcleo acelerador Nest (NX) criptocéntrico introducido con POWER7+ . Este soporte está disponible para programas que se ejecutan con AIX 7.2 Technology Level 4 Expansion Pack o AIX 7.2 Technology Level 5 Service Pack 2 a través de la biblioteca zlibNX. ^{[18] [19]}

Descodificador/descompresor

Inflar es el proceso de decodificación que toma un flujo de bits de Deflate para descomprimirlo y produce correctamente los datos o el archivo original en tamaño completo.

Implementaciones de solo inflación

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.

• Asamblea
  • 6502 inflar, 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 el 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 , escrita por Keir Fraser y lanzada al dominio público .

• C / C++
  • kunzip de Michael Kohn y no relacionado con "KZIP". Viene con código fuente en C bajo la licencia GNU LGPL . Se utiliza en el instalador de GIMP .
  • puff.c ( zlib ), una implementación de referencia de archivo único, pequeña y sin restricciones, 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 alrededor de 2k de código.
  • tinfl.c (miniz), implementación de Inflate de dominio público contenida completamente en una sola función C.
• PCDEZIP, Bob Flanders y Michael Holmes, publicado en PC Magazine el 11 de enero de 1994.
• inflate.cl de John Foderaro. Decodificador autónomo de Common Lisp distribuido con licencia GNU LGPL .
• inflate.s7i/gzip.s7i, una implementación pura de Seed7 de Deflate y descompresión gzip, por Thomas Mertes. Disponible bajo la licencia GNU LGPL .
• pyflate, un decodificador independiente de Deflate ( gzip ) y bzip2 basado en Python, creado por Paul Sladen. Escrito para investigación y creación de prototipos y disponible bajo las licencias BSD / GPL / LGPL / DFSG .
• deflatelua, una implementación puramente Lua de Deflate y descompresión gzip /zlib, por David Manura.
• Inflate es una implementación puramente Javascript de Inflate por Chris Dickinson
• pako: puerto de zlib optimizado para la velocidad de JavaScript. Contiene compilación independiente con inflado únicamente.

Decodificadores de hardware

• GPU Inflate en serie de BitSim. Implementación de hardware de Inflate. Parte de la oferta de controladores BADGE (Bitsim Accelerated Display Graphics Engine) de BitSim para sistemas integrados.
• Implementación de FPGA GPL HDL-Deflate.
• ZipAccel-D de CAST Inc. Se trata de un núcleo IP de silicio que admite la descompresión de archivos Deflate, Zlib y Gzip . El núcleo IP ZipAccel-D se puede implementar en ASIC o FPGA. La empresa ofrece diseños de referencia de placas aceleradoras de compresión/descompresión para FPGA de Intel (ZipAccel-RD-INT) y FPGA de Xilinx (ZipAccel-RD-XIL).
• Las CPU IBM z15 incorporan una versión mejorada de la aceleración de hardware Nest Accelerator Unit (NXU) de las tarjetas de expansión zEDC Express I/O utilizadas en sistemas z14 para la compresión y descompresión de hardware Deflate según lo especificado por RFC1951. ^{[16] [17]}
• A partir de la arquitectura POWER9 , IBM agregó soporte de hardware para comprimir y descomprimir Deflate (como se especifica en RFC 1951) al núcleo acelerador Nest (NX) criptocéntrico introducido con POWER7+ . Este soporte está disponible para programas que se ejecutan con AIX 7.2 Technology Level 4 Expansion Pack o AIX 7.2 Technology Level 5 Service Pack 2 a través de la biblioteca zlibNX. ^{[18] [19]}

Véase también

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

Referencias

1. Los autores de Go. "paquete flate - compress/flate - Paquetes Go". El lenguaje de programación Go . Google . Consultado el 5 de septiembre de 2023 . El paquete flate implementa el formato de datos comprimidos DEFLATE, descrito en la RFC número 1951.
2. Adobe Systems Incorporated . «PDF 32000-1:2008: Document management — Portable document format — Part 1: PDF 1.7» (PDF) . Adobe Open Source . Adobe. pág. 23. Consultado el 5 de septiembre de 2023. FlateDecode [...] Descomprime datos codificados con el método de compresión zlib/deflate .
3. Deutsch, L. Peter (mayo de 1996). DEFLATE Compressed Data Format Specification versión 1.3. IETF . pág. 1. seg. Resumen. doi : 10.17487/RFC1951 . RFC 1951 . Consultado el 23 de abril de 2014 .
4. Patente estadounidense 5051745, Katz, Phillip W. , "Buscador de cadenas y compresor que lo utiliza", publicada el 24 de septiembre de 1991, expedida el 24 de septiembre de 1991, asignada a PKWare Inc. 
5. David, Salomon (2007). Compresión de datos: la referencia completa (4.ª ed.). Springer. pág. 241. ISBN 978-1-84628-602-5.
6. "Binary Essence – Deflate64". Archivado desde el original el 21 de junio de 2017. Consultado el 22 de mayo de 2011 .{{cite web}}: CS1 maint: bot: estado de URL original desconocido ( enlace )
7. "Binary Essence – Comparaciones de compresión del "Corpus de Calgary"". Archivado desde el original el 27 de diciembre de 2017. Consultado el 22 de mayo de 2011 .{{cite web}}: CS1 maint: bot: estado de URL original desconocido ( enlace )
8. "Conmutador -m (Establecer método de compresión)". sevenzip.osdn.jp . Archivado desde el original el 2022-04-09 . Consultado el 2023-01-21 .
9. Historia de los algoritmos de compresión de datos sin pérdida – Deflate64
10. Preguntas frecuentes de zlib: ¿zlib admite el nuevo formato "Deflate64" introducido por PKWare?
11. "Plan 9 de /n/sources/plan9/sys/src/libflate de Bell Labs". plan9.bell-labs.com . Lucent Technologies. Archivado desde el original el 15 de marzo de 2006.
12. "Compresión DEFLATE de alto rendimiento con optimizaciones para conjuntos de datos genómicos". Intel Software . 1 de octubre de 2019 . Consultado el 18 de enero de 2020 .
13. "libdeflate". Biblioteca altamente optimizada para compresión y descompresión DEFLATE/zlib/gzip .
14. Mazzoleni, Andrea (21 de febrero de 2023). "amadvance/advancecomp". GitHub .
15. "Procesador Intel® Xeon® serie E5-2600 y E5-2400 con chipset de comunicaciones Intel® serie 89xx" . Consultado el 18 de mayo de 2016 .
16. "Presentación de IBM z15: la plataforma empresarial para multicloud híbrido de misión crítica". IBM . 12 de septiembre de 2019 . Consultado el 1 de noviembre de 2021 .
17. Lascu, Octavian (28 de abril de 2021). Guía técnica de IBM z15 (8562), página 97. IBM Redbooks. ISBN 9780738458991. Recuperado el 1 de noviembre de 2021 .
18. "Compresión de datos mediante la biblioteca zlibNX - Documentación de IBM". IBM . Consultado el 1 de noviembre de 2021 .
19. "Explotación de la aceleración en el núcleo de los procesadores POWER para AIX" . Consultado el 1 de noviembre de 2021 .

Enlaces externos

• Especificación del formato de archivo .ZIP de PKWARE, Inc.appnote.txt Archivado el 5 de diciembre de 2014 en Wayback Machine ; Sección 10, X. Desinflado – Método 8 .
• RFC 1951 – Especificación del formato de datos comprimidos Deflate versión 1.3
• Página de inicio de zlib
• Una explicación del algoritmo Deflate – por Antaeus Feldspar
• Aplicación extendida de árboles de sufijos a la compresión de datos Archivado el 23 de septiembre de 2016 en Wayback Machine : un excelente algoritmo para implementar Deflate por Jesper Larsson
• Archivos Zip: Historia, explicación e implementación: recorrido por la implementación de Deflate