Como compactar arquivos de entropia serveral, grande e alta, mas muito semelhantes?

Question

Eu tenho vários arquivos grandes (como em: maior que qualquer dicionário, 100s de GBs). Esses arquivos têm entropia muito alta e compactam muito mal. No entanto, esses arquivos são (tanto quanto eu posso dizer) quase completamente idênticos. (E não comprimido realmente)

Como um testcase tentou uma simulação em pequena escala:

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

cat random random random > 3random

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

Eu acho que isso simula a embalagem de um tar com meus arquivos muito bem. Não me surpreende que nem o gz nem o xz consigam compactar esses arquivos. Na verdade, eles ficam um pouco maiores.

Existe uma maneira sensata de compactar esses arquivos? Isto é para o arquivo (offline-) proposto apenas, a descompactação não será feita com frequência.

    

Answer 1

Vamos começar com um arquivo de 10 MB de dados pseudo-aleatórios e fazer duas cópias:

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

Vamos alterar essas cópias para que elas sejam "quase completamente idênticas" (como você disse):

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

Agora podemos compactar os dados em cada arquivo para ver o que acontece:

$ 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 isso realmente aumenta o tamanho dos dados. Agora vamos transformar os dados em dados hexadecimais legíveis (bem, mais ou menos) e comprimir o 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

Os dados foram muito grandes. Quatro vezes em hexadecimal, duas vezes se o hex é comprimido. Agora a parte divertida: vamos calcular a diferença entre o hex e comprimir isso:

$ 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

E isso é adorável. Vamos resumir:

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

Quanto mais arquivos você tiver, melhor isso funcionará. Para fazer um teste de restauração dos dados de seus diffs compactados 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

OBSERVAÇÕES

• Você não precisa de alguns dos arquivos gerados aqui, como as versões compactadas dos arquivos originais e o hexadecimal compactado. Eu fiz aqueles só para fazer um ponto.
• O sucesso deste método depende muito do significado de "quase completamente idêntico". Você precisa fazer testes. Eu fiz alguns testes e isso funciona muito bem para muitos, muitos tipos de dados (ou seja, despejos de banco de dados e até mesmo imagens e vídeos editados). Eu realmente uso isso para alguns backups.
• Um método mais sofisticado está usando o librsync, mas isso funciona muito em muitas situações e funcionará perfeitamente em praticamente qualquer ambiente * nix sem a necessidade de instalar novos softwares.
• No lado negativo, isso pode exigir alguns scripts.
• Eu não conheço nenhuma ferramenta que faça isso.

Answer 2

O gzip funciona em blocos de 32Kb, o que ajudaria se os mesmos padrões estivessem em um intervalo de 32Kb (o que não é o seu caso). Para o xz você pode tentar passar um - tamanho de bloco muito grande, mas você precisa de muita memória sobressalente (veja as opções - memlimit ).