Algoritmos de compresión de datos sin pérdidas. Principios de compresión de información Tipos de compresión de gráficos, video y audio.

Hoy en día, en Internet hay docenas de archivadores populares, y en la descripción de cada programa puede encontrar que su algoritmo es el mejor... Decidí tomar varios archivadores populares en Internet, a saber: WinRar, WinUha, WinZip, KGB. archiver, 7Z y pruébelos en condiciones de “combate” ».

Un pequeño prefacio... La comparación puede no ser muy objetiva. La comparación de los ahivadores se realizó en la computadora doméstica más común, la promedio actual. Además, no se tomaron diferentes tipos de datos: la comparación de compresión se realizó en un documento "Word" normal, del cual muchos de los que estudian o trabajan con él pueden acumular una gran cantidad. Bueno, es lógico que sea recomendable empaquetar en un archivo información que rara vez utilizas y, a veces, extraerla. Y es mucho más fácil transferir un archivo de este tipo: se copiará en una unidad flash más rápido que un montón de archivos pequeños y se descargará más rápido a través de Internet...

Tabla comparativa de compresión

Para un pequeño experimento, se tomó un archivo RTF relativamente grande, de aproximadamente 3,5 MB, y se comprimió con diferentes archivadores. Todavía no tomamos en cuenta el tiempo de funcionamiento, las características de los programas se discutirán más a fondo, pero ahora solo veremos el nivel de compresión.

Programa	Formato	Índice de compresión	Tamaño, kbytes	¿Cuántas veces ha disminuido el tamaño del archivo? ?
Archivador 2 de la KGB	.kgb	máximo	141411	22,99
winrar	.rar	máximo	190546	17,07
WinUha	.uha	máximo	214294	15,17
7Z	.7z	máximo	218511	14,88
WinZip	.cremallera	máximo	299108	10,87
Archivo original	.rtf	Sin compresión	3252107	1

Como se puede ver en la placa pequeña, la relación de compresión más alta se logra con el programa KGB Archiver 2: ¡el tamaño del archivo original se ha reducido 23 veces! Aquellos. Si tiene varios gigabytes de documentación diversa en su disco duro que no usa y desea eliminar (pero no puede evitar la sensación de que podría resultarle útil), ¿no sería más fácil comprimirlo con tales un programa y escribirlo en el disco...

Pero sobre todos los peligros en orden...

Archivador 2 de la KGB

En general, no es un mal archivador; según los desarrolladores, su algoritmo de compresión es uno de los "más fuertes". Es difícil no estar de acuerdo...

Sólo la velocidad de compresión deja mucho que desear. Por ejemplo, el archivo del ejemplo (aproximadamente 3 MB) fue comprimido por el programa durante aproximadamente 3 minutos. No es difícil estimar que comprimirá un disco CD durante medio día, si no más.

Pero esto no es particularmente sorprendente. ¡Descomprimir un archivo lleva tanto tiempo como comprimirlo! Aquellos. Si pasó medio día comprimiendo algunos de sus documentos, dedicará la misma cantidad de tiempo a sacarlos del archivo.

Resultado: el programa se puede utilizar para pequeñas cantidades de información, especialmente cuando el tamaño mínimo del archivo fuente es importante (por ejemplo, el archivo debe colocarse en un disquete o en una pequeña unidad flash). Pero nuevamente, es imposible adivinar el tamaño del archivo comprimido de antemano, y puedes perder tiempo comprimiéndolo...

winrar

El famoso programa en el espacio postsoviético está instalado en la mayoría de las computadoras. Probablemente, si no hubiera mostrado tan buenos resultados, no habría tenido tantos fans. A continuación se muestra una captura de pantalla que muestra la configuración de compresión, nada especial, excepto que el nivel de compresión se estableció al máximo.

