Compresión sin perdidas

La compresión sin pérdida es una clase de compresión de datos que permite reconstruir perfectamente los datos originales a partir de los datos comprimidos sin pérdida de información. La compresión sin pérdidas es posible porque la mayoría de los datos del mundo real exhiben redundancia estadística. Por el contrario, la compresión con pérdida permite la reconstrucción solo de una aproximación de los datos originales, aunque generalmente con tasas de compresión muy mejoradas (y, por lo tanto, tamaños de medios reducidos).

De acuerdo con el principio del casillero, ningún algoritmo de compresión sin pérdidas puede comprimir de manera eficiente todos los datos posibles. Por esta razón, existen muchos algoritmos diferentes que están diseñados con un tipo específico de datos de entrada en mente o con suposiciones específicas sobre qué tipo de redundancia es probable que contengan los datos sin comprimir. Por lo tanto, las relaciones de compresión tienden a ser más fuertes en documentos y códigos legibles por humanos y máquinas en comparación con los datos binarios entrópicos (bytes aleatorios).

La compresión de datos sin pérdidas se utiliza en muchas aplicaciones. Por ejemplo, se utiliza en el formato de archivo ZIP y en la herramienta GNU gzip. También se usa a menudo como un componente dentro de las tecnologías de compresión de datos con pérdida (por ejemplo, preprocesamiento estéreo conjunto medio / lateral sin pérdida por codificadores de MP3 y otros codificadores de audio con pérdida).

La compresión sin pérdidas se utiliza en casos en los que es importante que los datos originales y descomprimidos sean idénticos, o en los que las desviaciones de los datos originales serían desfavorables. Ejemplos típicos son programas ejecutables, documentos de texto y código fuente. Algunos formatos de archivo de imagen, como PNG o GIF, solo usan compresión sin pérdida, mientras que otros, como TIFF y MNG, pueden usar métodos con pérdida o sin pérdida. Los formatos de audio sin pérdida se utilizan con mayor frecuencia para fines de archivo o producción, mientras que los archivos de audio con pérdida más pequeños se suelen utilizar en reproductores portátiles y en otros casos en los que el espacio de almacenamiento es limitado o no es necesaria la replicación exacta del audio.

Técnicas

La mayoría de los programas de compresión sin pérdidas hacen dos cosas en secuencia: el primer paso genera un modelo estadístico para los datos de entrada, y el segundo paso usa este modelo para asignar datos de entrada a secuencias de bits de tal manera que "probable" (es decir, encontrados con frecuencia) los datos producirán una salida más corta que "improbable" datos.

Los principales algoritmos de codificación utilizados para producir secuencias de bits son la codificación de Huffman (también utilizada por el algoritmo deflate) y la codificación aritmética. La codificación aritmética logra tasas de compresión cercanas a las mejores posibles para un modelo estadístico particular, que viene dada por la entropía de la información, mientras que la compresión Huffman es más simple y rápida pero produce resultados pobres para modelos que manejan probabilidades de símbolos cercanas a 1.

Hay dos formas principales de construir modelos estadísticos: en un modelo estático, los datos se analizan y se construye un modelo, luego este modelo se almacena con los datos comprimidos. Este enfoque es simple y modular, pero tiene la desventaja de que el modelo en sí puede ser costoso de almacenar y también que obliga a usar un solo modelo para comprimir todos los datos y, por lo tanto, funciona mal en archivos que contienen datos heterogéneos. Los modelos adaptables actualizan dinámicamente el modelo a medida que se comprimen los datos. Tanto el codificador como el decodificador comienzan con un modelo trivial, lo que genera una compresión deficiente de los datos iniciales, pero a medida que aprenden más sobre los datos, el rendimiento mejora. Los tipos de compresión más populares usados en la práctica ahora usan codificadores adaptativos.

Los métodos de compresión sin pérdidas pueden clasificarse según el tipo de datos que están diseñados para comprimir. Si bien, en principio, cualquier algoritmo de compresión sin pérdida de propósito general (propósito general, lo que significa que pueden aceptar cualquier cadena de bits) se puede usar en cualquier tipo de datos, muchos no pueden lograr una compresión significativa en los datos que no tienen la forma para la que fueron diseñados para comprimirse. Muchas de las técnicas de compresión sin pérdidas utilizadas para texto también funcionan razonablemente bien para imágenes indexadas.

