Compresión eficiente de datos binarios simples.

27

Tengo un archivo que contiene números binarios ordenados de a 2 n - 1 :02n1

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.

DSblizzard
fuente
11
Echa un vistazo a la complejidad de Kolmogorov, que en cierto sentido es la compresión óptima (hasta una constante aditiva). Desafortunadamente, la complejidad de Kolmogorov no es computable ...
Yuval Filmus
12
¿Por qué necesitas comprimir esos datos? ¿No puedes regenerarlo cada vez que lo necesites? (Lo que está estrechamente relacionado con el enfoque de complejidad de Kolmogorov mencionado por @YuvalFilmus: la complejidad de Kolmogorov es esencialmente la duración del programa más corto que genera la salida).
David Richerby
77
Escribí tal algoritmo en la escuela secundaria, hace 20 años. Dada su entrada, se habría comprimido a unos "pocos bytes" (aproximadamente 3,500,000: 1 en un escenario óptimo). Sin embargo, los datos rara vez se ven así, por lo que no es práctico tener un algoritmo como este. Los algoritmos de compresión generales tienen que lidiar con patrones complejos, no simples. Cualquiera puede escribir un algoritmo para almacenar datos lineales, pero almacenar datos interesantes es el desafío.
phyrfox
3
¿Cómo te da n = 20 22MB? Obtengo 4.2 MB si uso enteros de 4 bytes
njzk2
3
@JiK oh, está bien. bueno, esa sería una primera noción de compresión, no usar 8 bits para representar un solo bit.
njzk2

Respuestas:

27

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

0
1
1
1
1
...

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 azarnTrozos de tamaño N , para amortizar los gastos generales de encontrarnmientras se conserva una buena fiabilidad.Nn

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).

a la izquierda
fuente
44

Claro, por supuesto que hay algoritmos. Aquí está mi algoritmo:

  1. 02n1nn

  2. 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 y lea libros de texto sobre compresión de datos.

DW
fuente
55
El trabajo de un compresor es reconocer patrones comunes y explotarlos. No es que este patrón sea poco común u oscuro. Entonces, es una pregunta natural preguntarse por qué no se explota. Decirle que hay una compensación o darle un algoritmo que falla en todo, excepto que el patrón es una evasión total.
Mehrdad
17
Claro que me parece poco común. Esto aparecería en los datos de la vida real muy raramente, en comparación con los tipos de patrones que buscan los buenos compresores.
amalloy
17
@Mehrdad No es una evasiva sarcástica: es todo . Para cualquier patrón X que simplemente se genera y se verifica, hay un algoritmo de compresión que busca ese patrón y lo trata. Entonces, esta es la respuesta a cualquier pregunta en la línea de "¿Existe un algoritmo de compresión que se ocupe de esa X?" Claro, siempre hay un algoritmo que busca patrones ligeramente más complejos. Y hay uno que busca patrones ligeramente más complejos que ese, también, hasta el infinito . Su objeción es infundada.
David Richerby
Los comentarios no son para discusión extendida; Esta conversación se ha movido al chat .
Gilles 'SO- deja de ser malvado'
Una aplicación extrema de este principio son los enlaces magnéticos de bittorrent donde cualquier archivo o colecciones de archivos de cualquier tamaño simplemente se representan (comprimidos) en 160 bits de datos fijos. Por supuesto, existe el riesgo de que se produzca una colisión de hash.
slebetman
17

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:

>>> import gzip
>>> import lzma
>>> import zlib
>>> import bz2
>>> import time
>>> dLen = 16
>>> inputData = '\n'.join('{:0{}b}'.format(x, dLen) for x in range(2**dLen))
>>> inputData[:100]
'0000000000000000\n0000000000000001\n0000000000000010\n0000000000000011\n0000000000000100\n000000000000010'
>>> inputData[-100:]
'111111111111010\n1111111111111011\n1111111111111100\n1111111111111101\n1111111111111110\n1111111111111111'
>>> def bwt(text):
    N = len(text)
    text2 = text * 2
    class K:
        def __init__(self, i):
            self.i = i
        def __lt__(a, b):
            i, j = a.i, b.i
            for k in range(N): # use `range()` in Python 3
                if text2[i+k] < text2[j+k]:
                    return True
                elif text2[i+k] > text2[j+k]:
                    return False
            return False # they're equal

    inorder = sorted(range(N), key=K)
    return "".join(text2[i+N-1] for i in inorder)

>>> class nothing:
    def compress(x):
        return x