Sorprendentemente, WinRar comprimió el archivo en unos pocos segundos y el tamaño del archivo se redujo 17 veces. Un resultado muy digno, teniendo en cuenta que el tiempo dedicado al procesamiento es insignificante. ¡Y el tiempo para descomprimir el archivo es aún menor!

Resultado: Un excelente programa que muestra algunos de los mejores resultados. Durante la configuración de compresión, también puede especificar el tamaño máximo del archivo y el programa lo dividirá en varias partes. Esto es muy conveniente para transferir un archivo de una computadora a otra en una unidad flash o en un disco CD/DVD, cuando no puede escribir el archivo completo en...

WinUha

Un archivero relativamente joven. No se puede llamar muy popular, pero muchos usuarios que trabajan a menudo con archivos están interesados ​​en él. Y no es casualidad, porque según los desarrolladores del archivador, su algoritmo de compresión es más potente que el de RAR y 7Z.

En nuestro pequeño experimento, no diría que esto sea así. Es posible que con algunos otros datos muestre resultados mucho mejores...

Por cierto, al instalar, seleccione inglés, en ruso el programa muestra "cryakozabry".

Resultado: un buen programa con un interesante algoritmo de compresión. El tiempo para procesar y crear un archivo es, por supuesto, más largo que el de WinRar, pero para algunos tipos de datos puede obtener una relación de compresión ligeramente mayor. Aunque, personalmente, no pondría mucho énfasis en esto...

7Z

Un archivador gratuito muy popular. Muchos argumentan que la relación de compresión en 7z es incluso mejor que en WinRar. Es muy posible, pero cuando se comprime con el nivel "Ultra" en la mayoría de los archivos, pierde frente a WinRar.

Resultado: una buena alternativa a WinRar. Relación de compresión bastante comparable, buen soporte para el idioma ruso, integración conveniente en el menú contextual del Explorador.

WinZip

Legendario, uno de los archivadores más populares de todos los tiempos. En Internet, probablemente los archivos más comunes sean “ZIP”. Y no es una coincidencia: a pesar de la relación de compresión no tan alta, la velocidad de funcionamiento es simplemente asombrosa. Por ejemplo, Windows abre dichos archivos como carpetas normales.

Además, no debemos olvidar que este formato de archivado y compresión es mucho más antiguo que sus novedosos competidores. Y no todo el mundo dispone ahora de ordenadores potentes que les permitan trabajar rápidamente con nuevos formatos. ¡Y el formato Zip es compatible con todos los archivadores modernos!

La mayoría de los usuarios saben que a veces se utiliza la compresión para reducir el tamaño de los archivos fuente para que sea más conveniente almacenarlos o enviarlos, por ejemplo, por correo electrónico. Sin embargo, por alguna razón, en este caso la asociación se produce solo con aplicaciones de archivado y no se tienen en cuenta otras técnicas de compresión de datos. A continuación, veremos qué determina el grado de compresión de un archivo, usando el ejemplo de varias de las situaciones más comunes.

¿Qué se entiende por relación de compresión de archivos?

Comencemos con preguntas teóricas. ¿Cuál es la relación de compresión de un archivo? Según las interpretaciones más simples de este término, significa la relación entre el tamaño del objeto final (comprimido) y el volumen inicial. Sin embargo, esta explicación puede aplicarse en gran medida exclusivamente a los datos de archivo, ya que no aborda en absoluto algunas cuestiones asociadas con el cambio de formato multimedia, donde la compresión también es muy común. En general, no se puede decir que el grado de compresión de un archivo dependa únicamente de una característica particular. En este caso, influyen el tipo de objeto, los programas utilizados para comprimir los datos y la velocidad del proceso de compresión. A continuación, discutiremos brevemente algunos aspectos importantes que pueden afectar el resultado final de reducir el tamaño de los datos fuente.

El grado de compresión del archivo depende únicamente del tipo de archivo: ¿es esto realmente cierto?

