3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Could super compression(…) Through recursive compression algorithms. These sentences no verbal phrase, or this sentence has a word capitalised that shouldn't be. Apologies if this is the wrong SE site. None of SE is for defying logic: there are limitations to lossless data compression. (The problem isn't that arbitrary data compression isn't possible - just re-obtaining every original is. With binary encoded data: count the numbers of ones, encode as binary number, repeat to fixed-point - one bit. For how many originals?) $\endgroup$ – greybeard Dec 4 '16 at 10:30
  • 1
    $\begingroup$ @greybeard "These sentences no verbal phrase" That sentence of yours also has no verb phrase. Please try to leave comments that are more constructive than "Your grammar sucks. Oops, so does mine." $\endgroup$ – David Richerby Dec 4 '16 at 10:39
  • 1
    $\begingroup$ @greybeard has a point: I struggle to extract what the question here is. That said, simple counting arguments show that there is no free lunch in compression. You want free food forever, which is similarly impossible. $\endgroup$ – Raphael Dec 4 '16 at 11:02
  • 2
    $\begingroup$ 1. The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! 2. Comments are not for extended discussion; they exist to help you improve your question. If you think people have misunderstood what you are talking about, edit your question so that it will be clearer to others who read it for the first time, rather than trying to use the comments for an extended back-and-forth. $\endgroup$ – D.W. Dec 4 '16 at 16:26
  • $\begingroup$ Is it yours: cstheory.stackexchange.com/questions/37088/… ? $\endgroup$ – Evil Dec 6 '16 at 20:32
6
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Ooh. Thank you, I get what you mean now. I'm thinking of the compressed file being two files. One for the compressed file, and another file containimg rules for decompression. So even if two files compressed to the same thing, the decompressor, could still decompress. Maybe the second file will be appended as an header to the first. Thanks for explaining the logoc of why we can't compress up to half of the $2^n$ files. $\endgroup$ – Tobi Alafin Dec 4 '16 at 11:57
  • 1
    $\begingroup$ @TobiAlafin Huffman Codes (which create two "files", the code tree and the compressed file itself) are close to optimal, speaking in information-theoretic terms, and they don't achieve the bounds you imagine. In fact, David shows how no method can achieve compression always, let alone of more than a constant factor, asymptotically. That proof applies no matter how many files you create. $\endgroup$ – Raphael Dec 4 '16 at 12:24
  • $\begingroup$ Thanks @Raphael, I'll do some more research. If the idea isn't feasible, I''ll drop it. $\endgroup$ – Tobi Alafin Dec 4 '16 at 13:18
  • $\begingroup$ @Raphael, if the decompression "key" is generated where the "key" is a relation that maps the compressed file unto the original using a predefined set of rules, then doesn't that resolve the pidgeon hole problem. An arbitrary file of length $m$ can be mapped unto many files of length $n, n: m \lt n$, shouldn't this allow compression of all files{Ignoring the length of the "key" file. It'll grow $o${linearly}(hopefully logarithmically)with the growth of the file to be compressed. $\endgroup$ – Tobi Alafin Dec 4 '16 at 13:46
  • 2
    $\begingroup$ @TobiAlafin If you ignore the length of the key, just let the key be the exact contents of the original file and compress everything to the empty file plus a huge key. If you measure the total data required to recover the initial file, it will always obey the mathematics I set out in my answer. $\endgroup$ – David Richerby Dec 4 '16 at 15:08

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.