Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compression > #675 > unrolled thread

a friend wants proof...

Back to article view | Back to comp.compression

Contents

  a friend wants proof... Einstein <michaelhh@gmail.com> - 2012-01-02 12:57 -0800
    Re: a friend wants proof... pfraser <pete_fraser@comcast.net> - 2012-01-02 15:03 -0800
      Re: a friend wants proof... Michael <michaelhh@gmail.com> - 2012-01-02 23:04 -0800
    Re: a friend wants proof... Jim Leonard <mobygamer@gmail.com> - 2012-01-03 08:17 -0800
      Re: a friend wants proof... Jim Leonard <mobygamer@gmail.com> - 2012-01-03 08:18 -0800
    Re: a friend wants proof... Sebastian <s.gesemann@gmail.com> - 2012-01-08 04:52 -0800
      Re: a friend wants proof... Sebastian <s.gesemann@gmail.com> - 2012-01-08 05:03 -0800
        Re: a friend wants proof... Jim Leonard <mobygamer@gmail.com> - 2012-01-09 08:29 -0800
      Re: a friend wants proof... Alex Mizrahi <alex.mizrahi@gmail.com> - 2012-01-09 20:03 +0200
        Re: a friend wants proof... Sebastian <s.gesemann@gmail.com> - 2012-01-09 15:10 -0800

#675 — a friend wants proof...

Ok so I know this is a silly question, so do not hit me on the head
please.

What is the highest percentage of compression on RAND data achieved?

What links can you provide to show that compression on them is not
possible?

And what rewards exist (as proof of inability) for compressing RAND?


Be kind... just act like a 10 year old is asking the question, k?

[toc] | [next] | [standalone]

#679

Einstein wrote:
> Ok so I know this is a silly question, so do not hit me on the head
> please.
>
> What is the highest percentage of compression on RAND data achieved?
>
> What links can you provide to show that compression on them is not
> possible?
>
> And what rewards exist (as proof of inability) for compressing RAND?
>
>
> Be kind... just act like a 10 year old is asking the question, k?

I think the counting argument is good and simple.
A random source can generate any sequence.
Some of these sequences will be compressible.