>>> class bwt_c:
    def compress(x):
        return bwt(x.decode('latin_1')).encode('latin_1')

>>> for first in ('bwt_c', 'nothing', 'lzma', 'zlib', 'gzip', 'bz2'):
    fTime = -time.process_time()
    fOut = eval(first).compress(inputData)
    fTime += time.process_time()
    print(first, fTime)
    for second in ('nothing', 'lzma', 'zlib', 'gzip', 'bz2'):
        print(first, second, end=' ')
        sTime = -time.process_time()
        sOut = eval(second).compress(fOut)
        sTime += time.process_time()
        print(fTime + sTime, len(sOut))

bwt_c 53.76768319200005
bwt_c nothing 53.767727423000224 1114111
bwt_c lzma 53.83853460699993 2344
bwt_c zlib 53.7767307470001 5930
bwt_c gzip 53.782549449000044 4024
bwt_c bz2 54.15730512699997 237
nothing 6.357100005516259e-05
nothing nothing 0.0001084830000763759 1114111
nothing lzma 0.6671195740000258 27264
nothing zlib 0.05987233699988792 118206
nothing gzip 2.307255977000068 147743
nothing bz2 0.07741139000017938 187906
lzma 0.6767229399999906
lzma nothing 0.6767684639999061 27264
lzma lzma 0.6843232409999018 27324
lzma zlib 0.6774435929999072 27280
lzma gzip 0.6774431810001715 27292
lzma bz2 0.6821310499999527 27741
zlib 0.05984937799985346
zlib nothing 0.05989508399989063 118206
zlib lzma 0.09543156799986718 22800
zlib zlib 0.06264000899977873 24854
zlib gzip 0.0639041649999399 24611
zlib bz2 0.07275534999985211 21283
gzip 2.303239570000187
gzip nothing 2.303286251000145 147743
gzip lzma 2.309592880000082 1312
gzip zlib 2.3042639900002087 2088
gzip gzip 2.304663197000309 1996
gzip bz2 2.344431411000187 1670
bz2 0.07537686600016968
bz2 nothing 0.07542737000017041 187906
bz2 lzma 0.11371452700018381 22940
bz2 zlib 0.0785322910001014 24719
bz2 gzip 0.07945505000020603 24605
bz2 bz2 0.09332576600013454 27138

(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.

TLW
fuente
Puedes deshacerte evalhaciendo: for first in (bwt_c, nothing, lzma, zlib, gzip, bz2):y fOut = first.compress(inputData).
Kasperd
@kasperd: ¿cómo imprimiría los nombres en ese caso? Personalmente, es más simple (y menos propenso a errores) hacer una evaluación que tratar de mantener sincronizados los nombres + referencias.
TLW
55
Primero bwt y luego bz2 comprime esto extremadamente bien. Este es un comportamiento extremadamente extraño y probablemente debido a este patrón exacto. Tenga en cuenta que está haciendo el bwt dos veces (bz2 se basa en el BWT), lo que generalmente resulta en una peor compresión. También tenga en cuenta que bwt hoy se ejecuta habitualmente en la 4 times block sizememoria (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.
Christoph
3
@ Christoph - Sé que bz2 se basa en BWT ... En realidad, había comenzado a escribir una respuesta al efecto de 'solo usa bz2', pero descubrí que no se comprimía tan bien como esperaba, dije 'huh ', y decidí ver si mi propio BWT lo haría mejor. Solo necesitaba un compresor para la salida, y me fui 'podría probar diferentes compresores para ver qué pasa'.
TLW
1
@ Christoph - Eché otro vistazo. 2 bwts de estos datos generan algo que es extremadamente susceptible de codificación RLE. Como en, si cuenta el número de pares RLE necesarios para 0, 1, 2, ... BWT anidados en una entrada de 16 bits, obtendrá 622591 1081343 83 ...
TLW
10

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.

0000000000       00000  most significant bits
0000000001       00000
0000000010  =>   00000
0000000011       00000
0000000100       00000
                 00000
                 00000
                 00001
                 00110
                 01010 least significant bits
Cort Ammon - Restablece a Monica
fuente
5

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).

Roman Starkov
fuente
n
1
nnn+1n1
Bueno, herramientas como Mathematica encuentran funciones para muchas secuencias ...
Raphael
3

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]; diferencia a'[i] = a[i-1]-a[i]; diferencia inversa a'[i] = a[i]-a[i-1]; y el xor a'[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).

monstruo de trinquete
fuente