2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ As for 2., compression uses a (at least one) model for the source. If it has to build it from the message, it exploits some kind of repetition. If not, it has to use prior knowledge about the messages (or the source, which could arguably have used same knowledge to encode the messages more succinctly in the first place) shared with the decompressor. $\endgroup$ – greybeard Jul 24 '16 at 13:29
  • $\begingroup$ @greybeard , for example you have a string $a$ of $n$ bits, after using a compression method=function=process $f$, you get string $b$, which is the encrypted version of $a$. Now you again call $f$ to compress $b$, so it is a repetition of $f$, I was refereeing this to recursion. $\endgroup$ – Jim Jul 24 '16 at 13:37
  • 2
    $\begingroup$ @jim It is advisable to limit yourself to one question per post. Also it wood be good if you include the link to the reference material. $\endgroup$ – sashas Jul 24 '16 at 13:51
  • 2
    $\begingroup$ I'd call the output of a data compressor encoded (or compressed) - encrypted implies the intention to hide something. There has been abundant idle talk about recursive compression - bottom line: gets you nowhere. You can find some even on stackexchange and stackoverflow. (Another term to while your time away is Jules Gilbert.) If you insist, call Markov compression using higher order context recursive. $\endgroup$ – greybeard Jul 24 '16 at 13:59
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Is the BWT truly bijective though? As I understand, the BWT produces one extra piece of information of size log2(n), which is the start index of the permuted array $\endgroup$ – Nayuki Jul 24 '16 at 20:44
  • 1
    $\begingroup$ There is bijective BWT (this fact included in the name) that does not add additional terminator, so output size matches the input. $\endgroup$ – Evil Jul 24 '16 at 20:51
  • 4
    $\begingroup$ @Nayuki Bijective variant of BWT. $\endgroup$ – Evil Jul 24 '16 at 20:59
  • $\begingroup$ +1 for noting that some algorithms can benefit (contrary to popular educated belief). e.g., when I tried to mix data compression goals with other goals (quick programming implementation), I found using BCL worked, and specifically using RLE, then LZ, then HUFF components (in that order) provided optimal results. The common scenario is that compressed data doesn't tend to re-compress well, but that is not an absolutely universal truth. $\endgroup$ – TOOGAM Jul 26 '16 at 5:53
  • $\begingroup$ Are there other Transformative compression algorithms? I've slowly been working on a transformative algorithm and wonder if I'm reinventing the wheel. $\endgroup$ – Hellonearthis Apr 16 '17 at 3:40
2
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ This is a particular case of a very special case. It would be better with real data, for example, a natural text file. $\endgroup$ – Davidmh Jul 24 '16 at 20:00
  • 2
    $\begingroup$ @Davidmh While it's certainly not a perfect example, it nicely shows that the categorical statements in the other answers are false (something I strongly suspected). On average compressing compressed data will enlarge them but that's true for most data (as you point out), and there certainly are cases where iterating compression can lower the size (it's really about how you hit the windows that compression algorithms use I think). $\endgroup$ – DRF Jul 24 '16 at 20:35
  • 4
    $\begingroup$ The reason gzip can be compressed twice effectively is because if you have a long run of zeros, the DEFLATE codec can't represent it effectively, breaking it up into runs of only 257. Newer compressors that can natively encode longer runs do not suffer from this problem. $\endgroup$ – Nayuki Jul 24 '16 at 20:45
  • $\begingroup$ @Davidmh: You did read my last paragraph? $\endgroup$ – celtschk Jul 25 '16 at 4:51
  • $\begingroup$ @celtschk yes, and my point is that what happens here is hardly generalisable to practical cases. $\endgroup$ – Davidmh Jul 25 '16 at 9:56
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "Lossless compression algorithms, on average, increase the size of the file" Misleading. That would be true if the average is (uniformly) over all the possible sizes (up to some size). $\endgroup$ – leonbloy Jul 24 '16 at 20:49

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.