Sí, de hecho, el tipo de datos que se comprimen tiene un impacto bastante grande en la reducción del tamaño del archivo final y no todos los formatos pueden someterse a tales procedimientos. Esto se puede explicar con el ejemplo de los archivos de sonido, que inicialmente ya están comprimidos.

Al intentar empaquetar dichos datos en un archivo, es casi imposible lograr una reducción significativa de su tamaño. Lo mismo ocurre con el formato WAV. Sin embargo, si no comprime, sino que transcodifica de WAV a MP3, el tamaño se puede reducir en un factor de diez o más. Muchos usuarios se desaniman inmediatamente por el hecho de que el grado de compresión del archivo depende del formato inicial y final. Esto no es del todo cierto, ya que el algoritmo de recodificación utilizado también juega un papel importante, que se analizará por separado. Por ahora, centrémonos en el uso de archivadores.

¿Qué determina el grado de compresión de un archivo al empaquetarlo en un archivo?

Para comprender inicialmente la esencia de este tipo de compresión, para facilitar la explicación usaremos como ejemplo el archivador WinRAR más común. No tocaremos los tipos de datos que se empaquetan, sino que nos centraremos en las herramientas de la aplicación en sí.

Para empezar, debes prestar atención al formato final del archivo, así como al método de empaquetado utilizado. Está claro que en este caso el grado de compresión del archivo por parte del programa de archivo depende de la técnica preferida. Con el método de alta velocidad, la compresión será mínima, pero con la relación de compresión máxima, el tamaño se reducirá de manera más significativa y se necesitará más tiempo.

Si consideramos los formatos de archivos en relación con los archivadores, los documentos de texto de cualquier formato se pueden distinguir de los más comprimibles.

Algunos archivos ejecutables en formato EXE se comprimen relativamente bien (utilizando el método de compresión estándar, puede reducir el tamaño a más de la mitad). Los más incompresibles, como ya se mencionó, son los objetos multimedia. Y, aunque al menos de alguna manera es posible reducir el tamaño de las imágenes, tales acciones no funcionan con audio y video sin cambiar el formato inicial, y los archivadores no tienen absolutamente nada que ver con eso.

Tipos de compresión de gráficos, vídeo y audio.

Cuando se trata de multimedia, existen dos tipos principales de compresión: con pérdida y sin pérdida. Y en este caso, el grado de compresión del archivo depende precisamente de la tecnología de compresión utilizada.

En el primer caso la compresión es máxima, en el segundo puede variar, lo que está influenciado por el conjunto de códecs utilizados y el formato del contenedor final. Así, por ejemplo, el mismo archivo AVI puede ser un contenedor que contenga tipos de datos completamente diferentes y con diferentes grados de compresión. Debido a esto, por cierto, a veces pueden surgir problemas con la reproducción de vídeo en los reproductores domésticos.

En general, si hablamos específicamente de multimedia, aquí debe comprender claramente que es casi imposible lograr la reducción máxima en el tamaño del archivo fuente de cualquier formato sin una pérdida significativa de calidad, a pesar de las tecnologías para eliminar contenido redundante (por (por ejemplo, para gráficos o vídeo, esto sólo funciona en el caso de escenas que no se pueden modificar). En el caso del audio, se reduce la tasa de bits y se recortan determinadas frecuencias. Es posible que el usuario medio no sienta la diferencia, pero un profesional con buen oído detectará inmediatamente lo que falta.

Los programas más habituales para todas las ocasiones.

Averigüemos un poco de qué depende el grado de compresión del archivo. Ahora deberíamos decir algunas palabras sobre los productos de software utilizados. Entre los archivadores, los más comunes son WinRAR, WinZIP y 7-Zip.

En cuanto a la compresión multimedia, en el caso más simple, puede utilizar aplicaciones de conversión especiales que funcionan según el principio de transcodificar el material fuente a otro formato para reducir el tamaño del archivo.

Breve resumen

En resumen, se puede observar que el grado de compresión de archivos por parte del archivador depende de varios factores y, con mayor frecuencia, del tipo de datos que se comprimen, el software utilizado y (generalmente los algoritmos de Huffman y Lempel-Ziv, que funcionan en pares, son usados). En el caso de los contenidos multimedia la situación es casi la misma, pero la posición dominante la ocupa la conversión de formato de uno a otro.

ARCHIVADORES

Compresión de información es el proceso de transformar la información almacenada en un archivo reduciendo la redundancia de datos. La finalidad de este proceso es reducir el volumen ocupado por los datos.

Archivo de archivo es un archivo especialmente creado que contiene uno o más archivos en forma comprimida.

Índice de compresión: Kc =Vc /Vo *100%

kc- índice de compresión, vc– volumen del archivo comprimido, vo– tamaño del archivo inicial.

La relación de compresión depende de:

1) el programa utilizado - archivador,