Multimedia

Estas técnicas aprovechan las características específicas de las imágenes, como el fenómeno común de áreas bidimensionales contiguas de tonos similares. Cada píxel, excepto el primero, se reemplaza por la diferencia con su vecino izquierdo. Esto lleva a que los valores pequeños tengan una probabilidad mucho mayor que los valores grandes. A menudo, esto también se aplica a los archivos de sonido y puede comprimir archivos que contienen principalmente frecuencias bajas y volúmenes bajos. Para las imágenes, este paso se puede repetir llevando la diferencia al píxel superior y, luego, en los videos, se puede tomar la diferencia al píxel del cuadro siguiente.

Una versión jerárquica de esta técnica toma pares vecinos de puntos de datos, almacena su diferencia y suma, y en un nivel superior con menor resolución continúa con las sumas. Esto se llama transformada wavelet discreta. JPEG2000 también usa puntos de datos de otros pares y factores de multiplicación para mezclarlos en la diferencia. Estos factores deben ser números enteros, para que el resultado sea un número entero en todas las circunstancias. Por lo tanto, los valores aumentan, lo que aumenta el tamaño del archivo, pero es de esperar que la distribución de valores sea más puntiaguda.

La codificación adaptativa utiliza las probabilidades de la muestra anterior en la codificación de sonido, del píxel izquierdo y superior en la codificación de imágenes y, además, del cuadro anterior en la codificación de video. En la transformación wavelet, las probabilidades también pasan a través de la jerarquía.

Cuestiones legales históricas

Muchos de estos métodos se implementan en herramientas propietarias y de código abierto, en particular LZW y sus variantes. Algunos algoritmos están patentados en los Estados Unidos y otros países y su uso legal requiere una licencia del titular de la patente. Debido a las patentes sobre ciertos tipos de compresión LZW y, en particular, a las prácticas de licencia del titular de la patente Unisys que muchos desarrolladores consideraron abusivas, algunos defensores del código abierto alentaron a las personas a evitar el uso del formato de intercambio de gráficos (GIF) para comprimir archivos de imágenes fijas en favor de Portable. Gráficos de red (PNG), que combina el algoritmo de deflación basado en LZ77 con una selección de filtros de predicción específicos del dominio. Sin embargo, las patentes de LZW expiraron el 20 de junio de 2003.

Muchas de las técnicas de compresión sin pérdida utilizadas para texto también funcionan razonablemente bien para imágenes indexadas, pero existen otras técnicas que no funcionan para texto típico que son útiles para algunas imágenes (particularmente mapas de bits simples) y otras técnicas que aprovechan de las características específicas de las imágenes (como el fenómeno común de áreas bidimensionales contiguas de tonos similares, y el hecho de que las imágenes en color suelen tener una preponderancia de una gama limitada de colores fuera de los representables en el espacio de color).

Como se mencionó anteriormente, la compresión de sonido sin pérdidas es un área algo especializada. Los algoritmos de compresión de sonido sin pérdida pueden aprovechar los patrones repetitivos que muestra la naturaleza ondulatoria de los datos, esencialmente usando modelos autorregresivos para predecir el "siguiente" valor y codificando la diferencia (con suerte pequeña) entre el valor esperado y los datos reales. Si la diferencia entre los datos predichos y los reales (llamado error) tiende a ser pequeña, entonces ciertos valores de diferencia (como 0, +1, −1, etc. en valores de muestra) se vuelven muy frecuentes, que se pueden explotar codificándolos en pocos bits de salida.

A veces es beneficioso comprimir solo las diferencias entre dos versiones de un archivo (o, en la compresión de video, de imágenes sucesivas dentro de una secuencia). Esto se denomina codificación delta (de la letra griega Δ, que en matemáticas denota una diferencia), pero el término generalmente solo se usa si ambas versiones son significativas fuera de la compresión y la descompresión. Por ejemplo, mientras que el proceso de comprimir el error en el esquema de compresión de audio sin pérdidas mencionado anteriormente podría describirse como una codificación delta de la onda de sonido aproximada a la onda de sonido original, la versión aproximada de la onda de sonido no tiene sentido en ningún otro contexto..

Métodos

