1
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ See also the answers to Compression of random data is impossible. $\endgroup$
    – John Kemeny
    Commented Mar 23, 2020 at 15:56
  • 1
    $\begingroup$ 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." $\endgroup$
    – John Kemeny
    Commented Mar 23, 2020 at 15:58
  • $\begingroup$ @PålGD Any research reference on such method or similar to these? $\endgroup$
    – Michael
    Commented Mar 23, 2020 at 20:56

2 Answers 2

Reset to default
1
$\begingroup$

Here's a partial "yes" answer to your question.

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).

Improve this answer
$\endgroup$
2
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Any research reference on such method? $\endgroup$
    – Michael
    Commented Mar 23, 2020 at 20:56
  • $\begingroup$ Yep. Lots. As I mentioned above, just google "compression counting argument" $\endgroup$
    – Ray
    Commented Mar 24, 2020 at 14:39
  • $\begingroup$ 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. $\endgroup$
    – Michael
    Commented Mar 24, 2020 at 16:04
  • 2
    $\begingroup$ 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.) $\endgroup$
    – Mars
    Commented Mar 24, 2020 at 16:53
  • 1
    $\begingroup$ 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. $\endgroup$
    – Ray
    Commented Mar 25, 2020 at 17:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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