2) método de compresión,

3) tipo de archivo fuente: texto, gráfico, vídeo, sonido, etc.

Los programas que empaquetan y descomprimen archivos se llaman archivadores. Los más comunes son: ARJ, ZIP, RAR. La extensión de los archivos comprimidos coincide con el nombre del archivador utilizado para crearlos.

Los archivadores le permiten crear archivos de almacenamiento autoextraíbles, es decir. Para descomprimirlos, no es necesario iniciar el programa de archivado, porque ellos mismos contienen un programa de desembalaje. Estos archivos se llaman archivos SFX.
(Autoextraíble). La extensión de dichos archivos es *.EXE.

Principios de compresión de información.

Hay caracteres repetidos en cualquier texto. Es posible especificar un carácter y el número de repeticiones. La eficiencia de este algoritmo es aún mayor cuando se aplica a archivos gráficos. Si miras el monitor, puedes ver muchos puntos repetidos del mismo color. El formato de archivo gráfico PCX se basa en este principio de compresión de información. Los archivadores modernos resaltan no solo caracteres repetidos, sino también cadenas de caracteres y palabras individuales.

Si el texto no utiliza todos los caracteres del alfabeto de la PC, para codificarlos puede utilizar un byte, 8 bits o un número menor. Este principio se utiliza en los aparatos de telégrafo, donde sólo se utilizan letras mayúsculas rusas; para representarlas bastan 5 bits, lo que permite escribir tres caracteres en dos bytes.

3. El siguiente principio utiliza el patrón de que las letras aparecen en el texto con diferentes frecuencias. Por ejemplo, en este texto el espacio es el carácter más común; los símbolos “a” y “y” son muy comunes. Estos caracteres que aparecen con frecuencia se pueden representar como una secuencia corta de bits, mientras que otros caracteres se pueden codificar como una secuencia más larga. Por ejemplo:

4. Físicamente, la PC asigna espacio para colocar archivos en el disco en grupos, en bloques de 4 kB. Es imposible destacar menos. Por ejemplo, si un archivo tiene un tamaño de 8193 bytes (8 kB y 1 byte), ocupará físicamente 16 kB o 16384 bytes. Combinar un grupo de archivos en uno le permite ahorrar estos restos. Esto proporciona grandes ahorros al empaquetar archivos pequeños.

En total, al colocar archivos por separado, no se utilizan 6 kB, que es el 100% del contenido de los archivos. En el segundo caso, quedan 2 kB, el 33%, sin utilizar.

zip del archivador

Empacar archivos pkzip [claves]<имя архива>[rutas de archivos]

Llaves: -rp Archivar con subdirectorios manteniendo la estructura.

S PWD protección de contraseña de archivo (PWD)

A agregar archivos para archivar

M mover archivos para archivar

V ver el contenido del archivo

Si se están archivando todos los archivos en un directorio, entonces es necesario especificar la máscara *.*

Descomprimiendo archivos pkunzip [interruptores]<имя архива>[nombres de archivos]

Claves: -d descomprimir con subdirectorios preservando la estructura