Ningún algoritmo de compresión sin pérdidas puede comprimir de manera eficiente todos los datos posibles (consulte la sección Limitaciones a continuación para obtener más detalles). Por esta razón, existen muchos algoritmos diferentes que están diseñados con un tipo específico de datos de entrada en mente o con suposiciones específicas sobre qué tipo de redundancia es probable que contengan los datos sin comprimir.

Algunos de los algoritmos de compresión sin pérdidas más comunes se enumeran a continuación.

Propósito general

• ANS – Entropy encoding, utilizado por LZFSE y Zstandard
• Codificación Aritmética – Codificación entropía
• Burrows–Wheeler transforma la transformación reversible para hacer los datos textuales más compresibles, utilizados por bzip2
• Codificación de Huffman – Codificación de entropía, se combina bien con otros algoritmos
• Compresión Lempel-Ziv (LZ77 y LZ78) – algoritmo basado en diccionario que forma la base de muchos otros algoritmos
  • algoritmo de cadena Lempel–Ziv–Markov (LZMA) – ratio de compresión muy alta, utilizado por 7zip y xz
  • Lempel–Ziv–Storer–Szymanski (LZSS) – Utilizado por WinRAR en tándem con codificación Huffman
    • Deflate – Combina la compresión LZSS con codificación Huffman, utilizada por imágenes ZIP, gzip y PNG
  • Lempel–Ziv–Welch (LZW) – Utilizado por imágenes GIF y Unix compress utilidad
• Predicción por coincidencia parcial (PPM) – Optimizado para comprimir texto plano
• Codificación de longitud de carrera (RLE) – Esquema simple que proporciona una buena compresión de datos que contienen muchas carreras del mismo valor

Sonido

