☰

Algoritmo LZMA/LZMA2 ( xz, 7z)

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

Acabei de fazer um pequeno experimento onde criei um arquivo tar com arquivos duplicados para ver se seria compactado, para minha surpresa, não foi! Seguem detalhes (resultados recuados para prazer de leitura):

$ 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
$

Primeiro criei um arquivo de 1MiB de dados aleatórios (a). Então copiei-o para um arquivo be também vinculei-o para c. Ao criar o tarball, o tar aparentemente estava ciente do hardlink, já que o tarball tinha apenas ~2MiB e não ~3Mib.

Agora eu esperava que o gzip reduzisse o tamanho do tarball para ~ 1MiB, já que aeb são duplicatas e deveria haver 1MiB de dados contínuos repetidos dentro do tarball, mas isso não ocorreu.

Por que é isso? E como eu poderia compactar o tarball com eficiência nesses casos?

Responder1

Gzip gzip é baseado no algoritmo DEFLATE, que é uma combinação da codificação LZ77 e Huffman. É um algoritmo de compactação de dados sem perdas que funciona transformando o fluxo de entrada em símbolos compactados usando um dicionário criado dinamicamente e observando duplicatas. Mas não consegue encontrar duplicatas separadas por mais de 32K. Esperar que ele identifique duplicatas com 1 MB de distância não é realista.

Responder2

Nicole Hamilton observa corretamenteque gzipnão encontrará dados duplicados distantes devido ao pequeno tamanho do dicionário.

bzip2é semelhante porque está limitado a 900 KB de memória.

Em vez disso, tente:

Algoritmo LZMA/LZMA2 ( xz, 7z)

O algoritmo LZMA é da mesma família do Deflate, mas usa um tamanho de dicionário muito maior (personalizável; o padrão é algo em torno de 384 MB). O xzutilitário, que deve ser instalado por padrão nas distribuições Linux mais recentes, é semelhante gzipe usa LZMA.

Como o LZMA detecta redundância de longo alcance, ele poderá desduplicar seus dados aqui. No entanto, é mais lento que o Gzip.

Outra opção é o 7-zip ( 7z, no p7zippacote), que é um arquivador (em vez de um compressor de fluxo único) que usa LZMA por padrão (escrito pelo autor do LZMA). O arquivador 7-zip executa sua própria desduplicação no nível do arquivo (observando arquivos com a mesma extensão) ao arquivar em seu .7zformato. Isso significa que, se você estiver disposto a substituir tarpor 7z, obterá arquivos idênticos desduplicados. No entanto, 7z não preserva carimbos de data/hora, permissões ou xattrs de nanossegundos, portanto, pode não atender às suas necessidades.

lrzip

lrzipé um compressor que pré-processa os dados para remover redundância de longa distância antes de alimentá-los em um algoritmo convencional como Gzip/Deflate, bzip2, lzop ou LZMA. Para os dados de amostra fornecidos aqui, não é necessário; é útil quando os dados de entrada são maiores do que cabem na memória.

Para esse tipo de dados (pedaços incompressíveis duplicados), você deve usar lzopcompactação (muito rápida) com lrzip, porque não há benefício em se esforçar mais para compactar dados completamente aleatórios depois de desduplicados.

Bup e Obnam

Já que você marcou a pergunta, se o seu objetivo aqui é fazer backup de dados, considere usar um programa de backup com desduplicação comoBupouObnam.

Responder3

gzipnão encontrará duplicatas, mesmo xzcom um tamanho de dicionário enorme. O que você pode fazer é usar mksquashfs- isso realmente economizará espaço de duplicatas.

Alguns resultados de testes rápidos com xze mksquashfscom três arquivos binários aleatórios (64 MB), dos quais dois são iguais:

Configurar:

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

Abóboras:

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

Responder4

Como complemento à resposta do 'caracol mecânico:

Mesmo xz (ou lzma) não encontrará duplicatas se o tamanho do arquivo único descompactado (ou, mais precisamente, a distância entre as duplicatas) exceder o tamanho do dicionário. xz (ou lzma), mesmo na configuração mais alta, -9ereserva apenas 64 MB para isso.

Felizmente você pode especificar seu próprio tamanho de dicionário com a opção --lzma2=dict=256MB (só --lzma1=dict=256MBé permitido ao usar o alias lzma para o comando)

Infelizmente, ao substituir as configurações por cadeias de compactação personalizadas, como no exemplo acima, os valores padrão para todos os outros parâmetros não são definidos no mesmo nível de -9e. Portanto, a densidade de compactação não é tão alta para arquivos únicos.

informação relacionada