Contraseña de archivo SPWD (PWD)

Archivador arj

arj<команда>[llaves]<имя архива>[nombres de archivos]

Para el archivador arj, un archivo realiza operaciones de descompresión y empaquetado.

Equipos: a archivar

e descomprimir sin preservar la estructura del directorio

X desembalaje preservando la estructura

l ver el contenido del archivo

m mover archivos para archivar

d eliminar archivos del archivo

Claves: -r empaquetar con subdirectorios preservando la estructura

V desglose del archivo en volúmenes con un volumen de vol (si se especifica)

el tamaño de los disquetes estándar (360, 720, 1200, 1440) se indica en kilobytes, el tamaño de los disquetes no estándar se indica en bytes

V se indica al descomprimir un archivo de varios volúmenes

GRAMO PWD contraseña de archivo ( PWD)

Empacar archivos

Descomprimir archivos

Uno de los tipos más comunes de programas de sistema son los programas diseñados para archivar y empaquetar archivos comprimiendo la información almacenada en ellos.

La compresión de información es el proceso de transformar la información almacenada en un archivo, como resultado de lo cual se reduce su redundancia y, en consecuencia, se requiere menos memoria para el almacenamiento.

La compresión de información en archivos se logra eliminando la redundancia de varias maneras, como simplificando los códigos, eliminando bits constantes o representando caracteres repetidos o una secuencia repetida de caracteres en términos de un factor de repetición y los caracteres correspondientes. Se utilizan varios algoritmos para dicha compresión de información.

Se pueden comprimir tanto uno como varios archivos, que en forma comprimida se colocan en el llamado archivo de almacenamiento o archivar.

Un archivo de almacenamiento es un archivo especialmente organizado que contiene uno o más archivos comprimidos o sin comprimir e información de servicio sobre nombres de archivos, fecha y hora de su creación o modificación, tamaños, etc.

El propósito del empaquetado de archivos suele ser garantizar una ubicación más compacta de la información en el disco, reduciendo el tiempo y, en consecuencia, el costo de transmitir información a través de canales de comunicación en redes informáticas. Además, empaquetar un grupo de archivos en un archivo simplifica significativamente su transferencia de una computadora a otra, reduce el tiempo de copia de archivos a discos, le permite proteger la información del acceso no autorizado y ayuda a proteger contra infecciones por virus informáticos.

Bajo índice de compresión comprender la relación entre los tamaños del archivo comprimido y el original, expresada como porcentaje.

Índice de compresión Depende del programa de compresión utilizado, el método de compresión y el tipo de archivo fuente. Los mejores archivos comprimidos son imágenes gráficas, archivos de texto, archivos de datos, cuya relación de compresión puede alcanzar entre el 5 y el 40%, los archivos de programas ejecutables y módulos de carga se comprimen menos: entre el 60 y el 90%. Los archivos comprimidos casi no están comprimidos. Los programas de archivo difieren en los métodos de compresión que utilizan, lo que en consecuencia afecta la relación de compresión.

Archivar (empaquetar): colocar (descargar) archivos fuente en un archivo comprimido en forma comprimida o sin comprimir.

Descomprimir (descomprimir) es el proceso de restaurar archivos de un archivo exactamente como estaban antes de cargarlos en el archivo. Al descomprimir, los archivos se extraen del archivo y se colocan en el disco o en la RAM.

Los programas que empaquetan y descomprimen archivos se denominan programas de archivado.

Los archivos grandes se pueden colocar en varios discos (volúmenes). Estos archivos se denominan multi volumen. Un volumen es una parte integral de un archivo de varios volúmenes. Al crear un archivo a partir de varias partes, puede grabar sus partes en varios medios.

Principales tipos de programas de archivado.

Actualmente, se utilizan varias docenas de programas de archivado, que se diferencian en la lista de funciones y parámetros operativos, pero los mejores tienen aproximadamente las mismas características. Entre los programas más populares se encuentran: Zip (y su modificación WinZip), WinRAR, Arj (y sus variedades), G-Zip, 7-Zip.