• Adaptive Transform Acoustic Coding (ATRAC)
• Apple Lossless (ALAC – Apple Lossless Audio Codec)
• Codificación sin pérdida de audio (también conocido como MPEG-4 ALS)
• Direct Stream Transfer (DST)
• Dolby TrueHD
• DTS-HD Master Audio
• Free Lossless Audio Codec (FLAC)
• Meridian Lossless Packing (MLP)
• Audio de mono (Monkey's Audio APE)
• MPEG-4 SLS (también conocido como HD-AAC)
• OptimFROG
• Original Sound Quality (OSQ)
• RealPlayer (RealAudio Lossless)
• Shorten (SHN)
• TTA (True Audio Lossless)
• WavPack (WavPack sin pérdida)
• WMA Lossless (Windows Media Lossless)

Gráficos de trama

• AVIF – AOMedia Video 1 Formato de archivo de imagen
• FLIF – Formato de imagen sin perder
• HEIF – Formato de archivo de imagen de alta eficiencia (comprsión sin pérdida o pérdida, utilizando HEVC)
• ILBM – (comprensión sin pérdidas RLE de imágenes de Amiga IFF)
• JBIG2 – (comprensión sin pérdida o pérdida de imágenes de B limitadaW)
• JPEG 2000 – (incluye el método de compresión sin pérdidas a través de Le Gall-Tabatabai 5/3 transformado de onda de entero reversible)
• JPEG-LS – (perdida/near-perdida estándar de compresión)
• JPEG XL – (comprensión sin pérdida o pérdida)
• JPEG XR – anteriormente WMPhoto y HD Photo, incluye un método de compresión sin pérdidas
• LDCT – Transformación Cosine discreta sin pérdida
• PCX – EXchange de pilas
• PDF – Formato de documento portátil (comprensión sin pérdida o pérdida)
• PNG – Gráficos de Redes portátiles
• TGA – Truevision TGA
• TIFF – Etiquetado Formato de Archivo de Imagen (comprensión sin pérdida o pérdida)
• WebP – (comprensión sin pérdida o pérdida de imágenes RGB y RGBA)

Gráficos 3D

• OpenCTM – Compresión sin pérdidas de mallas triangulares 3D

Vídeo

Vea la lista de códecs de video sin pérdida

Criptografía

Los criptosistemas a menudo comprimen los datos (el "texto sin formato") antes del cifrado para mayor seguridad. Cuando se implementa correctamente, la compresión aumenta considerablemente la distancia de unicidad al eliminar patrones que podrían facilitar el criptoanálisis. Sin embargo, muchos algoritmos de compresión ordinarios sin pérdida producen encabezados, contenedores, tablas u otros resultados predecibles que, en cambio, podrían facilitar el criptoanálisis. Por lo tanto, los criptosistemas deben utilizar algoritmos de compresión cuya salida no contenga estos patrones predecibles.

Genética y Genómica

Los algoritmos de compresión genética (que no deben confundirse con los algoritmos genéticos) son la última generación de algoritmos sin pérdidas que comprimen datos (normalmente secuencias de nucleótidos) mediante algoritmos de compresión convencionales y algoritmos específicos adaptados a datos genéticos. En 2012, un equipo de científicos de la Universidad Johns Hopkins publicó el primer algoritmo de compresión genética que no se basa en bases de datos genéticas externas para la compresión. HAPZIPPER se diseñó para los datos de HapMap y logra una compresión de más de 20 veces (reducción del 95 % en el tamaño del archivo), proporcionando una compresión de 2 a 4 veces mejor, mucho más rápido que las principales utilidades de compresión de propósito general.

Los algoritmos de compresión de secuencias genómicas, también conocidos como compresores de secuencias de ADN, exploran el hecho de que las secuencias de ADN tienen propiedades características, como repeticiones invertidas. Los compresores más exitosos son XM y GeCo. Para eucariotas, XM es ligeramente mejor en relación de compresión, aunque para secuencias de más de 100 MB, sus requisitos computacionales no son prácticos.

Ejecutables

Los ejecutables autoextraíbles contienen una aplicación comprimida y un descompresor. Cuando se ejecuta, el descompresor descomprime de forma transparente y ejecuta la aplicación original. Esto se usa especialmente en la codificación de demostración, donde se realizan competencias para demostraciones con límites de tamaño estrictos, tan pequeños como 1k. Este tipo de compresión no se limita estrictamente a ejecutables binarios, sino que también se puede aplicar a scripts, como JavaScript.

Puntos de referencia

Los algoritmos de compresión sin pérdidas y sus implementaciones se prueban de forma rutinaria en puntos de referencia comparativos. Hay una serie de puntos de referencia de compresión más conocidos. Algunos puntos de referencia cubren solo la relación de compresión de datos, por lo que los ganadores en estos puntos de referencia pueden no ser adecuados para el uso diario debido a la baja velocidad de los mejores. Otro inconveniente de algunos puntos de referencia es que sus archivos de datos son conocidos, por lo que algunos programadores pueden optimizar sus programas para obtener el mejor rendimiento en un conjunto de datos en particular. Los ganadores en estos puntos de referencia a menudo provienen de la clase de software de compresión de mezcla de contexto.

Matt Mahoney, en su edición de febrero de 2010 del folleto gratuito Explicación de la compresión de datos, también enumera lo siguiente:

• El Corpus Calgary que data de 1987 ya no es ampliamente utilizado debido a su pequeño tamaño. Matt Mahoney mantuvo el Calgary Compression Challenge, creado y mantenido desde el 21 de mayo de 1996, hasta el 21 de mayo de 2016, por Leonid A. Broukhis.
• El Benchmark de Compresión de Textos Grandes y el Premio Hutter similar utilizan un conjunto de datos XML UTF-8 de Wikipedia recortada.
• El Parámetro de Compresión Genérica, mantenido por Matt Mahoney, prueba la compresión de datos generados por máquinas de Turing aleatorias.
• Sami Runsas (el autor de NanoZip) mantuvo Compression Ratings, un punto de referencia similar a Maximum Compression prueba de archivos múltiples, pero con requisitos mínimos de velocidad. Ofreció la calculadora que permitió al usuario ponderar la importancia de la velocidad y la relación de compresión. Los programas superiores eran bastante diferentes debido al requisito de velocidad. En enero de 2010, el programa superior fue NanoZip seguido por FreeArc, CCM, flashzip y 7-Zip.
• El parámetro Monster of Compression de Nania Francesco Antonio probó la compresión en 1Gb de datos públicos con un límite de tiempo de 40 minutos. En diciembre de 2009, el archivador de categoría superior fue NanoZip 0.07a y el compresor de archivo único de categoría superior fue ccmx 1.30c.

El sitio web de Compression Ratings publicó un resumen gráfico de la "frontera" en relación de compresión y tiempo.

La herramienta de análisis de compresión es una aplicación de Windows que permite a los usuarios finales comparar las características de rendimiento de las implementaciones de transmisión de LZF4, Deflate, ZLIB, GZIP, BZIP2 y LZMA utilizando sus propios datos. Produce mediciones y gráficos con los que los usuarios pueden comparar la velocidad de compresión, la velocidad de descompresión y la relación de compresión de los diferentes métodos de compresión y examinar cómo el nivel de compresión, el tamaño del búfer y las operaciones de limpieza afectan los resultados.

Limitaciones

Los algoritmos de compresión de datos sin pérdida (que no adjuntan etiquetas de identificación de compresión a sus conjuntos de datos de salida) no pueden garantizar la compresión para todos los conjuntos de datos de entrada. En otras palabras, para cualquier algoritmo de compresión de datos sin pérdidas, habrá un conjunto de datos de entrada que no se reducirá cuando el algoritmo los procese, y para cualquier algoritmo de compresión de datos sin pérdidas que reduzca al menos un archivo, habrá al menos un archivo que hace más grande. Esto se demuestra fácilmente con matemáticas elementales usando un argumento de conteo llamado principio del casillero, como sigue:

• Supongamos que cada archivo está representado como una cadena de bits de cierta longitud arbitraria.
• Supongamos que hay un algoritmo de compresión que transforma cada archivo en un archivo de salida que no es más que el archivo original, y que al menos un archivo será comprimido en un archivo de salida que es más corto que el archivo original.
• Vamos M ser el menor número de tal que hay un archivo F con longitud M bits que comprimen algo más corto. Vamos N ser la longitud (en bits) de la versión comprimida de F.
• Porque... N.M, cada uno archivo de longitud N mantiene su tamaño durante la compresión. Hay 2^N tales archivos posibles. Juntos F, esto hace 2^N+1 archivos que todo se comprime en uno de los 2^N archivos de longitud N.
• Pero 2^N es más pequeño que 2^N+1, así que por el principio de la paloma debe haber algún archivo de longitud N que es simultáneamente la salida de la función de compresión en dos entradas diferentes. Ese archivo no puede descomprimirse de forma fiable (¿cuál de los dos originales debería ese rendimiento?), lo que contradice la suposición de que el algoritmo era infalible.
• Por lo tanto, debemos concluir que nuestra hipótesis original (que la función de compresión ya no hace archivo) es necesariamente falsa.

La mayoría de los algoritmos de compresión prácticos proporcionan un "escape" instalación que puede desactivar la codificación normal para archivos que se volverían más largos al ser codificados. En teoría, solo se requiere un bit adicional para decirle al decodificador que la codificación normal se ha desactivado para toda la entrada; sin embargo, la mayoría de los algoritmos de codificación usan al menos un byte completo (y normalmente más de uno) para este propósito. Por ejemplo, los archivos comprimidos desinflados nunca necesitan crecer más de 5 bytes por cada 65 535 bytes de entrada.

De hecho, si consideramos archivos de longitud N, si todos los archivos fueran igualmente probables, entonces para cualquier compresión sin pérdida que reduzca el tamaño de algún archivo, la longitud esperada de un archivo comprimido (promediada sobre todos los archivos posibles de longitud N) necesariamente debe ser mayor que N. Entonces, si no sabemos nada acerca de las propiedades de los datos que estamos comprimiendo, es mejor que no los comprimamos en absoluto. Un algoritmo de compresión sin pérdidas es útil solo cuando es más probable que comprimamos ciertos tipos de archivos que otros; entonces el algoritmo podría diseñarse para comprimir mejor esos tipos de datos.

Por lo tanto, la lección principal del argumento no es que uno se arriesgue a grandes pérdidas, sino simplemente que no siempre se puede ganar. Elegir un algoritmo siempre significa implícitamente seleccionar un subconjunto de todos los archivos que serán útilmente más cortos. Esta es la razón teórica por la que necesitamos tener diferentes algoritmos de compresión para diferentes tipos de archivos: no puede haber ningún algoritmo que sea bueno para todo tipo de datos.

El "truco" que permite que los algoritmos de compresión sin pérdida, utilizados en el tipo de datos para los que fueron diseñados, compriman consistentemente dichos archivos a una forma más corta es que los archivos en los que los algoritmos están diseñados para actuar tienen alguna forma de redundancia fácilmente modelada que el algoritmo está diseñado para eliminar y, por lo tanto, pertenecen al subconjunto de archivos que ese algoritmo puede acortar, mientras que otros archivos no se comprimirían o incluso se agrandarían. Por lo general, los algoritmos están ajustados específicamente a un tipo de archivo en particular: por ejemplo, los programas de compresión de audio sin pérdidas no funcionan bien en archivos de texto y viceversa.

En particular, los archivos de datos aleatorios no se pueden comprimir de manera consistente mediante ningún algoritmo de compresión de datos sin pérdida concebible; de hecho, este resultado se usa para definir el concepto de aleatoriedad en la complejidad de Kolmogorov.

Probablemente es imposible crear un algoritmo que pueda comprimir cualquier dato sin pérdidas. Si bien ha habido muchas afirmaciones a lo largo de los años de empresas que lograron "compresión perfecta" donde un número arbitrario N de bits aleatorios siempre se puede comprimir a N − 1 bits, este tipo de afirmaciones se pueden descartar de forma segura sin siquiera mirar más detalles con respecto a la supuesta esquema de compresión. Tal algoritmo contradice las leyes fundamentales de las matemáticas porque, si existiera, podría aplicarse repetidamente para reducir sin pérdidas cualquier archivo a la longitud 1.

Por otro lado, también se ha demostrado que no existe un algoritmo para determinar si un archivo es incompresible en el sentido de la complejidad de Kolmogorov. Por lo tanto, es posible que cualquier archivo en particular, incluso si parece aleatorio, puede comprimirse significativamente, incluido el tamaño del descompresor. Un ejemplo son los dígitos de la constante matemática pi, que parecen aleatorios pero pueden generarse con un programa muy pequeño. Sin embargo, aunque no se puede determinar si un archivo en particular es incompresible, un simple teorema sobre las cadenas incompresibles muestra que más del 99 % de los archivos de cualquier longitud determinada no pueden comprimirse en más de un byte (incluido el tamaño del descompresor).

Antecedentes matemáticos

Abstractamente, un algoritmo de compresión puede verse como una función en secuencias (normalmente de octetos). La compresión es exitosa si la secuencia resultante es más corta que la secuencia original (y las instrucciones para el mapa de descompresión). Para que un algoritmo de compresión no tenga pérdidas, el mapa de compresión debe formar una inyección desde "simple" a "comprimido" secuencias de bits. El principio del casillero prohíbe una biyección entre la colección de secuencias de longitud N y cualquier subconjunto de la colección de secuencias de longitud N−1. Por lo tanto, no es posible producir un algoritmo sin pérdidas que reduzca el tamaño de cada secuencia de entrada posible.

Puntos de aplicación en la teoría de la compresión real

Los diseñadores de algoritmos de compresión reales aceptan que los flujos de información de alta entropía no se pueden comprimir y, en consecuencia, incluyen funciones para detectar y manejar esta condición. Una forma obvia de detección es aplicar un algoritmo de compresión sin procesar y probar si su salida es más pequeña que su entrada. A veces, la detección se realiza mediante heurística; por ejemplo, una aplicación de compresión puede considerar archivos cuyos nombres terminan en ".zip", ".arj" o ".lha" incompresible sin ninguna detección más sofisticada. Una forma común de manejar esta situación es citar la entrada o partes no comprimibles de la entrada en la salida, minimizando la sobrecarga de compresión. Por ejemplo, el formato de datos zip especifica el 'método de compresión' de 'Almacenado' para archivos de entrada que se han copiado en el archivo palabra por palabra.

El desafío del millón de dígitos aleatorios

Mark Nelson, en respuesta a las afirmaciones de "magia" algoritmos de compresión que aparecen en comp.compression, ha construido un archivo binario de 415,241 bytes de contenido altamente entrópico, y ha lanzado un desafío público de $100 a cualquiera para que escriba un programa que, junto con su entrada, sea más pequeño que los datos binarios proporcionados pero que sea capaz de reconstituirlo sin error. Mike Goldman lanzó un desafío similar, con $ 5,000 como recompensa.