如何压缩多个、大、高熵但非常相似的文件？

Question

我有几个大（例如：比任何字典都大，100 多 GB）文件。这些文件具有非常高的熵并且压缩性非常差。然而，这些文件（据我所知）几乎完全相同。（实际上并没有压缩）

作为一个测试用例，尝试了一个小规模的模拟：

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 都不能压缩这些文件，我并不感到惊讶，事实上它们会变大一些。

有没有一种合理的方法来压缩这些文件？这仅用于（离线）存档建议，不会经常进行解压缩。

Answer 1

让我们从一个 10MB 的伪随机数据文件开始，并制作它的两个副本：

$ 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

您拥有的文件越多，效果就越好。要从“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 环境中完美运行，而无需安装新软件。
• 不利的一面是，这可能需要编写一些脚本。
• 我不知道有什么工具可以做到这一切。