Using Data Compression on the output of Data Compression

Question

Context:

Lossless Data compression (source coding) algorithms heavily rely on repetitive pattern (redundancy)

Questions

Is there a data compression method/algorithm that uses another data compression on the compressed data obtained so far?
If such a method exists, what are its limits?

Answer 1

When we compress something the output is smaller than input (that is the purpose of compression, otherwise we do not use it or cope with bigger file). This can be achieved by various methods including (but not limited to) matching of substrings (dictionary compression) or frequency of characters (entropy compression, like Huffman encoding) or arithmetic coding (like MTF, Elias etc.).
Some methods like (Bijective) Burrows Wheeler Transform does not compress, just change the order of characters so other methods might benefit from local similarity of characters, so it is used in conjunction with other techniques.

If we try to apply dictionary method or entropy method twice (or more times) there are no benefits at all, we already exploited the redundancy of data. Using methods with chunks of data twice will give us the issue of compressing the packed data and the header (dictionary, frame, characters etc.), so it is harder task than one we started with and the most benefitial would be changing frame size or make it addaptive (but not applying the same method more times).

Encryption is not concerned about file size - it secures data with key so that any person obtaining the file without the key will have very hard time opening it. If the quality of encryption is useable the resulting file has no obvious dependencies or visible redundancy. Encrypted files are not compressible. Now encrypting chunks several times will not add any security and will not compress file.

Please keep in mind that methods like Cezar, Rot13 and xor of key (cyclic) with data are not encryption methods, and even if they were, cyclic shift of characters (mod 256) will not change compression.

About limits - when we compress something then we have to encode header, dictionary etc., so our output file is transformed input plus additional information about it, which is commonly short and not compressible, so every time we put output of compression into input of another one we have a bit more to deal with and some redundancies were already used, this is one limit.
The second limit is that we cannot compress anything in the mean sense, taking all possible inputs of given size, compressing and calculating the mean shows that we in fact ended with more data than we started with. At the best (unlikely) case we end up with the same amount of data. This comes from the fact that contraction of data with better result is not unique anymore so we cannot decompress it uniquely to original.

Answer 2

Sometimes the best thing you can do is a little experiment:

$ dd if=/dev/zero of=zero.000 bs=1024 count=100
100+0 Datensätze ein
100+0 Datensätze aus
102400 Bytes (102 kB) kopiert, 0,00106735 s, 95,9 MB/s
$ cat zero.000| wc -c
102400
$ cat zero.000 | gzip | wc -c
133
$ cat zero.000 | gzip | gzip | wc -c
58
$ cat zero.000 | gzip | gzip | gzip| wc -c
81

So assuming that gzip implements a compression algorithm (most people would say it does), we have evidence that at least sometimes running a compression algorithm a second time can improve the compression.

Of course the file I've used here is very special (all bytes zero), and it is unlikely that anyone normally would try to compress this file.

Answer 3

Lossless compression algorithms, on average, increase the size of the file.

This is another realisation of the pigeons and the holes problem: there are $2^x$ possible messages of $x$ bits, and storing them all takes $x 2^x$. Now, if we come up with a compression algorithm that reduces one of them in 3 bits, you'll have to pay the price with another message. So, in the ideal case, all the messages will take the same amount of space. In practice, due to bookkeeping and other factors, this is increased.

In practice we aren't concerned with compressing random streams of data: real data has some structure that can be exploited, and we pay the price in "unrealistic messages". The output of a compression algorithm doesn't look anything like a "natural input", and so, it is likely to fall into the "unrealistic messages" basket. This is true even when for more powerful methods: feeding the output of gzip (DEFLATE) to a more powerful compressor, like xz (LZMA), will increase its size, and in some occasions, make it bigger than the original.

After all, if the output of a compression algorithm were likely to have certain kind of compressible patterns, the authors would have added it to the process, perhaps as an optional second pass.

Answer 4

There are a few potential ways to approach this question. One way would be to use a data compression algorithm on the output of another data compression algorithm. This can be done by taking the output of one data compression algorithm and compressing it with a second data compression algorithm.

Another way to compress the output of a data compression algorithm is to use a different type of data compression algorithm. For example, you could use a Huffman code or an arithmetic code on the output of a Run-Length Encoding (RLE) compressor. This approach can often result in smaller file sizes than using the same type of compressor twice.