Algorithm that makes maximum compression of completly diffused data.

Tim Roberts timr at probo.com
Sat Nov 2 22:31:09 CET 2013


jonas.thornvall at gmail.com wrote:
>
>Well then i have news for you.

Well, then, why don't you share it?

Let me try to get you to understand WHY what you say is impossible.  Let's
say you do have a function f(x) that can produce a compressed output y for
any given x, such that y is always smaller than x.  If that were true, then
I could call f() recursively:
    f(f(...f(f(f(f(f(x)))))...))
and eventually the result get down to a single bit.  I hope it is clear
that there's no way to restore a single bit back into different source
texts.

Here's another way to look at it.  If f(x) is smaller than x for every x,
that means there MUST me multiple values of x that produce the same f(x).
Do you see?  If x is three bits and f(x) is two bits, that means there are
8 possible values for x but only 4 values for f(x).  So, given an f(x), you
cannot tell which value of x it came from.  You have lost information.
-- 
Tim Roberts, timr at probo.com
Providenza & Boekelheide, Inc.



More information about the Python-list mailing list