☰

¿Cómo comprimir varios archivos, grandes, de alta entropía, pero muy similares?

tag-icon • tag-icon linux backup compression archiving
¿Cómo comprimir varios archivos, grandes, de alta entropía, pero muy similares?

Tengo varios archivos grandes (como en: más grandes que cualquier diccionario, cientos de GB). Estos archivos tienen una entropía muy alta y se comprimen muy mal. Sin embargo, estos archivos son (hasta donde yo sé) casi completamente idénticos. (Y en realidad no comprimido)

Como caso de prueba probé una simulación a pequeña escala:

dd if=/dev/urandom of=random count=1G

cat random random random > 3random

gz -1 < 3random > 3random.gz
xz -1 < 3random > 3random.xz

Creo que esto simula bastante bien empaquetar un tar con mis archivos. No me sorprende que ni gz ni xz puedan comprimir estos archivos; de hecho, se vuelven un poco más grandes.

¿Existe una forma sensata de comprimir estos archivos? Esto es solo para propuestas de archivo (sin conexión), la descompresión no se realizará con frecuencia.

Respuesta1

Comencemos con un archivo de 10 MB de datos pseudoaleatorios y hagamos dos copias del mismo:

$ dd if=/dev/urandom of=f1 bs=1M count=10
$ cp f1 f2
$ cp f1 f3

Modifiquemos esas copias para que sean "casi completamente idénticas" (como dijiste):

$   # Avoid typos and improve readability
$ alias random='od -t u4 -N 4 /dev/urandom |
  sed -n "1{s/^\S*\s//;s/\s/${fill}/g;p}"'
$ alias randomize='dd if=/dev/urandom bs=1 seek="$(
    echo "scale=0;$(random)$(random)$(random)$(random) % (1024*1024*10)" | bc -l
  )" count="$( echo "scale=0;$(random)$(random) % 512 + 1" |
    bc -l )" conv=notrunc'
$   # In files "f2" and "f3, replace 1 to 512Bytes of data with other
$   #+ pseudo-random data in a pseudo-random position. Do this 3
$   #+ times for each file
$ randomize of=f2
$ randomize of=f2
$ randomize of=f2
$ randomize of=f3
$ randomize of=f3
$ randomize of=f3

Ahora podemos comprimir los datos de cada archivo para ver qué pasa:

$ xz -1 < f1 > f1.xz
$ xz -1 < f2 > f2.xz
$ xz -1 < f3 > f3.xz
$ ls -lh f{1..3}{,.xz}
-rw-rw-r-- 1 myuser mygroup 10M may 29 09:31 f1
-rw-rw-r-- 1 myuser mygroup 11M may 29 10:07 f1.xz
-rw-rw-r-- 1 myuser mygroup 10M may 29 10:00 f2
-rw-rw-r-- 1 myuser mygroup 11M may 29 10:07 f2.xz
-rw-rw-r-- 1 myuser mygroup 10M may 29 10:05 f3
-rw-rw-r-- 1 myuser mygroup 11M may 29 10:07 f3.xz

Podemos ver que esto en realidad aumenta el tamaño de los datos. Ahora transformemos los datos en datos hexadecimales legibles por humanos (bueno, más o menos) y comprimamos el resultado:

$ xxd f1 | tee f1.hex | xz -1 > f1.hex.xz
$ xxd f2 | tee f2.hex | xz -1 > f2.hex.xz
$ xxd f3 | tee f3.hex | xz -1 > f3.hex.xz
$ ls -lh f{1..3}.hex*
-rw-rw-r-- 1 myuser mygroup 42M may 29 10:03 f1.hex
-rw-rw-r-- 1 myuser mygroup 22M may 29 10:04 f1.hex.xz
-rw-rw-r-- 1 myuser mygroup 42M may 29 10:04 f2.hex
-rw-rw-r-- 1 myuser mygroup 22M may 29 10:07 f2.hex.xz
-rw-rw-r-- 1 myuser mygroup 42M may 29 10:05 f3.hex
-rw-rw-r-- 1 myuser mygroup 22M may 29 10:07 f3.hex.xz

Los datos se hicieron realmente grandes. Cuatro veces en hexadecimal, dos veces si hexadecimal está comprimido. Ahora la parte divertida: calculemos la diferencia entre el hexadecimal y comprimámoslo:

$ diff f{1,2}.hex | tee f1-f2.diff | xz -1 > f1-f2.diff.xz
$ diff f{1,3}.hex | tee f1-f3.diff | xz -1 > f1-f3.diff.xz
$ ls -lh f1-*
-rw-rw-r-- 1 myuser mygroup 7,8K may 29 10:04 f1-f2.diff
-rw-rw-r-- 1 myuser mygroup 4,3K may 29 10:06 f1-f2.diff.xz
-rw-rw-r-- 1 myuser mygroup 2,6K may 29 10:06 f1-f3.diff
-rw-rw-r-- 1 myuser mygroup 1,7K may 29 10:06 f1-f3.diff.xz

Y eso es encantador. Resumamos:

$   # All you need to save to disk is this
$ du -cb f1{,-*z}
10485760        f1
4400    f1-f2.diff.xz
1652    f1-f3.diff.xz
10491812        total
$   # This is what you would have had to store
$ du -cb f{1..3}
10485760        f1
10485760        f2
10485760        f3
31457280        total
$   # Compared to "f2"'s original size, this is the percentage
$   #+ of all the new information you need to store about it
$ echo 'scale=4; 4400 * 100 / 31457280' | bc -l
.0419
$   # Compared to "f3"'s original size, this is the percentage
$   #+ of all the new information you need to store about it
$ echo 'scale=4; 1652 * 100 / 10485760' | bc -l
.0157
$   # So, compared to the grand total, this is the percetage
$   #+ of information you need to store 
$ echo 'scale=2; 10491812 * 100 / 10485760' | bc -l
33.35

Cuantos más archivos tengas, mejor funcionará. Para realizar una prueba de restauración de los datos de sus diferencias comprimidas de "f2":

$ xz -d < f1-f2.diff.xz > f1-f2.diff.restored
$   # Assuming you haven't deleted "f1.diff":
$ patch -o f2.hex.restored f1.hex f1-f2.diff.restored
patching file f1.hex
$ diff f2.hex.restored f2.hex # No diffs will be found unless corrupted
$ xxd -r f2.hex.restored f2.restored # We get the completely restored file
$ diff -q f2 f2.restored # No diffs will be found unless corrupted

OBSERVACIONES

  • No necesita algunos de los archivos generados aquí, como las versiones comprimidas de los archivos originales y el formato hexadecimal comprimido. Los hice solo para dejar claro un punto.
  • El éxito de este método depende en gran medida del significado de "casi completamente idéntico". Necesitas hacer pruebas. Hice algunas pruebas y esto funciona muy bien para muchos, muchos tipos de datos (es decir, volcados de bases de datos e incluso imágenes y videos editados). De hecho, uso esto para algunas copias de seguridad.
  • Un método más sofisticado es usar librsync, pero funciona muy bien en muchas situaciones y funcionará perfectamente en casi cualquier entorno *nix sin necesidad de instalar software nuevo.
  • La desventaja es que esto podría requerir algunas secuencias de comandos.
  • No conozco ninguna herramienta que haga todo esto.

Respuesta2

gzip funciona en bloques de 32 Kb, por lo que sería útil si los mismos patrones están en un rango de 32 Kb (que no es su caso). Para xz podrías intentar pasar un tamaño muy grande.--tamaño de bloquepero necesita mucha memoria adicional (consulte la--memlimitopciones).

información relacionada