Algorithms that achieve better compression for more data

Question

I'm interested in compression algorithms where the compression ratio increases as the amount of data to be compressed increases. Let's call this "super compression". Could super compression be achieved through recursive compression algorithms?

Here's the kind of algorithm I'm contemplating. The binary file is first scanned, to identify patterns. After this, the file is rewritten such that the patterns are encoded, e.g., if there is a sequence of 100 $0$'s, it could be represented as $xxx 0$ where $xxx$ represents that the $0$ occurs 100 times.

After this is done, the algorithm is then called on the generated compression file, until a file with no patterns is produced. The header of the file will contain how many times the algorithm was run, so the file can be decompressed. Will this work to achieve super compression?

Answer 1

Compressing compressed data only benefits you if the original compression wasn't very good. Good compression essentially removes all the patterns, leaving very little for any future round of compression to exploit.

There is a fundamental limit as to how well any particular lossless compression scheme can compress. In particular, if a compression scheme could make every file smaller, you could indeed run it repeatedly and you could keep going until the file you started with had become one bit long. Since there are only two compressed files and the decompression program is deterministic, the decompression program can only have two possible outputs, but it's supposed to be able to produce whatever file was actually compressed.

In fact, you can't even compress all files once. There are $2^n$ $n$-bit files, but only $\sum_{i=0}^{n-1}=2^n-1$ files of length strictly less than $n$. So, if you had an algorithm that could make every file of length $n$ strictly smaller, there would have to be two different files that compress to the same thing, by the pigeonhole principle. But now the decompresser doesn't know how to decompress that file.

And it gets worse. Any fixed lossless compression scheme can't compress half of the possible files by even one bit. When we talked about compressing $n$-bit files in the previous paragraph, we didn't mention that there are also files of length less than $n$, which need to be compressed, too. There are $2^{n+1}-1$ possible files whose length is in the range $0$–$n$ bits. If we could compress all of those by even one bit, we'd have to be able to write $2^{n+1}-1$ different files of length at most $n-1$ bits, but there are only half that number of $(n-1)$-bit files, so it simply cannot be done.

Note that you can't get around this by saying "If algorithm A compresses the file, I'll use that and, otherwise, I'll use algorithm B." Even if it were guaranteed that every file could be compressed by one of those two algorithms, you'd have to write a header to the file to say which one was used. So, now you need to compress by at least two bits so that the compressed file plus the header is shorter than the original file. But no single algorithm can compress more than a quarter of files by two bits, so your combination of A and B still can't compressed half your files.

You can't get around it by using multiple files because the total length of those files will still obey the same rules that we already discussed. Since, in reality, files on disks are stored in blocks so storing $k$ files means you need to allocate at least $k$ blocks, which isn't efficient when the files are small. Multiple files does allow you to cheat slightly, since it means you don't need any delimiter between your metadata in one file and the data in the second. However, that data still has to be stored in the directory entry so you're not really saving any space.

Note that everything above applies to all possible compression algorithms. It doesn't use any properties of whatever algorithm you could think of: the argument is just about the number of files of different lengths. The scheme you're thinking of – looking for patterns and representing them using some language – is no different. It cannot win because nothing can win. Taken to the ultimate degree, you're moving towards Kolmogorov complexity, which essentially compresses a file into the shortest program that will output that file when it's run. Still, this doesn't let you get around the fundamental bounds. Indeed, it's the tool that's used to prove a lot of the more interesting fundamental bounds. And it turns out that, for most files, the shortest program is print "[literal string containing the file contents]";, which is, essentially, one bit longer than the file you started with.