Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question
10  
Your code isn't a code. How do you intend to decode 00010? –  SSS Dec 21 '12 at 1:35
2  
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
add comment

migrated from cstheory.stackexchange.com Dec 21 '12 at 8:04

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

3 Answers

up vote 13 down vote accepted

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.

share|improve this answer
    
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
add comment

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

share|improve this answer
add comment

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?

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.