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?