Author |
Topic: Lossless compression (Read 641 times) |
|
harpanet
Junior Member
Posts: 109
|
 |
Lossless compression
« on: Sep 16th, 2003, 5:46am » |
 Quote  Modify
|
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).
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: Lossless compression
« Reply #1 on: Sep 16th, 2003, 7:20am » |
Quote Modify
|
::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::
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
harpanet
Junior Member
Posts: 109
|
|
Re: Lossless compression
« Reply #2 on: Sep 16th, 2003, 7:28am » |
Quote Modify
|
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.
::It's a neat non-mathematical solution. And is quite literally a Reductio Ad Absurdum proof.  ::
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Lossless compression
« Reply #3 on: Sep 16th, 2003, 8:04am » |
Quote Modify
|
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)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: Lossless compression
« Reply #4 on: Sep 16th, 2003, 8:09am » |
Quote Modify
|
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.
|
| « Last Edit: Sep 16th, 2003, 8:11am by James Fingas » |
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: Lossless compression
« Reply #5 on: Sep 16th, 2003, 8:43am » |
Quote Modify
|
on Sep 16th, 2003, 7:28am, 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. 
|
|
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
Sameer
Uberpuzzler
Pie = pi * e
Gender:
Posts: 1261
|
|
Re: Lossless compression
« Reply #6 on: Sep 19th, 2003, 8:04am » |
Quote Modify
|
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.
|
|
IP Logged |
"Obvious" is the most dangerous word in mathematics.
--Bell, Eric Temple
Proof is an idol before which the mathematician tortures himself.
Sir Arthur Eddington, quoted in Bridges to Infinity
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print