wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> easy >> Lossless compression
        
(Message started by: harpanet on Sep 16^th, 2003, 5:46am)

Title: Lossless compression
Post by harpanet on Sep 16^th, 2003, 5:46am

Given a lossless data compression algorithm, show that some inputs cannot be compressed (i.e. the number of bits in the output is of equal size to, or greater size than the number of bit in the input).

Title: Re: Lossless compression
Post by towr on Sep 16^th, 2003, 7:20am

::[hide]repeatly compress the output of the compression (of whatever input). Since all information must retained, at some point the output must be greater or equal to the output in the last cycle, because else it has been compressed to nothingness, which doesn't contain any information[/hide]::

Title: Re: Lossless compression
Post by harpanet on Sep 16^th, 2003, 7:28am

I think it's one of those things, that once you know, it's so obvious. I recall my teacher telling me that one [mumble]ty years ago. It was a bit of a 'oh wow!' moment that something that on the face of it seems as if it would be very complex can be answered so simply.

::[hide]It's a neat non-mathematical solution. And is quite literally a Reductio Ad Absurdum proof. :D[/hide]::

Title: Re: Lossless compression
Post by towr on Sep 16^th, 2003, 8:04am

I never really thought about it before.
I did know about a theoretical limit, which can be proven in a different way. (Though the what and how of that has slipped my mind)

Title: Re: Lossless compression
Post by James Fingas on Sep 16^th, 2003, 8:09am

If we know the entropy of the source, then we can use the platypus-hole principle to show that we need at least as many bits in the compressed file as bits of information are contained in the source.

Of course, measuring the entropy of the source accurately is just as difficult as making a good lossless compression algorithm...

Here's the platypus-hole principle: If you put N platypuses (platypi?) into M holes, and N>M, then at least one hole has more than a single platypus in it.

Title: Re: Lossless compression
Post by Sir Col on Sep 16^th, 2003, 8:43am

on 09/16/03 at 07:28:17, harpanet wrote:

I think it's one of those things, that once you know, it's so obvious ... It was a bit of a 'oh wow!' moment that something that on the face of it seems as if it would be very complex can be answered so simply.

I agree! I've never seen that problem before and I confess to reading Towr's elegant solution after only giving it cursory thought, but... "Oh Wow!" Great solution, Towr, and thanks for posting the problem Harpanet. 8)

Title: Re: Lossless compression
Post by Sameer on Sep 19^th, 2003, 8:04am

towr has given us a nice conceptual proof.. yea its been couple of years that I have touched error coding but using entropy you can prove the limit.