La compresión sin pérdidas 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 presentan redundancia estadística . [1] Por el contrario, la compresión con pérdida permite la reconstrucción sólo 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 la operación del principio del casillero , 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 byte.
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 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é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 utiliza a menudo como 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érdidas mediante codificadores de MP3 y otros codificadores de audio con pérdida). [2]
La compresión sin pérdidas se utiliza en los 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. Ejemplos comunes son programas ejecutables, documentos de texto y código fuente. Algunos formatos de archivos de imagen, como PNG o GIF , utilizan únicamente compresión sin pérdidas, mientras que otros, como TIFF y MNG, pueden utilizar métodos sin pérdidas 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 generalmente se usan en reproductores portátiles y en otros casos donde 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érdidas 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 asignar datos de entrada a secuencias de bits de tal manera que los datos "probables" (es decir, encontrados con frecuencia) producirá resultados más cortos que los datos "improbables".
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 de Huffman es más simple y rápida pero produce resultados pobres para modelos que tratan con 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 de que obliga a utilizar un único modelo para todos los datos que se comprimen, por lo que tiene un rendimiento 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 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 utilizados en la práctica ahora utilizan codificadores adaptativos.
Los métodos de compresión sin pérdidas se pueden clasificar según el tipo de datos para los que están diseñados. Si bien, en principio, cualquier algoritmo de compresión sin pérdidas de 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 datos que no tienen la forma para la cual fueron diseñados para comprimir. Muchas de las técnicas de compresión sin pérdidas utilizadas 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 á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 archivos de sonido y puede comprimir archivos que contienen principalmente frecuencias bajas y volúmenes bajos. Para imágenes, este paso se puede repetir llevando la diferencia al píxel superior y luego, en 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 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 además utiliza 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. [ cita necesaria ]
La codificación adaptativa utiliza las probabilidades de la muestra anterior en codificación de sonido, del píxel izquierdo y superior en codificación de imagen y, además, del cuadro anterior en codificación de vídeo. En la transformación wavelet, las probabilidades también pasan a través de la jerarquía.
Muchos de estos métodos se implementan en herramientas patentadas y de código abierto, particularmente LZW y sus variantes. Algunos algoritmos están patentados en los Estados Unidos y otros países y su uso legal requiere una licencia por parte del titular de la patente. Debido a las patentes sobre ciertos tipos de compresión LZW y, en particular, a las prácticas de concesión de licencias por parte 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 del formato portátil. Network Graphics (PNG), que combina el algoritmo de desinflado 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. [3]
Muchas de las técnicas de compresión sin pérdidas utilizadas para texto también funcionan razonablemente bien para imágenes indexadas , pero existen otras técnicas que no funcionan para texto típico y que son útiles para algunas imágenes (particularmente mapas de bits simples) y otras técnicas que aprovechan las ventajas específicas. características 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 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érdidas pueden aprovechar los patrones repetidos mostrados por la naturaleza ondulatoria de los datos - usando modelos autorregresivos para predecir el "siguiente" valor y codificando la diferencia (con suerte pequeña) entre el valor esperado y el real. datos. Si la diferencia entre los datos pronosticados 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, lo que puede explotarse codificándolos. en unos pocos bits de salida.
A veces resulta beneficioso comprimir sólo las diferencias entre dos versiones de un archivo (o, en la compresión de vídeo , de imágenes sucesivas dentro de una secuencia). Esto se llama codificación delta (de la letra griega Δ , que en matemáticas denota una diferencia), pero el término normalmente solo se usa si ambas versiones son significativas fuera de la compresión y descompresión. Por ejemplo, si bien el proceso de compresión del 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 significado en ningún otro contexto. .
Ningún algoritmo de compresión sin pérdidas puede comprimir eficientemente 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é tipos 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.
compress y utilidad de UnixVer lista de códecs de vídeo sin pérdidas
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 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érdidas ordinarios producen encabezados, envoltorios, tablas u otros resultados predecibles que, en cambio, podrían facilitar el criptoanálisis. Por tanto, los criptosistemas deben utilizar algoritmos de compresión cuya salida 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érdidas 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 y mucho más rápido que las principales utilidades de compresión de uso 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 repeticiones invertidas. Los compresores de mayor éxito son XM y GeCo. [11] 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.
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 utiliza especialmente en la codificación de demostraciones , donde se llevan a cabo competiciones 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 .
Los algoritmos de compresión sin pérdidas y sus implementaciones se prueban de forma rutinaria en comparativas comparativas . Hay varios 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 de mejor rendimiento. Otro inconveniente de algunos puntos de referencia es que se conocen sus archivos de datos, por lo que algunos escritores de programas 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 , 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 comparar 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 lavado 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 el algoritmo lo procesa, y para cualquier algoritmo de compresión de datos sin pérdida que reduzca al menos un archivo, habrá al menos un archivo que agranda. Esto se prueba fácilmente con matemáticas elementales utilizando un argumento de conteo llamado principio de casillero , 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 archivos que se alargarían si se codificaran. En teoría, sólo se requiere un bit adicional para indicarle 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 fin. 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érdidas 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 necesariamente ser mayor que N. [19] 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 sólo 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 que se desprende del argumento no es que uno se arriesga a sufrir 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. Ésta 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 a los algoritmos de compresión sin pérdidas, utilizados según el tipo de datos para el que fueron diseñados, comprimir consistentemente dichos archivos a una forma más corta es que todos los archivos sobre los que están diseñados los algoritmos tienen alguna forma de redundancia fácilmente modelable que el algoritmo está diseñado para eliminar y, por lo tanto, pertenecer al subconjunto de archivos que ese algoritmo puede acortar, mientras que otros archivos no se comprimen o incluso se hacen más grandes. Los algoritmos generalmente se ajustan específicamente a un tipo particular de archivo: 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 pueden comprimirse consistentemente mediante ningún algoritmo de compresión de datos sin pérdidas imaginable; de hecho, este resultado se utiliza para definir el concepto de aleatoriedad en la complejidad de Kolmogorov . [20]
Es demostrablemente 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 han logrado una "compresión perfecta" en la que 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 sobre el supuesto esquema de compresión. Un algoritmo de este tipo contradice las leyes fundamentales de las matemáticas porque, si existiera, podría aplicarse repetidamente para reducir sin pérdidas cualquier archivo a una longitud de 1. [18]
Por otro lado, 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 comprimirse significativamente, incluso incluyendo el tamaño del descompresor. Un ejemplo son los dígitos de la constante matemática pi , que parecen aleatorios pero pueden generarse mediante 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 determinada no se pueden comprimir en más de un byte (incluido el tamaño del descompresor).
De manera abstracta, un algoritmo de compresión puede verse como una función sobre secuencias (normalmente de octetos). La compresión tiene éxito 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 de secuencias de bits "simples" a "comprimidas". El principio de 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. [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 formato y probar si su salida es más pequeña que su entrada. A veces, la detección se realiza mediante heurísticas ; por ejemplo, una aplicación de compresión puede considerar archivos cuyos nombres terminan en ".zip", ".arj" o ".lha" como no comprimibles sin una 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 los archivos de entrada que se han copiado en el archivo palabra por palabra. [23]
Mark Nelson, en respuesta a las afirmaciones de algoritmos de compresión "mágicos" que aparecen en comp.compression, ha construido un archivo binario de 415.241 bytes de contenido altamente entrópico y lanzó un desafío público de 100 dólares a cualquiera para que escribiera un programa que, junto con su entrada , sería más pequeño que los datos binarios proporcionados pero podría reconstituirlos sin errores. [24] Mike Goldman lanzó un desafío similar, con 5.000 dólares como recompensa. [25]
{{cite book}}: CS1 maint: location missing publisher (link){{cite book}}: |journal=ignorado ( ayuda )Teorema 2.6 La función no es recursiva parcial.
