Tengo un archivo que contiene números binarios ordenados de a 2 n - 1 :
0000000000
0000000001
0000000010
0000000011
0000000100
...
1111111111
7z no comprimió este archivo de manera muy eficiente (para n = 20, 22 MB se comprimieron a 300 kB).
¿Existen algoritmos que puedan reconocer una estructura de datos muy simple y comprimir el archivo a varios bytes? También quiero saber qué área de CS o teoría de la información estudia dichos algoritmos inteligentes. "AI" sería demasiado amplio, sugiera palabras clave más concretas.
La noción de simetría debería desempeñar un papel fundamental en la compresión de datos, pero las consultas de búsqueda "simetría en la compresión de datos" y "teoría de grupos en la compresión de datos" sorprendentemente no devuelven casi nada relevante.
information-theory
data-compression
DSblizzard
fuente
fuente
Respuestas:
Este parece ser un caso de uso claro para la compresión delta . Si se conoce a priori, esto es trivial: almacene el primer número literalmente, y para cada número siguiente almacene solo la diferencia con el anterior. En su caso, esto le darán
Esto se puede almacenar con una codificación de longitud de ejecución simple en el espacio , ya que solo hay grupos O ( 1 ) (es decir, dos) de deltas diferentes.O(n) O(1)
Si no se conoce , lo más simple sería una búsqueda de fuerza bruta para el tamaño de palabra para el cual esta representación delta / longitud de ejecución sale más corta. Quizás solo haga esta búsqueda de √ elegido al azarn Trozos de tamaño N , para amortizar los gastos generales de encontrarnmientras se conserva una buena fiabilidad.N−−√ n
A diferencia de la propuesta de "todo o nada" de DW, la compresión delta con codificación de longitud de ejecución en realidad puede proporcionar relaciones de compresión sensibles para algunos tipos simples de contenido del mundo real, como el audio de baja resolución. (Por lo tanto, es adecuado para compresión de audio de baja calidad, muy baja latencia y baja potencia).
fuente
Claro, por supuesto que hay algoritmos. Aquí está mi algoritmo:
Si no, escriba 1 bit, luego escriba la compresión 7z del archivo.
Esto es extremadamente eficiente para archivos de esa estructura particular.
El punto es: no hay almuerzo gratis en la compresión de datos. Es posible que pueda crear un algoritmo de compresión que comprima bien un tipo de archivo, a costa de comprimir otros peor. Pero, si sabe a priori algo sobre la naturaleza de los archivos que comprimirá, puede optimizar su algoritmo para ese tipo particular de archivo.
El área es "compresión de datos". Vea nuestra etiqueta de compresión de datos y lea libros de texto sobre compresión de datos.
fuente
Cualquier cosa que use una BWT (transformación de Burrows – Wheeler) debería ser capaz de comprimirlo bastante bien.
Mi prueba rápida de Python:
(Los números aquí son 'first_compressor second_compressor time_taken bytes_out')
(BWT tomado de aquí )
Esto sigue siendo 'no solo unos pocos bytes', pero es mucho mejor que solo gzip solo. BWT + bz2 se reduce a 237 bytes desde 1114111 para una entrada de 16 bits, por ejemplo.
Por desgracia, los BWT son demasiado lentos y requieren mucha memoria para muchas aplicaciones. Especialmente dado que esta es una implementación ingenua en Python: en mi máquina me quedo sin RAM antes de 2 ** 20.
Con Pypy pude ejecutar la entrada completa de 2 ** 20, y la comprime a 2611 bytes con un BWT seguido de bz2. Pero usar más de 3 minutos y alcanzar un máximo de más de 4 GB de RAM ...
También desafortunadamente, este enfoque sigue siendo el espacio de salida O (2 ^ n), al parecer, al menos a partir del ajuste de curva 1..20.
fuente
eval
haciendo:for first in (bwt_c, nothing, lzma, zlib, gzip, bz2):
yfOut = first.compress(inputData)
.4 times block size
memoria (por ejemplo, ~ 4 MB para esto) y a velocidades de>10 MB/s
(soy el autor de una biblioteca de bwt / algoritmo de compresión) que es bastante útil para muchas aplicaciones. Tenga en cuenta que incluso gzip produce muy buenos resultados de compresión. Gracias por compartir No conozco ninguna investigación sobre el uso de bwt dos veces.La codificación PNG hace exactamente lo que quieres. Funciona también con datos de la vida real, no solo con datos extremadamente organizados.
En PNG, cada fila está codificada con un filtro, de los cuales se especifican 4. Una de ellas es "codificar este píxel como la diferencia entre su valor y el valor del píxel que está encima de él". Después de filtrar, los datos se comprimen usando DEFLATE.
Este filtrado es un ejemplo específico de la codificación Delta mencionada por leftaroundabout en su respuesta, excepto que, en lugar de seguirlo con la codificación de longitud de ejecución, lo sigue con el algoritmo DEFLATE más poderoso. Alcanza el mismo objetivo, solo DEFLATE manejará una mayor variedad de entradas sin dejar de proporcionar las relaciones de compresión deseables.
Otra herramienta que a menudo se usa en datos científicos en los que el filtro simple + DEFLATE no es tan efectivo es la codificación RICE. En RICE, toma un bloque de valores y genera todos los bits más significativos primero, luego todos los bits 2º más significativos, hasta los bits menos significativos. Luego comprime el resultado. Para sus datos que no serán tan efectivos como el filtrado de estilo PNG (porque sus datos son perfectos para el filtrado PNG), pero para muchos datos científicos tiende a dar buenos resultados. En muchos datos científicos, vemos que el bit más significativo tiende a cambiar lentamente, mientras que el menos significativo es casi aleatorio. Esto separa los datos altamente predecibles de los datos altamente entrópicos.
fuente
Cualquier algoritmo práctico que busque estructuras específicas se limitaría solo a las estructuras codificadas en él. Podrías parchear 7z para reconocer esta secuencia específica, pero ¿con qué frecuencia ocurrirá esta estructura específica en la vida real? No con la frecuencia suficiente para garantizar el tiempo que lleva verificar las entradas para esta entrada.
Dejando de lado las practicidades, uno puede concebir el compresor perfecto como un algoritmo que intenta construir el programa más corto que produce una salida dada. No hace falta decir que no hay formas prácticas de hacerlo. Incluso si probó una enumeración de fuerza bruta de todos los programas posibles y verificó si produjeron el resultado deseado ( no una idea completamente loca ), se encontrará con el problema de detención , lo que significa que tendrá que abortar las ejecuciones de prueba después de un cierto número de pasos de ejecución, antes de saber si este programa definitivamente no puede producir el resultado deseado.
El árbol de búsqueda para un enfoque de fuerza bruta de este tipo crece exponencialmente con la longitud del programa y no es práctico para todos, excepto para los programas más simples (algo así como 5-7 instrucciones de largo).
fuente
Las relaciones de compresión dependen completamente del descompresor objetivo. Si el descompresor no puede decodificar números secuenciales de 4 bytes de manera más compacta que 4 bytes por número, entonces usted es SOL.
Hay varias cosas que permitirían la codificación de números secuenciales. Por ejemplo, una codificación diferencial. Toma n bytes a la vez y luego toma la diferencia o el xor de los bits y luego comprime el resultado. Esto agrega 4 opciones aquí para probar cada conteo de bytes: identidad
a'[i] = a[i]
; diferenciaa'[i] = a[i-1]-a[i]
; diferencia inversaa'[i] = a[i]-a[i-1]
; y el xora'[i] = a[i]^a[i-1]
. Eso significa agregar 2 bits para seleccionar los métodos y un recuento de bytes para 3 de las 4 opciones.Sin embargo, no todos los datos son una secuencia de registros de longitud fija. La codificación diferencial no tiene sentido para eso (a menos que el compresor pueda probar empíricamente que funciona para un poco de datos).
fuente