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érdidas 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 . La desinflación se especificó posteriormente en RFC 1951 (1996). ^[3]

Katz también diseñó el algoritmo original utilizado para construir transmisiones 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 producía archivos Deflate se podía implementar de una manera no cubierta por 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

Una secuencia 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 este.
• 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 estático comprimido de Huffman, que utiliza un árbol de Huffman previamente acordado y definido en el RFC.
  • 10: Un bloque dinámico comprimido de Huffman, completo con la mesa Huffman suministrada
  • 11: Reservado: no utilizar.

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 codificados utilizando el método 10, la codificación dinámica de Huffman , que produce un árbol de Huffman optimizado y 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 utiliza 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 Huffman).

La compresión se logra mediante dos pasos:

• La coincidencia y sustitución de cadenas duplicadas con punteros.
• Reemplazar símbolos con 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 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 a 258 bytes) y una distancia de 15 bits (1 a 32 768 bytes) hasta el comienzo del duplicado. Se pueden hacer referencias relativas a cualquier número de bloques, siempre que la distancia aparezca dentro de los últimos 32  KiB de datos sin comprimir decodificados (lo que se denomina ventana deslizante ).

Si la distancia es menor que la longitud, el duplicado se superpone, 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.

Buscar subcadenas duplicadas en el texto anterior 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.

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 que no se superponen, donde la longitud de cada secuencia es inversamente proporcional al logaritmo de la probabilidad de que ese símbolo deba codificarse. Cuanto más probable sea que sea necesario codificar un símbolo, 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 del bloque: detenga el procesamiento si es el último bloque; de ​​lo contrario, comience 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 sigue siendo parte del árbol.

Un código de longitud de coincidencia siempre irá seguido de un código de distancia. Según 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 a 29, el número de bits adicionales se puede calcular como . ${\displaystyle \left\lfloor {\frac {n}{2}}\right\rfloor -1}$

Los dos códigos (el árbol literal/longitud de 288 símbolos y el árbol de distancia de 32 símbolos) están codificados como códigos canónicos de Huffman al proporcionar la longitud en 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 incluir la representación de á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.

Codificador/compresor

Durante la etapa de compresión, es el codificador el que elige la cantidad de tiempo dedicado a buscar cadenas coincidentes. La implementación de referencia zlib/gzip permite al usuario seleccionar entre una escala móvil el posible nivel de compresión resultante frente a la velocidad de codificación. Las opciones van desde 0(no intentar comprimir, 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. Es probable que diferentes implementaciones produzcan variaciones en el flujo de bits codificado final producido. El objetivo de las versiones de un codificador que no son zlib normalmente ha sido 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 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 ampliación de los códigos de distancia a 16 bits para que puedan abordar un rango de 64 KB, y la longitud del código, que se amplía a 16 bits para que puede definir longitudes de tres a 65.538 bytes. ^[6] Esto lleva a que Deflate64 tenga un tiempo de compresión más largo y potencialmente una relación de compresión ligeramente mayor que Deflate. ^[7] Varios proyectos gratuitos y/o de código abierto soportan Deflate64, como 7-Zip , ^[8] mientras que otros, como zlib , no lo hacen, como resultado de la naturaleza propietaria del procedimiento ^[9] y el muy modesto aumento del rendimiento respecto a Deflate. ^[10]

Usando Deflate en software nuevo

Las implementaciones de Deflate están disponibles gratuitamente en muchos idiomas. Las aplicaciones escritas en C suelen utilizar la biblioteca zlib (bajo la licencia zlib permisiva ). Las aplicaciones en Borland Pascal (e idiomas compatibles) pueden usar paszlib. Las aplicaciones en C++ pueden aprovechar la biblioteca Deflate mejorada en 7-Zip . Tanto Java como .NET Framework ofrecen soporte listo para usar para Deflate en sus bibliotecas (respectivamente, java.util.zipy System.IO.Compression). Las aplicaciones en Ada pueden usar Zip-Ada (puro) o ZLib-Ada.

Implementaciones de codificador

• 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 § Horquillas para horquillas 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 con suerte más comprensible y fácil de mantener [que zlib] ".
• 7-Zip : escrita por Igor Pavlov en C++ , esta versión tiene licencia gratuita y logra una mayor compresión 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 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 del Plan 9 de Bell Labs , implementa la compresión desinflada
• Hyperbac : utiliza su propia biblioteca de compresión patentada (en C++ y ensamblador) con una opción para implementar el formato de almacenamiento DEFLATE64.
• Zopfli : Implementación de C bajo Licencia Apache de Google ; logra la máxima 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 , lanzado por Intel bajo la licencia MIT . 3 veces más rápido que zlib -1. Útil para comprimir datos genómicos. ^[12]
• libdeflate: ^[13] una biblioteca para compresión y descompresión rápida basada en DEFLATE en todo el búfer. Libdeflate está muy optimizado y especialmente en procesadores x86.

AdvanceCOMP utiliza las versiones con una relación de compresión más alta de Deflate 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 la configuración máxima. ^[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 usando Deflate a una velocidad de hasta 3,0 Gbit/s (375 MB/s) para datos entrantes sin comprimir. Acompañando al controlador del kernel de Linux para el AHA361-PCIX hay una " " utilidad personalizada " " capaz de utilizar la compresión de hardware de Apache . El hardware se basa en una FPGA Xilinx Virtex y cuatro ASIC AHA3601 personalizados . Las placas AHA361/AHA362 están limitadas a manejar únicamente bloques Huffman estáticos y requieren que se modifique el software para agregar soporte; las tarjetas no pudieron soportar la especificación Deflate completa, lo que significa que solo pudieron decodificar de manera confiable su propia salida (una secuencia que no contener cualquier bloque dinámico de Huffman 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 presentan entre uno y seis motores de compresión con velocidades de procesamiento declaradas de hasta 3,6 Gbit/s (450 MB/s). Hay disponible una versión de las tarjetas con la marca separada WebEnhance, diseñada específicamente para uso de servicio web en lugar de SAN o uso de respaldo; Como revisión de 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. Utilizando 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 la tarjeta de solo codificación 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. Los controladores de dispositivos kernel de Linux, Microsoft Windows y OpenSolaris están disponibles para ambas tarjetas nuevas, 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 del AHA362-PCIX, los motores de descompresión de las placas AHA363-PCIe y AHA367-PCIe cumplen totalmente con la normativa de desinflado.
• 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 HDL-Deflate GPL FPGA.
• ZipAccel-C de CAST Inc. Este es un núcleo IP de silicio que admite compresión Deflate, 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 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 en 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 del acelerador Nest (NX) anteriormente 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]}

Decodificador/descompresor

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

Implementaciones de solo inflar

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 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 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 C bajo la licencia GNU LGPL . Utilizado en el instalador de GIMP .
  • puff.c ( zlib ), una pequeña implementación de referencia de un solo archivo, 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 Inflate de dominio público contenida íntegramente en una única función de C.
• PCDEZIP, Bob Flanders y Michael Holmes, publicado en PC Magazine el 11 de enero de 1994.
• inflar.cl por John Foderaro. Decodificador Common Lisp autónomo 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 Deflate ( gzip ) y bzip2 independiente de Python puro de Paul Sladen. Escrito para investigación/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.
• inflar una implementación Javascript pura de Inflate por Chris Dickinson
• pako: puerto JavaScript de velocidad optimizada de zlib. Contiene construcción separada con inflado únicamente.

Decodificadores de hardware

• GPU inflada en serie de BitSim. Implementación hardware de Inflate. Parte de la oferta de controladores BADGE (Bitsim Accelerated Display Graphics Engine) de BitSim para sistemas integrados.
• Implementación HDL-Deflate GPL FPGA.
• ZipAccel-D de CAST Inc. Este es un núcleo IP de silicio que admite la descompresión de archivos Deflate, 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).
• 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 en 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 del acelerador Nest (NX) anteriormente 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]}

