No compression algorithm can compress all input messages?

Question

I just started reading a book called Introduction to Data Compression, by Guy E. Blelloch. On page one, he states:

The truth is that if any one message is shortened by an algorithm, then some other message needs to be lengthened. You can verify this in practice by running GZIP on a GIF file. It is, in fact, possible to go further and show that for a set of input messages of fixed length, if one message is compressed, then the average length of the compressed messages over all possible inputs is always going to be longer than the original input messages.

Consider, for example, the 8 possible 3 bit messages. If one is compressed to two bits, it is not hard to convince yourself that two messages will have to expand to 4 bits, giving an average of 3 1/8 bits.

Really? I find it very hard to convince myself of that. In fact, here's a counter example. Consider the algorithm which accepts as input any 3-bit string, and maps to the following outputs:

000 -> 0
001 -> 001
010 -> 010
011 -> 011
100 -> 100 
101 -> 101
110 -> 110
111 -> 111

So there you are - no input is mapped to a longer output. There are certainly no "two messages" that have expanded to 4 bits.

So what exactly is the author talking about? I suspect either there's some implicit caveat that just isn't obvious to me, or he's using language that's far too sweeping.

Disclaimer: I realize that if my algorithm is applied iteratively, you do indeed lose data. Try applying it twice to the input 110: 110 -> 000 -> 0, and now you don't know which of 110 and 000 was the original input. However, if you apply it only once, it seems lossless to me. Is that related to what the author's talking about?

Answer 1

What you are missing is that you need to consider all bits of size 3 or less. That is: if in a compression scheme for bits of size 3 or less we compress one of the 3-bit strings to a 2-bit string, then some string of size 3 or less will have to expand to 3 bits or more.

A losless compression scheme is a function $C$ from finite bit strings to finite bit strings which is injective, i.e., if $C(x) = C(y)$ then $x = y$, i.e., $C(x)$ uniquely determines $x$.

Consider an arbitrary compression scheme $C$ and let $S$ be a set of binary strings. We can express how well $C$ works on $S$ by computing the ratio $$\text{CompressionRatio}(C,S) = \frac{\sum_{x \in S} \mathrm{length}(C(x))}{\sum_{x \in S} \mathrm{length}(x)}.$$ A small compression ratio is good. For example, if it is $1/2$ that means we can on average compress strings in $S$ by 50% using $C$.

If we try to compress all strings of length at most $n$ then we are in trouble:

Theorem: Let $S$ be the set of all strings of length at most $n$ and $C$ any compression scheme. Then $\text{CompressionRatio}(C,S) \geq 1$.

So, the best compression scheme in the world is the identity function! Well, only if we want to compress random strings of bits. The bit strings which occur in practice are far from random and exhibit a lot of regularity. This is why it makes sense to compress data despite the above theorem.

Answer 2

Just an additional note to Andrej's good answer:

You can also take a look to to Kolmogorov complexity:

Definition: Given a string $s$, its Kolmogorov complexity $C(s)$ relative to a fixed model of computation is the length of the shortes program (e.g. Turing machine) that outputs $s$.

Informally $C(s)$ measures its information content or its degree of redundancy; a string $s$ is incompressible if $C(s) \geq |s|$

Two fundamental theorems are:

1) independently from the model of computation there is a constant $c$ such that for every string $s$: $C(s) \leq |s| + c$ (informally, given a string $s$ you can hard encode it in a program that simply outputs it without any processing or compression)

2) for all $n$ there exist a string $s$ of length $n$ that is incompressible: $C(s) \geq |s|$ (analogous to the theorem described in Andrej's answer).

The proof is simple: there are $2^n$ binary strings of length $n$, but fewer descriptions (programs) of length $< n$:

$\sum_{i=0}^{n-1} 2^i = 2^n - 1 < 2^n$.

Answer 3

Your counterexample is wrong.

Your list of compressed values has some hidden information which indeed makes the average length longer than 3 bits. The extra information is the length of the output string.

With our eyes we can see from your table that the first output string is only 1 bit long, and the others are 3 bits, but you're cheating if you don't explicitly encode that fact. Let's encode that by prepending one more bit; 0 will mean "length = 1", and 1 will mean "length = 3".

So your table really becomes:

000 -> 00
001 -> 1001
010 -> 1010
011 -> 1011
100 -> 1100 
101 -> 1101
110 -> 1110
111 -> 1111

...which averages to 3.75 bits.

EDIT

Here's an afterthought, which illustrates the same point. It's a nice quiz question:

Morse code is made up of just dots and dashes. Let's call dot 0, and dash 1. All the uppercase letters are encoded as no more than four bits.

E = . = 0
Q = --.- = 1101

There are 26 uppercase letters. But four bits should only be able to encode 16 distinct values. What's going on?

Answer 4

Counting the trivial zero-length case, there are $2^{n+1}-1$ bit strings whose length is at most n (if lengths are known to be exact multiples of eight, the number is smaller but harder to compute). Thus, all strings of length $n$ or less could be represented using strings of fixed length $n+1$. If many strings will be much shorter than the maximum length, however, it may be helpful to use alternative coding schemes which add more than one to the length of maximal strings, but less to the length of shorter strings. Consequently, the amount of information conveyed by knowing a string's exact length depends upon how long one would assume that the string could be, and how willing one would be to pad shorter strings.

Because such factors are very much application dependent, it's helpful to assume a computation model in which input strings are assumed to contain information that would be sufficient to let a reader know where they end (even if they were padded with arbitrary quantities of arbitrary data), and output strings are required to do likewise. Such a computation model will allow any operations which would work on individual data records to just work as well on any concatenated sequence of data records [code which would know when to stop reading entire uncompressed records can be presumed to know just as well when to stop reading entire compressed ones].