# No compression algorithm can compress all input messages?

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?

## migrated from cstheory.stackexchange.comDec 21 '12 at 8:04

This question came from our site for theoretical computer scientists and researchers in related fields.

• Your code isn't a code. How do you intend to decode 00010? – SSS Dec 21 '12 at 1:35
• Actually, there is a very simple proof of this fact that relies on the pigeonhole principle. en.wikipedia.org/wiki/… – chazisop Dec 21 '12 at 13:23
• If you could compress every 3-bit message to <= 3 bits, you could compress infinitely long message in just few bits. e.g. if your proposal would work, then you could just xor with the most occurring 3-bit value, add the value to the beginning and compress. then just keep repeating until any message takes only few bits. – JarkkoL Sep 12 '14 at 2:02

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.

• Thank you. So the author misspoke, right? He said "messages of fixed length" and "consider the 8 3-bit messages", but he should have said "messages of fixed maximum length" and "consider the 14 possible messsages of at most 3-bits"? – Jack M Dec 21 '12 at 9:38
• @JackM: or even better: "consider all the strings of length at most 3 over alphabet $\{0,1\}$" – Vor Dec 21 '12 at 11:26

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

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

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?

• Is this really necessary? It seems to me that in some situations it's perfectly reasonable to allow length to be implicit - like if you have a protocol where EVERY message is preceded with its length encoded as a fixed-width word. Since it precedes every message, compressed or not, it can be neglected. And Andrej's post answers the question while allowing length to be implicit, so your restriction seems unnecessary. Still a good point to be bring up either way, of course. – Jack M Dec 22 '12 at 11:43
• Actually, do you think maybe your restriction of needing to explicitly encode length is equivalent to Andrej's restriction of needing to encode all strings of under 3 bits? – Jack M Dec 22 '12 at 11:45
• @JackM: In most cases, a compression scheme will be used not just to map single pieces of data to other (hopefully smaller) single pieces of data, but rather to map sequences of pieces of data to other (hopefully shorter) sequences of pieces of data. If the input sequences are all in a single stream which includes enough information to subdivide them, then the "input length" should include all information necessary to parse the input from a single stream, and the "output length" should include all information necessary to parse the output. – supercat Sep 11 '14 at 16:23

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