Los programas de archivo también le permiten crear archivos que no requieren ningún programa para extraer archivos, ya que los archivos en sí pueden contener un programa de descompresión. Estos archivos comprimidos se denominan autoextraíbles. Un archivo de almacenamiento autoextraíble es un módulo ejecutable de arranque que es capaz de descomprimir de forma independiente los archivos que contiene sin utilizar un programa de archivado.

Archivo autoextraíble tengo el nombre archivo de efectos especiales(Autoextraíble). Los archivos de este tipo normalmente se crean en formato de archivo EXE.

Muchos programas de archivado descomprimen archivos volcándolos en el disco, pero también existen aquellos que están diseñados para crear un módulo (programa) ejecutable empaquetado. Como resultado de dicho empaquetado, se crea un archivo de programa con el mismo nombre y extensión que, cuando se carga en la RAM, se autoextrae y se ejecuta inmediatamente. Al mismo tiempo, también es posible convertir el archivo del programa al formato descomprimido. Estos archivadores incluyen los programas Upx, PKLITE, LZEXE.

El programa EXPAND, que forma parte de las utilidades del sistema operativo Windows, se utiliza para descomprimir archivos de productos de software suministrados por Microsoft.

Formas de gestionar el programa de archivado.

El programa de archivado se controla de una de las siguientes maneras:

• - utilizando la línea de comando, en la que se genera un comando de inicio que contiene el nombre del programa archivador, el comando de control y sus claves de configuración, así como los nombres del archivo y los archivos fuente;
• - utilizando un shell integrado y paneles de diálogo que aparecen después de iniciar el programa y permiten el control mediante menús y teclas de función, lo que crea condiciones de trabajo más cómodas para el usuario;
• - utilizando el menú contextual del Explorador en el sistema operativo Windows.

Primera parte - histórica.

Introducción

Los algoritmos de compresión de datos existentes se pueden dividir en dos grandes clases: con pérdida y sin pérdida. Los algoritmos con pérdida se utilizan comúnmente para la compresión de imágenes y audio. Estos algoritmos permiten alcanzar altas tasas de compresión mediante una pérdida selectiva de calidad. Sin embargo, por definición, es imposible recuperar los datos originales del resultado comprimido.
Los algoritmos de compresión sin pérdida se utilizan para reducir el tamaño de los datos y funcionan de tal manera que es posible restaurar los datos exactamente como estaban antes de la compresión. Se utilizan en comunicaciones, archivadores y algunos algoritmos para comprimir información gráfica y de audio. A continuación, consideraremos únicamente algoritmos de compresión sin pérdidas.
El principio básico de los algoritmos de compresión se basa en el hecho de que en cualquier archivo que contenga datos no aleatorios, la información se repite parcialmente. Utilizando modelos matemáticos estadísticos, se puede determinar la probabilidad de repetición de una determinada combinación de símbolos. Luego puede crear códigos para las frases seleccionadas y asignar los códigos más cortos a las frases que se repiten con más frecuencia. Para ello se utilizan varias técnicas, por ejemplo: codificación de entropía, codificación de repetición y compresión de diccionario. Con su ayuda, se puede sustituir un carácter de 8 bits o una cadena completa por unos pocos bits, eliminando así información innecesaria.

Historia

Jerarquía de algoritmos:

