Compression - Re: Repeated compression of previously compressed data is not impossible,

Author

Re: Repeated compression of previously compressed data is not impossible,

Ben Rudiak-Gould

2005-12-11, 6:55 pm

jules.stocks@gmail.com wrote:
> STEP: 1MERIT: 74.95117188% 61400:ok 20520:ng

Let's concentrate on this first line. In this case the compressor sends just
four bits to the decompressor, which, on the basis of those four bits alone,
reconstructs a file which differs from the original in just 20520 of 81920 bits.

Since the decompressor only has four bits to work with, it can produce at
most 16 different reconstructed files. I'll assume that all 16 of those
files have a length of 10K.

Given any file of 10K, the number of 10K files differing from that file in
at most 20520 bits is exactly sum{i=0 to 20520} choose(81920,i), which is an
integer between 2^66515 and 2^66516. If you assume that your 16 different
files are chosen such that there's no overlap in their 20520-differing-bit
neighborhoods (i.e. any pair of such files differs in at least 41041 bits),
then the number of source files which could be approximated to within 20520
bits using a 4-bit hint is exactly 16 * sum{i=0 to 20520} choose(81920,i),
which is an integer between 2^66519 and 2^66520.

The number of files of length 10K is exactly 2^81920, so the chance that a
10K file selected uniformly at random will be compressible to the degree
indicated above is less than 1 in 2^15400. This is vastly less probable than
factoring RSA-2048 by guessing the factors correctly on your first try.

Another example:

> STEP:64MERIT: 97.94677734% 80238:ok 1682:ng

The number of 10K files differing from a 10K file in at most 1682 bits is
exactly sum{i=0 to 1682} choose(81920,i), which is an integer between
2^11824 and 2^11825. Using 256 bits you can approximate at most 2^256 times
that many files to that accuracy. So the chance that a 10K file selected
uniformly at random will be compressible to the degree indicated above is
less than 1 in 2^(81920-11825-256) = 1 in 2^69839.

-- Ben

Ben Rudiak-Gould

2005-12-12, 6:56 pm

jules.stocks@gmail.com wrote:
> It's like we're in different worlds, with different physical laws!

Look, it's very simple: I proved that it's impossible to obtain the
compression figures you quoted on the overwhelming majority of possible
input files. Your choices are:

(a) Deny my premises. ("I never claimed it could do that.")
(b) Point out a flaw in my reasoning.
(c) Deny the validity of mathematical proof as a path to knowledge.
(d) Talk about something else.

You seem to have picked (d). Admittedly, politicians are pretty successful
with (d), but that's because people are gullible, not because the
politicians are correct.

For what it's worth, I suggest (a). If you simply claim that you can
compress every 10K file that *actually exists in the real world*, then I
would have no problem with that. I certainly don't believe you can do it,
but I'll stop saying it's logically impossible, because it isn't. What
you're currently claiming is that you can compress random data, which is
another matter entirely.

> That listing was made from an actual compression.

That statement means nothing to me, because you haven't established a trust
path. It ought to mean something to you, though! Think about it: I proved
that something is impossible. You have a program which does the impossible
thing. What's wrong with this picture? Only you can answer that question,
because only you have access to both the proof and the program. Something's
got to give, and if I were you I wouldn't be able to rest until I figured
out what it is.

> Ben, I appreciate your reasoning but there is a little something
> (several 'little' somethings, actually) which I am not disclosing --
> these are novel improvements that I've invented to enable my process to
> work.

It was surprising how many of our authors failed to realise that
*to attack an argument, you must find something wrong in it*.
Several authors believed that you can avoid a proof by simply
doing something else.

-- Wilfrid Hodges, _An Editor Recalls Some Hopeless Papers_
(emphasis his)

> Private note headed your way.

I eagerly await it.

-- Ben

Sponsored Links