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érdida es posible porque la mayoría de los datos del mundo real presentan redundancia estadística . [1] 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).
Mediante el funcionamiento del principio del palomar , ningún algoritmo de compresión sin pérdidas puede reducir el tamaño de todos los datos posibles: algunos datos se alargarán al menos en un símbolo o bit.
Los algoritmos de compresión suelen ser eficaces para documentos legibles por humanos y máquinas y no pueden reducir el tamaño de datos aleatorios que no contienen redundancia . Existen diferentes algoritmos que están diseñados ya sea con un tipo específico de datos de entrada en mente o con suposiciones específicas sobre qué tipos de redundancia es probable que contengan los datos sin comprimir.
La compresión de datos sin pérdida se utiliza en muchas aplicaciones. Por ejemplo, se utiliza en el formato de archivo ZIP y en la herramienta GNU gzip . También se utiliza a menudo como un componente dentro de las tecnologías de compresión de datos con pérdida (por ejemplo, preprocesamiento estéreo de unión media/lateral sin pérdida mediante codificadores de MP3 y otros codificadores de audio con pérdida). [2]
La compresión sin pérdida se utiliza en casos en los que es importante que los datos originales y descomprimidos sean idénticos, o cuando las desviaciones de los datos originales serían desfavorables. Los ejemplos más comunes son los programas ejecutables, los documentos de texto y el código fuente. Algunos formatos de archivos de imagen, como PNG o GIF , utilizan solo compresión sin pérdida, mientras que otros, como TIFF y MNG, pueden utilizar métodos sin pérdida o con 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 utilizan normalmente en reproductores portátiles y en otros casos en los que el espacio de almacenamiento es limitado o la replicación exacta del audio no es necesaria.
La mayoría de los programas de compresión sin pérdida hacen dos cosas en secuencia: el primer paso genera un modelo estadístico para los datos de entrada y el segundo paso utiliza este modelo para mapear los datos de entrada a secuencias de bits de tal manera que los datos "probables" (es decir, los que se encuentran con frecuencia) producirán una salida más corta que los datos "improbables".
Los algoritmos de codificación primarios 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 se da por la entropía de la información , mientras que la compresión de Huffman es más simple y rápida, pero produce resultados deficientes para modelos que tratan con probabilidades de símbolos cercanas a 1.
Existen dos formas principales de construir modelos estadísticos: en un modelo estático , se analizan los datos y se construye un modelo, que luego 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 de que obliga a utilizar un único modelo para todos los datos que se comprimen, por lo que su rendimiento es deficiente en archivos que contienen datos heterogéneos. Los modelos adaptativos 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 produce una mala compresión 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 que se utilizan en la práctica ahora utilizan codificadores adaptativos.
Los métodos de compresión sin pérdida se pueden clasificar 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 significa que puede aceptar cualquier cadena de bits) se puede utilizar en cualquier tipo de datos, muchos no pueden lograr una compresión significativa en datos que no tienen el formato para el que fueron diseñados para comprimir. Muchas de las técnicas de compresión sin pérdida que se utilizan para texto también funcionan razonablemente bien para imágenes indexadas .
Estas técnicas aprovechan las características específicas de las imágenes, como el fenómeno común de las áreas bidimensionales contiguas de tonos similares. Cada píxel, excepto el primero, se reemplaza por la diferencia con su vecino izquierdo. Esto hace que los valores pequeños tengan una probabilidad mucho mayor que los valores grandes. Esto también se suele aplicar a los archivos de sonido y puede comprimir archivos que contienen principalmente frecuencias bajas y volúmenes bajos. En el caso de las imágenes, este paso se puede repetir tomando la diferencia del píxel superior y, luego, en los vídeos, se puede tomar la diferencia con el píxel del siguiente fotograma.
Una versión jerárquica de esta técnica toma pares de puntos de datos vecinos, almacena su diferencia y suma y, en un nivel superior con una resolución más baja, continúa con las sumas. Esto se llama transformada wavelet discreta . JPEG2000 utiliza además puntos de datos de otros pares y factores de multiplicación para mezclarlos en la diferencia. Estos factores deben ser números enteros, de modo que el resultado sea un número entero en todas las circunstancias. Por lo tanto, los valores se incrementan, lo que aumenta el tamaño del archivo, pero es de esperar que la distribución de los valores sea más uniforme. [ cita requerida ]
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 imagen y, además, del fotograma anterior en la codificación de vídeo. En la transformación wavelet, las probabilidades también se transmiten a través de la jerarquía. [3]
Muchos de estos métodos se implementan en herramientas de código abierto y propietarias, 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 licenciamiento del titular de la patente Unisys que muchos desarrolladores consideraron abusivas, algunos defensores del código abierto alentaron a la gente a evitar el uso del formato de intercambio de gráficos (GIF) para comprimir archivos de imágenes fijas en favor de Portable Network Graphics (PNG), que combina el algoritmo deflate 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. [4]
Muchas de las técnicas de compresión sin pérdida utilizadas para texto también funcionan razonablemente bien para imágenes indexadas , pero hay 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 las características específicas de las imágenes (como el fenómeno común de áreas 2-D contiguas de tonos similares y el hecho de que las imágenes en color generalmente tienen una preponderancia de una gama limitada de colores de los que se pueden representar en el espacio de color).
Como se mencionó anteriormente, la compresión de sonido sin pérdida 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 , utilizando modelos autorregresivos para predecir el "próximo" 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 (llamada error ) tiende a ser pequeña, entonces ciertos valores de diferencia (como 0, +1, −1, etc. en valores de muestra) se vuelven muy frecuentes, lo que se puede aprovechar codificándolos en unos pocos bits de salida.
A veces resulta beneficioso comprimir solo las diferencias entre dos versiones de un archivo (o, en el caso de la compresión de vídeo , 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 normalmente solo se utiliza si ambas versiones son significativas fuera de la compresión y la descompresión. Por ejemplo, si bien el proceso de compresión del error en el esquema de compresión de audio sin pérdida mencionado anteriormente podría describirse como 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 es significativa en ningún otro contexto.
Ningún algoritmo de compresión sin pérdida puede comprimir de manera eficiente todos los datos posibles . Por este motivo, existen muchos algoritmos diferentes que están diseñados ya sea con un tipo específico de datos de entrada en mente o con suposiciones específicas sobre qué tipos de redundancia es probable que contengan los datos sin comprimir.
A continuación se enumeran algunos de los algoritmos de compresión sin pérdida más comunes.
compress y utilidades de Unix.Ver lista de códecs de vídeo sin pérdida
Los criptosistemas suelen comprimir los datos (el "texto sin formato") antes de cifrarlos para mayor seguridad. Cuando se implementa correctamente, la compresión aumenta en gran medida la distancia de unicidad al eliminar patrones que podrían facilitar el criptoanálisis . [9] Sin embargo, muchos algoritmos de compresión sin pérdida ordinarios producen encabezados, contenedores, tablas u otros resultados predecibles que podrían facilitar el criptoanálisis. Por lo tanto, los criptosistemas deben utilizar algoritmos de compresión cuyo resultado no contenga estos patrones predecibles.
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érdida que comprimen datos (normalmente secuencias de nucleótidos) utilizando tanto algoritmos de compresión convencionales como 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 depende de bases de datos genéticas externas para la compresión. HAPZIPPER fue diseñado para 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. [10]
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 las repeticiones invertidas. Los compresores más exitosos son XM y GeCo. [11] Para los eucariotas, XM es ligeramente mejor en cuanto a la relación de compresión, aunque para secuencias mayores de 100 MB sus requisitos computacionales son poco prácticos.
Los ejecutables autoextraíbles contienen una aplicación comprimida y un descompresor. Cuando se ejecutan, el descompresor descomprime y ejecuta de forma transparente la aplicación original. Esto se utiliza especialmente en la codificación de demostración , donde se realizan competiciones para demos con límites de tamaño estrictos, tan pequeños como 1k . Este tipo de compresión no se limita estrictamente a los ejecutables binarios, sino que también se puede aplicar a scripts, como JavaScript .
Los algoritmos de compresión sin pérdida y sus implementaciones se prueban de forma rutinaria en pruebas comparativas cara a cara . Hay una serie de pruebas comparativas de compresión más conocidas. Algunas pruebas comparativas cubren solo la relación de compresión de datos , por lo que los ganadores en estas pruebas comparativas pueden no ser adecuados para el uso diario debido a la baja velocidad de los mejores. Otro inconveniente de algunas pruebas comparativas es que sus archivos de datos son conocidos, por lo que algunos desarrolladores de programas pueden optimizar sus programas para obtener el mejor rendimiento en un conjunto de datos en particular. Los ganadores en estas pruebas comparativas 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 Data Compression Explained , enumera además lo siguiente: [12]
El sitio web Compression Ratings publicó un resumen gráfico de la "frontera" en relación de compresión y tiempo. [15]
La herramienta de análisis de compresión [16] es una aplicación de Windows que permite a los usuarios finales evaluar las características de rendimiento de las implementaciones de streaming 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 vaciado afectan los resultados.
Los algoritmos de compresión de datos sin pérdida no pueden garantizar la compresión de todos los conjuntos de datos de entrada. En otras palabras, para cualquier algoritmo de compresión de datos sin pérdida, habrá un conjunto de datos de entrada que no se hace más pequeño cuando es procesado por el algoritmo, y para cualquier algoritmo de compresión de datos sin pérdida que haga que al menos un archivo sea más pequeño, habrá al menos un archivo que haga más grande. Esto se demuestra fácilmente con matemáticas elementales utilizando un argumento de conteo llamado principio del palomar , de la siguiente manera: [17] [18]
La mayoría de los algoritmos de compresión prácticos proporcionan una función de "escape" que puede desactivar la codificación normal de los archivos que se volverían más largos al ser codificados. En teoría, solo se requiere un único bit adicional para indicar 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 utilizan al menos un byte completo (y normalmente más de uno) para este propósito. Por ejemplo, los archivos comprimidos deflate 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) debe ser necesariamente mayor que N. [19] Por lo tanto, si no sabemos nada sobre las propiedades de los datos que estamos comprimiendo, bien podríamos no comprimirlos en absoluto. Un algoritmo de compresión sin pérdida 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 principal lección del argumento no es que se corre el riesgo de 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 se volverán útiles si se acortan. 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 todos los tipos 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 sistemáticamente dichos archivos a un formato más corto es que los archivos sobre los que están diseñados para actuar los algoritmos tienen algún tipo de redundancia 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. Los algoritmos generalmente están ajustados de manera bastante específica a un tipo particular de archivo: por ejemplo, los programas de compresión de audio sin pérdida no funcionan bien en archivos de texto y viceversa.
En particular, los archivos de datos aleatorios no pueden comprimirse de manera consistente mediante ningún algoritmo de compresión de datos sin pérdida concebible; de hecho, este resultado se utiliza para definir el concepto de aleatoriedad en la complejidad de Kolmogorov . [20]
Es imposible crear un algoritmo que pueda comprimir datos sin pérdida. Si bien a lo largo de los años ha habido muchas afirmaciones de empresas que han logrado una "compresión perfecta" en la que una cantidad arbitraria N de bits aleatorios siempre se puede comprimir a N − 1 bits, este tipo de afirmaciones se pueden descartar sin siquiera analizar más detalles sobre el supuesto esquema de compresión. Un algoritmo de este tipo contradice las leyes fundamentales de las matemáticas porque, si existiera, se podría aplicar repetidamente para reducir sin pérdida cualquier archivo a una longitud de 1. [18]
Por otra parte, también se ha demostrado [21] que no existe ningún 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, pueda estar significativamente comprimido, incluso incluyendo el tamaño del descompresor. Un ejemplo son los dígitos de la constante matemática pi , que parecen aleatorios pero pueden ser generados por un programa muy pequeño. Sin embargo, aunque no se puede determinar si un archivo en particular es incompresible, un teorema simple sobre cadenas incompresibles muestra que más del 99% de los archivos de cualquier longitud dada no pueden comprimirse en más de un byte (incluyendo el tamaño del descompresor).
De manera abstracta, un algoritmo de compresión puede verse como una función de 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 sea sin pérdidas , el mapa de compresión debe formar una inyección de secuencias de bits "simples" a "comprimidas". El principio del palomar 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. [22]
Los diseñadores de algoritmos de compresión reales aceptan que los flujos de alta entropía de información 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 que los archivos cuyos nombres terminan en ".zip", ".arj" o ".lha" no se pueden comprimir sin una detección más sofisticada. Una forma común de manejar esta situación es citar la entrada, o las 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 los archivos de entrada que se han copiado en el archivo textualmente. [23]
Mark Nelson, en respuesta a las afirmaciones de que aparecen algoritmos de compresión "mágicos" en comp.compression, ha construido un archivo binario de 415.241 bytes con un contenido altamente entrópico y ha lanzado un desafío público de 100 dólares a cualquiera que escriba un programa que, junto con su entrada, sea más pequeño que los datos binarios que le ha proporcionado, pero que sea capaz de reconstruirlos sin errores. [24] Mike Goldman lanzó un desafío similar, con una recompensa de 5.000 dólares. [25]
{{cite book}}: Mantenimiento de CS1: falta la ubicación del editor ( enlace )Teorema 2.6 La función no es parcialmente recursiva.