Aunque la compresión de datos se generalizó con Internet y después de la invención de los algoritmos Lempel y Ziv (algoritmos LZ), se pueden citar varios ejemplos anteriores de compresión. Morse, al inventar su código en 1838, asignó sabiamente las letras más utilizadas en el idioma inglés, “e” y “t”, las secuencias más cortas (punto y raya, respectivamente). Poco después de la llegada de las computadoras centrales en 1949, se inventó el algoritmo de Shannon-Fano, que asignaba códigos a los caracteres de un bloque de datos en función de la probabilidad de que aparecieran en el bloque. La probabilidad de que apareciera un carácter en un bloque era inversamente proporcional a la longitud del código, lo que permitía comprimir la representación de los datos.
David Huffman era estudiante de la clase de Robert Fano y eligió como trabajo de curso la búsqueda de un método mejorado de codificación de datos binarios. Como resultado, logró mejorar el algoritmo de Shannon-Fano.
Las primeras versiones de los algoritmos de Shannon-Fano y Huffman utilizaban códigos predefinidos. Posteriormente, comenzaron a utilizar códigos creados dinámicamente a partir de datos destinados a la compresión. En 1977, Lempel y Ziv publicaron su algoritmo LZ77, basado en el uso de un diccionario creado dinámicamente (también llamado “ventana deslizante”). En el 78 publicaron el algoritmo LZ78, que primero analiza los datos y crea un diccionario, en lugar de crearlo dinámicamente.

Cuestiones de derechos

Los algoritmos LZ77 y LZ78 ganaron gran popularidad y provocaron una ola de mejoradores, de los cuales DEFLATE, LZMA y LZX han sobrevivido hasta el día de hoy. La mayoría de los algoritmos populares se basan en LZ77 porque el algoritmo LZW derivado de LZ78 fue patentado por Unisys en 1984, después de lo cual comenzaron a trollear a todos, incluidos incluso los casos de uso de imágenes GIF. En ese momento, se utilizaba en UNIX una variación del algoritmo LZW llamado LZC y, debido a problemas de derechos, su uso tuvo que eliminarse gradualmente. Se dio preferencia al algoritmo DEFLATE (gzip) y a la transformada de Burrows-Wheeler, BWT (bzip2). Lo cual fue lo mejor, ya que estos algoritmos casi siempre superan a LZW en compresión.
En 2003, la patente había expirado, pero el tren ya había partido y el algoritmo LZW se conservaba, tal vez, sólo en archivos GIF. Los algoritmos basados ​​en LZ77 son dominantes.
Hubo otra batalla de patentes en 1993 cuando Stac Electronics descubrió que Microsoft estaba utilizando el algoritmo LZS que había desarrollado en un programa de compresión de disco que venía con MS-DOS 6.0. Stac Electronics presentó una demanda y pudieron ganar el caso, lo que les permitió recibir más de 100 millones de dólares.

El auge de Deflate

Las grandes corporaciones utilizaron algoritmos de compresión para almacenar cantidades cada vez mayores de datos, pero el verdadero auge de los algoritmos se produjo con el nacimiento de Internet a finales de los años ochenta. La capacidad de los canales era extremadamente estrecha. Para comprimir los datos transmitidos a través de la red, se inventaron los formatos ZIP, GIF y PNG.
Tom Henderson inventó y lanzó el primer archivador comercialmente exitoso, ARC, en 1985 (System Enhancement Associates). ARC era popular entre los usuarios de BBS porque... fue uno de los primeros en poder comprimir varios archivos en un archivo y sus fuentes también estaban abiertas. ARC utilizó un algoritmo LZW modificado.
Phil Katz, inspirado por la popularidad de ARC, lanzó el programa PKARC en formato shareware, en el que mejoró los algoritmos de compresión reescribiéndolos en lenguaje ensamblador. Sin embargo, Henderson fue juzgado y declarado culpable. PKARC copió ARC tan abiertamente que a veces incluso repetía errores tipográficos en los comentarios del código fuente.
Pero Phil Katz no estaba perdido y en 1989 cambió radicalmente el archivador y lanzó PKZIP. Después de ser atacado por su patente sobre el algoritmo LZW, cambió el algoritmo básico por uno nuevo llamado IMPLODE. El formato fue reemplazado nuevamente en 1993 con el lanzamiento de PKZIP 2.0, y DEFLATE se convirtió en su reemplazo. Entre las nuevas características estaba la función de dividir el archivo en volúmenes. Esta versión sigue siendo muy utilizada, a pesar de su avanzada edad.
El formato de imagen GIF (Graphics Interchange Format) fue creado por CompuServe en 1987. Como sabe, el formato admite la compresión de imágenes sin pérdidas y está limitado a una paleta de 256 colores. A pesar de todos los esfuerzos de Unisys, no pudo detener la difusión de este formato. Sigue siendo popular hoy en día, especialmente debido a su soporte de animación.
Ligeramente preocupado por cuestiones de patentes, CompuServe lanzó el formato Portable Network Graphics (PNG) en 1994. Al igual que ZIP, utilizaba el nuevo y sofisticado algoritmo DEFLATE. Aunque DEFLATE fue patentado por Katz, no hizo ninguna afirmación.
Este es ahora el algoritmo de compresión más popular. Además de PNG y ZIP, se utiliza en gzip, HTTP, SSL y otras tecnologías de transferencia de datos.

