☰

Algoritmo LZMA/LZMA2 ( xz, 7z)

tag-icon • tag-icon linux compression gzip
Algoritmo LZMA/LZMA2 ( xz, 7z)

Acabo de hacer un pequeño experimento en el que creé un archivo tar con archivos duplicados para ver si se comprimiría, para mi sorpresa, ¡no fue así! A continuación se detallan los detalles (resultados con sangría para facilitar la lectura):

$ dd if=/dev/urandom bs=1M count=1 of=a
  1+0 records in
  1+0 records out
  1048576 bytes (1.0 MB) copied, 0.114354 s, 9.2 MB/s
$ cp a b
$ ln a c
$ ll
  total 3072
  -rw-r--r-- 2 guido guido 1048576 Sep 24 15:51 a
  -rw-r--r-- 1 guido guido 1048576 Sep 24 15:51 b
  -rw-r--r-- 2 guido guido 1048576 Sep 24 15:51 c
$ tar -c * -f test.tar
$ ls -l test.tar 
  -rw-r--r-- 1 guido guido 2109440 Sep 24 15:51 test.tar
$ gzip test.tar 
$ ls -l test.tar.gz 
  -rw-r--r-- 1 guido guido 2097921 Sep 24 15:51 test.tar.gz
$

Primero creé un archivo de 1MiB de datos aleatorios (a). Luego lo copié en un archivo by también lo vinculé a c. Al crear el tarball, tar aparentemente estaba consciente del vínculo físico, ya que el tarball tenía solo ~2MiB y no ~3Mib.

Ahora esperaba que gzip redujera el tamaño del tarball a ~1MiB ya que a y b son duplicados, y debería haber 1MiB de datos continuos repetidos dentro del tarball, pero esto no ocurrió.

¿Por qué es esto? ¿Y cómo podría comprimir el tarball de manera eficiente en estos casos?

Respuesta1

Gzip gzip se basa en el algoritmo DEFLATE, que es una combinación de codificación LZ77 y Huffman. Es un algoritmo de compresión de datos sin pérdidas que funciona transformando el flujo de entrada en símbolos comprimidos utilizando un diccionario creado sobre la marcha y buscando duplicados. Pero no puede encontrar duplicados separados por más de 32K. Esperar que detecte duplicados con una separación de 1 MB no es realista.

Respuesta2

Nicole Hamilton anota correctamenteque gzipno encontrará datos duplicados distantes debido a su pequeño tamaño de diccionario.

bzip2es similar, porque está limitado a 900 KB de memoria.

En su lugar, intente:

Algoritmo LZMA/LZMA2 ( xz, 7z)

El algoritmo LZMA pertenece a la misma familia que Deflate, pero utiliza un tamaño de diccionario mucho mayor (personalizable; el valor predeterminado es algo así como 384 MB). La xzutilidad, que debería instalarse de forma predeterminada en las distribuciones de Linux más recientes, es similar gzipy utiliza LZMA.

A medida que LZMA detecte redundancia de mayor alcance, podrá deduplicar sus datos aquí. Sin embargo, es más lento que Gzip.

Otra opción es 7-zip ( 7z, en el p7zippaquete), que es un archivador (en lugar de un compresor de flujo único) que usa LZMA de forma predeterminada (escrito por el autor de LZMA). El archivador 7-zip ejecuta su propia deduplicación a nivel de archivo (buscando archivos con la misma extensión) al archivar en su .7zformato. Esto significa que si está dispuesto a reemplazar tarcon 7z, obtendrá archivos idénticos deduplicados. Sin embargo, 7z no conserva marcas de tiempo, permisos o xattrs de nanosegundos, por lo que es posible que no se adapte a sus necesidades.

lrzip

lrzipes un compresor que preprocesa los datos para eliminar la redundancia de larga distancia antes de enviarlos a un algoritmo convencional como Gzip/Deflate, bzip2, lzop o LZMA. Para los datos de muestra que proporciona aquí, no es necesario; Es útil cuando los datos de entrada son más grandes de lo que caben en la memoria.

Para este tipo de datos (fragmentos duplicados e incompresibles), debe usar lzopla compresión (muy rápida) con lrzip, porque no tiene ningún beneficio esforzarse más en comprimir datos completamente aleatorios una vez que se han deduplicado.

Bup y Obnam

Desde que etiquetaste la pregunta, si su objetivo aquí es hacer una copia de seguridad de los datos, considere usar un programa de copia de seguridad con deduplicación comobupoObnam.

Respuesta3

gzipno encontrará duplicados, incluso xzcon un tamaño de diccionario enorme. Lo que puedes hacer es usar mksquashfs; esto realmente ahorrará espacio de duplicados.

Algunos resultados de pruebas rápidas con xzy mksquashfscon tres archivos binarios aleatorios (64 MB), de los cuales dos son iguales:

Configuración:

mkdir test
cd test
dd if=/dev/urandom of=test1.bin count=64k bs=1k
dd if=/dev/urandom of=test2.bin count=64k bs=1k
cp test{2,3}.bin
cd ..

Calabazas:

mksquashfs test/ test.squash
> test.squash - 129M

xz:

XZ_OPT='-v --memlimit-compress=6G --memlimit-decompress=512M --lzma2=preset=9e,dict=512M --extreme -T4 ' tar -cJvf test.tar.xz test/
> test.tar.xz - 193M

Respuesta4

Como complemento a la respuesta del 'caracol mecánico':

Incluso xz (o lzma) no encontrará duplicados si el tamaño del archivo único sin comprimir (o, más exactamente, la distancia entre los duplicados) excede el tamaño del diccionario. xz (o lzma), incluso en la configuración más alta, -9esolo reserva 64 MB para esto.

Afortunadamente, puedes especificar tu propio tamaño de diccionario con la opción --lzma2=dict=256MB (solo --lzma1=dict=256MBse permite cuando se usa el alias lzma para el comando)

Desafortunadamente, al anular la configuración con cadenas de compresión personalizadas como las que se muestran en el ejemplo anterior, los valores predeterminados para todos los demás parámetros no se establecen en el mismo nivel que con -9e. Por tanto, la densidad de compresión no es tan alta para archivos individuales.

información relacionada