Data Compression :Compress a Compressed File

Suppose we have file A that has been compressed by the the method B and the output-file is C, now if I am not wrong We can not compress C more by method B, but there might another method=algorithm D that might compress C more and produce compressed file E.

Is this kind method of using more than one compression-method in each iteration of compression standard? if there is a paper/survey paper on performance of such kind of compression, please, comment or post an answer.

I mean, is there any study where 2 or 3 methods were apply to same file, if there is a paper/survey paper on performance of such kind of compression, please, comment or post an answer.

• See also the answers to Compression of random data is impossible. Mar 23 '20 at 15:56
• See also the Wikipedia article on the Pigeonhole principle. It says that "any lossless compression algorithm, provided it makes some inputs smaller (as the name compression suggests), will also make some other inputs larger." Mar 23 '20 at 15:58
• @PålGD Any research reference on such method or similar to these? Mar 23 '20 at 20:56

Consider a file containing:

0000000000
0000000001
0000000010
0000000011
0000000100
...
1111111111


That is, it is all binary numbers that are $$b$$ bits long (in this case $$b=10$$, but in the exercise that follows, try something smaller), in order, with each number separated by (say) a newline character.

The standard BWT compression algorithm (e.g. the one that BZip is based on) performs a Burrows-Wheeler transform, followed by move-to-front coding, then followed by some kind of entropy coding (possibly using run-length encoding).

This file compresses "better" if you apply the BWT twice, applying the following stages to the BWT of the BWT instead of just the BWT. I encourage you to compute both BWTs on a small example to see why.

Now this is only one stage of the full compression algorithm, and so we haven't found a file that compresses better if you compress it twice. But this BWT "adversary" is certainly suggestive.

I don't know if there are any papers on this. I discovered this one a few years ago (but I'm sure I'm not the only person who has noticed it).

The essential problem is that most files are NOT compressible (see the counting argument). And an already compressed file is much less likely to be compressible.

• Any research reference on such method? Mar 23 '20 at 20:56
• Yep. Lots. As I mentioned above, just google "compression counting argument"
– Ray
Mar 24 '20 at 14:39
• No I meant is there any study where 2 or 3 methods were apply to same file, if there is a paper/survey paper on performance of such kind of compression, please, comment or post an answer. Mar 24 '20 at 16:04
• Mike SQ, I think there are unlikely to be many papers testing to see whether something that has been proven to be close to impossible, really is impossible. Or rather, any practical compression algorithm that is any good is still probably imperfect, so there is some algorithm that could compress further--but not by much. The "not by much" is a theorem, given appropriately precise characterizations of "good" and "much". :-) So why bother? (You can try it out with a half a dozen compression utilities. My guess is that the second or third compression will usually produce a larger file.)
– Mars
Mar 24 '20 at 16:53
• So you CAN get promising results by zipping many times (superuser.com/questions/1324034/…). But these results are always the result of inefficiencies in the compressor. They are never generalizable nor research-worthy.
– Ray
Mar 25 '20 at 17:32