# I think you can always compress compressed data, is it true?

In compressed data, repetition of same pattern is not a lot, so, you can expect it to be with space inside to contain always. I found a way to compress data without limitation. Is it right? Am I thinking in the true way?

BigNumber = BigNumber * N + LittleBitsNumber (=>smaller than N) Remove that bits Number from data/file

Thanks!

• Well, not reversibly – Tom Zych Nov 24 '18 at 10:52
• "I found a way to compress data without limitation. Is it right?" -- No. Read up on the fundamental theorems of that area. – Raphael Nov 24 '18 at 11:17
• Funny enough, many years ago a colleague of mine implemented a well known compression algorithm. As expected, it compressed some text files quite nicely. Being curious, he applied it to the compressed file, and it compressed it again. And again. And again. Then he tried restoring the compressed files, and it didn't work, and finally he found the bug in his compression code :-) – gnasher729 Nov 25 '18 at 13:15

Here's the problem with that reasoning:

If you could always compress data, you could compress the compressed data, then compress that, etc. until you have something that is 0 bytes long.

You can always apply a compression algorithm to data, but there's no guarantee that you'll get something smaller out at the end.

If you're interested in this, there's a whole field of research, called Information Theory. Some important concepts are Kolmogorov complexity and entropy.

The effect of a compression method is to replace a string (the uncompressed data) with another string (the compressed data). So it is a function from strings to strings.

We want this function to have the following properties:

1. It must be reversible: we need to be able to uncompress the compressed data and get the original back. To allow doing this perfectly, the function must be injective. This is called lossless compression.
2. It must compress: the compressed data must be shorter than the uncompressed data. The function must be strictly decreasing with respect to the length of strings.
3. It must be total: we want to apply it to arbitrary data.

These properties cannot all hold at the same time. A function that maps every string to a shorter string must map every string of length 1 to the empty string, so it cannot be injective. (dkaeae and jmite use different arguments to argue the same thing.)

So compression utilities must drop one of the three criteria:

1. Some drop losslessness. For instance, the JPEG image format uses lossy compression: from a JPEG, you cannot perfectly reconstruct the original image.
2. Some drop monotonicity. For instance, using zip or gzip on a file may produce a larger file. Use them only on files they can actually compress. It's up to you.
3. Some drop totality. They compress certain data they know they can compress, and refuse to process anything else.
• "monotonically decreasing with respect to the standard lexicographical ordering of strings" -- I think you mean strictly decreasing with respect to length, since "aaa" < "z" in lex. order, and monotonically decreasing usually allows equality. – j_random_hacker Apr 4 '19 at 11:40
• Thanks, indeed, fixed! – reinierpost Apr 4 '19 at 13:46

It is a basic result on Kolmogorov complexity that there are incompressible strings of any length. A string $$w$$ is incompressible if $$K(w) \ge |w|,$$ where $$K(w)$$ is the Kolmogorov complexity of $$w$$ (think of this as the theoretical lower bound for a compressed representation of $$w$$) and $$|w|$$ is the length of $$w$$.

The proof is quite simple: Having fixed a length $$n$$, there are $$2^n$$ binary strings of length $$n$$, while there are only $$\sum_{i=0}^{n-1} 2^i = 2^n - 1$$ binary strings of length strictly smaller than $$n$$. Since string decompression is a well-defined function (i.e., a compressed string can only stand for at most one other string), there must be a string of length $$n$$ which is incompressible.

(I have only mentioned binary strings, but this can be generalized to other alphabets. I'll leave that as an exercise.)

Some more advanced results expand on this and show there is not a single incompressible string (as the proof above may seem to imply) but actually many, many incompressible strings of any given length.

• I don't think that'll help here, since it's always possible (and trivial) to compress any finite set of such strings. Arguments that directly disprove any alleged "perfect" compression method are more convincing, imho. – Raphael Nov 24 '18 at 11:19