Ver 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 plano - comprimir/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 RFC 1951.
2. Adobe Systems incorporados . "PDF 32000-1:2008: Gestión de documentos - Formato de documento portátil - Parte 1: PDF 1.7" (PDF) . Código abierto de Adobe . Adobe. pag. 23 . Consultado el 5 de septiembre de 2023 . FlateDecode [...] Descomprime datos codificados usando el método de compresión zlib/deflate
3. Deutsch, L. Peter (mayo de 1996). DEFLATE Especificación de formato de datos comprimidos versión 1.3. IETF . pag. 1 segundo. Abstracto. doi : 10.17487/RFC1951 . RFC 1951 . Consultado el 23 de abril de 2014 .
4. Patente de EE. UU. 5051745, Katz, Phillip W. , "String Searcher and Compressor usando el mismo", publicado el 24 de septiembre de 1991, emitido el 24 de septiembre de 1991, asignado a PKWare Inc. 
5. David, Salomón (2007). Compresión de datos: la referencia completa (4 ed.). Saltador. pag. 241.ISBN _ 978-1-84628-602-5.
6. "Esencia binaria - Deflate64". Archivado desde el original el 21 de junio de 2017 . Consultado el 22 de mayo de 2011 .{{cite web}}: Mantenimiento CS1: bot: estado de la URL original desconocido ( enlace )
7. "Binary Essence - Comparaciones de compresión" Calgary Corpus ". Archivado desde el original el 27 de diciembre de 2017 . Consultado el 22 de mayo de 2011 .{{cite web}}: Mantenimiento CS1: bot: estado de la URL original desconocido ( enlace )
8. "Interruptor -m (Establecer método de compresión)". Sevenzip.osdn.jp . Archivado desde el original el 9 de abril de 2022 . Consultado el 21 de enero de 2023 .
9. Historia de los algoritmos de compresión de datos sin pérdidas: Deflate64
10. Preguntas frecuentes sobre zlib: ¿zlib es compatible con el nuevo formato "Deflate64" introducido por PKWare?
11. "Plan 9 de /n/sources/plan9/sys/src/libflate de Bell Labs". plan9.bell-labs.com . Tecnologías Lucent. 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". Software Intel . 1 de octubre de 2019 . Consultado el 18 de enero de 2020 .
13. "libdeflate". Biblioteca muy 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® series 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 multinube híbrida de misión crítica". IBM . 12 de septiembre de 2019 . Consultado el 1 de noviembre de 2021 .
17. Lascu, Octavio (28 de abril de 2021). Guía técnica de IBM z15 (8562), página 97. IBM Redbooks. ISBN 9780738458991. Consultado el 1 de noviembre de 2021 .
18. "Compresión de datos mediante el uso de la biblioteca zlibNX - Documentación de IBM". IBM . Consultado el 1 de noviembre de 2021 .
19. "Explotación de la aceleración interna de procesadores POWER para AIX" . Consultado el 1 de noviembre de 2021 .

enlaces externos

• Especificación de formato de archivo .ZIP de PKWARE, Inc.appnote.txt Archivado el 5 de diciembre de 2014 en Wayback Machine ; Sección 10, X. Deflactación – Método 8 .
• RFC 1951 – Deflate Especificación de formato de datos comprimidos versión 1.3
• Página de inicio de zlib
• Una explicación del algoritmo de deflación – 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 de Jesper Larsson
• Archivos Zip: Historia, explicación e implementación: recorrido por una implementación de Deflate