3

I have several big (as in: bigger than any dictionary, 100s of GBs) files. These files are very high entropy and compress very poorly. However these files are (as far as i can tell) almost completely identical. (And not actually compressed)

As a testcase tried a small scale simulation:

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

cat random random random > 3random

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

I think this simulates packing a tar with my files quite well. I'm not surprised it turns out that neither gz nor xz can compress these files, in fact they get slightly larger.

Is there a sensible way to compress these files? This is for (offline-) archive proposes only, decompressing won't be done frequently.

  • I mean the compression ratio was slightly above 1, so it didn't compress, as expected of random data. – Fosap4 May 29 '15 at 13:30
6

Let's start with a file of 10MB of pseudo-random data and make two copies of it:

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

Let's alter those copies so that they are "almost completely identical" (as you said):

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

Now we can compress the data in each file to see what happens:

$ 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

We can see that this actually increases the size of the data. Now lets transform the data into hex human-readable data (well, sort of) and compress the result:

$ 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

Data went really big. Four times in hex, twice if hex is compressed. Now the fun part: let's compute the difference between the hex and compress that:

$ 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

And that's lovely. Let's summarize:

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

The more files you have, the better this works. To make a restoration test of the data from your compressed diffs of "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

REMARKS

  • You don't need some of the files generated here, like the compressed versions of the original files and the compressed hex. I made those just to make a point.
  • The success of this method greatly depends on the meaning of "almost completely identical". You need to make tests. I made some tests and this works great for many, many types of data (namely, database dumps and even edited images and videos). I actually use this for some backups.
  • A more sophisticated method is using librsync, but this works greatly in many situations and will work perfectly on almost any *nix environment without the need of installing new software.
  • On the down side, this might require some scripting.
  • I don't know any tool that does all this.
  • That's very hackish... but great. – Fosap4 May 29 '15 at 14:51
1

gzip works on 32Kb blocks so would help just if the same patterns are in a 32Kb range (which is not your case). For xz you could try passing a very large --block-size but you need a lot of spare memory (see the --memlimit options).

  • I don't think that works, the size of the files are beyond any reasonable block size. – Fosap4 May 29 '15 at 14:52
  • xz --block-size refers to chunks of compressed data. It's useful for random access since you need only start at the beginning of a block rather than reading the entire archive. The XZ DictSize is what you're thinking of, and that's dictated by the preset. Try xz -9 for the largest dictionray size (64MB). – Adam Katz Dec 6 '15 at 2:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.