Compression theory reference?

[Hadmut Danisch]

On Tue, Aug 31, 2004 at 05:07:30PM -0500, Matt Crawford wrote:
>
> Plus a string of log(N) bits telling you how many times to apply the 
> decompression function!
> Uh-oh, now goes over the judge's head ...


Yeah, I just posted a lengthy description why I think that this 
counterexample is not a counterexample. 

The problem is that if you ask for a string of log(N) bits, then 
someone else could take this as a proof that this actually works, 
because a string of log(N) bits is obviously shorter than the 
message of N bits, thus the compression scheme is working. Hooray!


The problem is, that the number of iterations is not in the order of 
N, but in the order of 2^N, so it takes log2(around 2^N) = around N bits to
store the number of iterations. The recursion convertes a message of 
N bit recursively into a message of 1 or zero bit length (to your
taste), *and* a number which takes around N bit to be stored. 
Nothing is won. But proof that. 

This recursion game is far more complicated than it appears to be. 


Note also that storing a number takes in reality more than log(N)
bits. Why? Because you don't know N in advance. We don't have any
limit for the message length. So you'r counting register needs
theoretically inifinte many bits. When you're finished you know 
how many bits your number took. But storing your number needs an 
end symbol or a tristate-bit (0,1,void). That's a common mistake. 

When determining the compression rate for a file people often 
forget, that some information is not stored in the file itself, but in
the file system, e.g. the file length (telling where the compressed
data stops) and the file name (telling you, that the file was
compressed). That's basically the same problem.

thanks and regards
Hadmut




---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com