☰

Как сжать несколько больших, высокоэнтропийных, но очень похожих файлов?

tag-icon • tag-icon linux backup compression archiving
Как сжать несколько больших, высокоэнтропийных, но очень похожих файлов?

У меня есть несколько больших (больше любого словаря, сотни ГБ) файлов. Эти файлы имеют очень высокую энтропию и очень плохо сжимаются. Однако эти файлы (насколько я могу судить) почти полностью идентичны. (И на самом деле не сжаты)

В качестве тестового примера была опробована мелкомасштабная симуляция:

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

cat random random random > 3random

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

Я думаю, это довольно хорошо имитирует упаковку tar с моими файлами. Я не удивлен, что ни gz, ни xz не могут сжать эти файлы, на самом деле они становятся немного больше.

Есть ли разумный способ сжать эти файлы? Это только для (офлайн) архивов, распаковка не будет производиться часто.

решение1

Начнем с файла размером 10 МБ псевдослучайных данных и сделаем две его копии:

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

Давайте изменим эти копии так, чтобы они стали «почти полностью идентичными» (как вы сказали):

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

Теперь мы можем сжать данные в каждом файле и посмотреть, что произойдет:

$ 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

Мы видим, что это фактически увеличивает размер данных. Теперь давайте преобразуем данные в шестнадцатеричные данные, понятные человеку (ну, в некотором роде) и сожмем результат:

$ 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

Данные стали очень большими. Четыре раза в шестнадцатеричном формате, дважды, если шестнадцатеричный формат сжат. Теперь самое интересное: давайте вычислим разницу между шестнадцатеричным форматом и сжатым форматом:

$ 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

И это прекрасно. Подведем итог:

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

Чем больше у вас файлов, тем лучше это работает. Чтобы сделать тест восстановления данных из ваших сжатых diffs "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

ЗАМЕЧАНИЯ

  • Вам не нужны некоторые из файлов, сгенерированных здесь, например, сжатые версии исходных файлов и сжатый hex. Я сделал их просто для того, чтобы подчеркнуть.
  • Успех этого метода во многом зависит от смысла "почти полностью идентичны". Вам нужно провести тесты. Я провел несколько тестов, и это отлично работает для многих, многих типов данных (а именно, дампов баз данных и даже отредактированных изображений и видео). Я на самом деле использую это для некоторых резервных копий.
  • Более сложный метод — использование librsync, но он отлично работает во многих ситуациях и будет отлично работать практически в любой среде *nix без необходимости установки нового программного обеспечения.
  • С другой стороны, это может потребовать написания некоторого скрипта.
  • Я не знаю ни одного инструмента, который бы делал все это.

решение2

gzip работает с блоками по 32 Кб, поэтому поможет, если те же шаблоны находятся в диапазоне 32 Кб (что не ваш случай). Для xz вы можете попробовать передать очень большой--размер блокано вам нужно много свободной памяти (см.--memlimitпараметры).

Связанный контент