However, there's no way that you can, on average, compress
all sequences from a random source.
Imagine that you could do that.
Inevitably more than one source sequence would compress
to the same output sequence (because the output sequences
are, on average, shorter than the source sequences,
so there are fewer of them. You then have no way of knowing
which of the (two or more) distinct source sequences resulted in
the compressed sequence. So you can't decompress.

[toc] | [prev] | [next] | [standalone]

#682

On Jan 2, 3:03 pm, pfraser <pete_fra...@comcast.net> wrote:
> Einstein wrote:
> > Ok so I know this is a silly question, so do not hit me on the head
> > please.
>
> > What is the highest percentage of compression on RAND data achieved?
>
> > What links can you provide to show that compression on them is not
> > possible?
>
> > And what rewards exist (as proof of inability) for compressing RAND?
>
> > Be kind... just act like a 10 year old is asking the question, k?
>
> I think the counting argument is good and simple.
> A random source can generate any sequence.
> Some of these sequences will be compressible.
>
> However, there's no way that you can, on average, compress
> all sequences from a random source.
> Imagine that you could do that.
> Inevitably more than one source sequence would compress
> to the same output sequence (because the output sequences
> are, on average, shorter than the source sequences,
> so there are fewer of them. You then have no way of knowing
> which of the (two or more) distinct source sequences resulted in
> the compressed sequence. So you can't decompress.

Only one reply? Do not be so dead. I need to show him everyones
thoughts here on this at 8am!

*yawn*



Predicted question


"But what if you could get random data to compress one time to say 90%
of its size?"

How bout a Doctorate handles that question for me so I can show my
friend?

[toc] | [prev] | [next] | [standalone]

#688

On Jan 2, 2:57 pm, Einstein <michae...@gmail.com> wrote:
> What links can you provide to show that compression on them is not
> possible?

http://en.wikipedia.org/wiki/Pigeonhole_principle

> And what rewards exist (as proof of inability) for compressing RAND?

I'm not sure I understand the exact wording of your question, but
here's a simple non-math explanation of why it is impossible to
compress every sequence:  Assume someone claims they have come up with
a method to compress any data by at least one byte.  The logical
extension of that claim is that you can then take the output of that
process and run it through again, shaving another byte off of the
data.  What happens when you do this so many times that you reach one
byte of output?  One byte can hold a single value between 0 and 255,
is that all of your original data?  Even if the byte points to a
gigantic index of data, that byte can only point to one of 256
different values, so that byte can represent 256 different sets of
data.  Because there are nearly infinite combinations of data in the
universe, how likely is it that one of 256 different sets of data was
your original input?

If someone claims to be able to compress RANDOM data -- data where its
contents cannot possibly be known beforehand because it is RANDOM --
then they are, by extension, claiming they have come up with a method
that can compress any input sequence.  That claim is provably false.

[toc] | [prev] | [next] | [standalone]

#689

On Jan 3, 10:17 am, Jim Leonard <mobyga...@gmail.com> wrote:
> On Jan 2, 2:57 pm, Einstein <michae...@gmail.com> wrote:
>
> > What links can you provide to show that compression on them is not
> > possible?

Sorry, a more specific link is:  http://en.wikipedia.org/wiki/Pigeonhole_principle#Uses_and_applications

[toc] | [prev] | [next] | [standalone]

#735

On Jan 2, 9:57 pm, Einstein wrote:
>
> Be kind... just act like a 10 year old is asking the question, k?
> What is the highest percentage of compression on RAND data achieved?

That depends on what it is exactly that you are talking about. What is
your definition of "RAND data", for example? And what compression
performance are we talking about? The expected compression ratio? To
be able to say something about what to _expect_ we would have to know
the probability distribution of possible input files to the compressor
(this is called a "source model").

Assuming that all possible files are equally likely "to occur" there
is no computer program that can map these files in a way so that the
expected compression ratio is smaller than 1.0 unless you allow data
loss.

Proof:
Let's restrict the set of possible input files to a set of files with
no more than N symbols of an alphabet A. Let's call this set X. A
deterministic "compressor" can simply be modeled as a function c that
maps elements from this set X to something else. Since we are
interested in lossless compression (in this case), this mapping has to
be injective. Since we are interested in a lower bound on the expected
compression ratio we can limit the focus to functions that map
elements from X to elements from X:
  c : X |--> X
Why? Because adding any larger files (with more than N symbols) to the
image of c won't help minimizing the expected compression ratio. Any
smaller set won't do either because of the injectivity requirement.
This requirement also makes c a permutation in this case. Since we
assumed every file to be equally likely, it does not actually matter
what kind of permutation c is. c won't affect the probability
distribution of the compressor's output at all. The files that the
compressor will be giving us will also be equally distributed and have
the _same_ expected file size as the compressor's input since it's the
same set and probability distribution. The expected compression ratio
is the expected output file size divided by the expected input file
size. So, regardless of what kind of permutation c actually is, the
expected compression ratio will always be 1 (= no compression at all).
You can't do any better than that.

They key here is the probability distribution. If some input files are
MORE likely than others, THEN you have a chance to write a lossless
compressor that turns larger files to smaller ones ON AVERAGE.
Luckily, most real life data is not random gibberish. You would not
expect the sequence "x03dkj" to be equally likely to occur in English
text as the word "expect", would you? No. And that's why lossless
compression actually works.

HTH,
SG

[toc] | [prev] | [next] | [standalone]

#736

On Jan 8, 1:52 pm, Sebastian wrote:
> Proof:
> Let's restrict the set of possible input files to a set of files with
> no more than N symbols of an alphabet A. Let's call this set X. A
> deterministic "compressor" can simply be modeled as a function c that
> maps elements from this set X to something else. Since we are
> interested in lossless compression (in this case), this mapping has to
> be injective. Since we are interested in a lower bound on the expected
> compression ratio we can limit the focus to functions that map
> elements from X to elements from X:
>   c : X |--> X
> Why? Because adding any larger files (with more than N symbols) to the
> image of c won't help minimizing the expected compression ratio. Any
> smaller set won't do either because of the injectivity requirement.

Of course, one could choose

  c: X |--> Y

with |X|==|Y| with X containing larger files by removing short ones
from X while short files are still in Y. This makes expected
compression ratios below 1.0 possible. But since X!=Y this won't allow
"recursive compression". The number of times you can apply c depends
on the input because -- eventually -- you'll arrive at a file that is
not part of X anymore. The metadata you would need to tell the decoder
how many times to invert c (including zero times if the input is not
in X already) will make the gains you get by applying c in the first
place vanish.

> HTH,
> SG

[toc] | [prev] | [next] | [standalone]

#742

On Jan 8, 7:03 am, Sebastian <s.gesem...@gmail.com> wrote:
> Of course, one could choose
>
>   c: X |--> Y
>
> with |X|==|Y| with X containing larger files by removing short ones
> from X while short files are still in Y. This makes expected
> compression ratios below 1.0 possible. But since X!=Y this won't allow
> "recursive compression". The number of times you can apply c depends
> on the input because -- eventually -- you'll arrive at a file that is
> not part of X anymore. The metadata you would need to tell the decoder
> how many times to invert c (including zero times if the input is not
> in X already) will make the gains you get by applying c in the first
> place vanish.

The quote above should be required reading for people attempting to
write "infinite compression" systems.

[toc] | [prev] | [next] | [standalone]

#743

>> Be kind... just act like a 10 year old is asking the question, k?
>> What is the highest percentage of compression on RAND data achieved?

> Assuming that all possible files are equally likely "to occur" there
> is no computer program that can map these files in a way so that the
> expected compression ratio is smaller than 1.0 unless you allow data
> loss.

We know that RAND data passes certain randomness tests. So it cannot be, 
for example, a sequence of zeroes, as it won't pass those randomness tests.

[toc] | [prev] | [next] | [standalone]

#747

On 9 Jan., 19:03, Alex Mizrahi wrote:
> >> Be kind... just act like a 10 year old is asking the question, k?
> >> What is the highest percentage of compression on RAND data achieved?
> > Assuming that all possible files are equally likely "to occur" there
> > is no computer program that can map these files in a way so that the
> > expected compression ratio is smaller than 1.0 unless you allow data
> > loss.
>
> We know that RAND data passes certain randomness tests. So it cannot be,
> for example, a sequence of zeroes, as it won't pass those randomness tests.

No, we don't know that. This is just your interpretation of "RAND
data" or your definition actually. It's as good as any other. But why
stop there? I would love to see a proper answer to the original
question using this interpretation of "RAND data". This should be a
fun math exercise...

Cheers!
SG

[toc] | [prev] | [standalone]

Back to top | Article view | comp.compression

csiph-web