Desafortunadamente, Phil Katz no vivió para ver el triunfo de DEFLATE; murió de alcoholismo en 2000 a la edad de 37 años. Ciudadanos: ¡el consumo excesivo de alcohol es peligroso para la salud! ¡Quizás no vivas para ver tu triunfo!

Archivadores modernos

ZIP reinó hasta mediados de los 90, pero en 1993, un simple genio ruso, Evgeniy Roshal, ideó su propio formato y algoritmo RAR. Sus últimas versiones se basan en los algoritmos PPM y LZSS. Hoy en día, ZIP es quizás el formato más común, RAR era hasta hace poco el estándar para distribuir diversos contenidos ilegales a través de Internet (gracias al mayor ancho de banda, los archivos se distribuyen cada vez más sin necesidad de archivarlos) y 7zip se utiliza como el formato con mejor compresión. con un tiempo de funcionamiento aceptable. En el mundo UNIX, se usa la combinación tar + gzip (gzip es un archivador y tar combina varios archivos en uno, ya que gzip no puede hacer esto).

Nota traducción Personalmente, además de los enumerados, también me encontré con el archivador ARJ (Archivado por Robert Jung), que fue popular en los años 90 durante la era BBS. Admitía archivos de varios volúmenes y, al igual que RAR, se utilizaba para distribuir juegos y otro software. También estaba el archivador HA de Harri Hirvola, que usaba compresión HSC (no encontré ninguna explicación clara, solo "modelo de contexto limitado y codificación aritmética"), que hizo un buen trabajo al comprimir archivos de texto largos.

En 1996, apareció la versión de código abierto del algoritmo BWT, bzip2, que rápidamente ganó popularidad. En 1999 apareció el programa 7-zip con el formato 7z. En términos de compresión compite con RAR, su ventaja es la apertura, así como la posibilidad de elegir entre los algoritmos bzip2, LZMA, LZMA2 y PPMd.
En 2002 apareció otro archivador, PAQ. El autor Matt Mahone utilizó una versión mejorada del algoritmo PPM utilizando una técnica llamada "mezcla contextual". Le permite utilizar más de un modelo estadístico para mejorar la predicción de la frecuencia de los símbolos.

El futuro de los algoritmos de compresión

Por supuesto, Dios lo sabe, pero aparentemente el algoritmo PAQ está ganando popularidad debido a su muy buena relación de compresión (aunque es muy lenta). Pero gracias al aumento de la velocidad de las computadoras, la velocidad se está volviendo menos crítica.
Por otro lado, el algoritmo Lempel-Ziv-Markov LZMA representa un equilibrio entre velocidad y relación de compresión y puede dar lugar a muchas ramificaciones interesantes.
Otra tecnología interesante es la “enumeración de subcadenas” o CSE, que todavía se utiliza poco en los programas.

En la siguiente parte veremos el aspecto técnico de los algoritmos mencionados y los principios de su funcionamiento.