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

Groups > comp.lang.python > #111276 > unrolled thread

Compression of random binary data

Back to article view | Back to comp.lang.python

Contents

  Compression of random binary data jonas.thornvall@gmail.com - 2016-07-11 10:52 -0700
    Re: Compression of random binary data Joonas Liik <liik.joonas@gmail.com> - 2016-07-11 21:09 +0300
      Re: Compression of random binary data jonas.thornvall@gmail.com - 2016-07-11 11:24 -0700
        Re: Compression of random binary data jonas.thornvall@gmail.com - 2016-07-11 11:32 -0700
    Re: Compression of random binary data MRAB <python@mrabarnett.plus.com> - 2016-07-11 19:30 +0100
    Re: Compression of random binary data Steven D'Aprano <steve@pearwood.info> - 2016-07-12 04:38 +1000
      Re: Compression of random binary data jonas.thornvall@gmail.com - 2016-07-12 07:24 -0700
        Re: Compression of random binary data Steven D'Aprano <steve@pearwood.info> - 2016-07-13 01:11 +1000
          Re: Compression of random binary data jonas.thornvall@gmail.com - 2016-07-12 10:35 -0700
            Re: Compression of random binary data Ian Kelly <ian.g.kelly@gmail.com> - 2016-07-12 16:23 -0600
              Re: Compression of random binary data jonas.thornvall@gmail.com - 2016-07-12 17:43 -0700
              Re: Compression of random binary data jonas.thornvall@gmail.com - 2016-07-12 17:47 -0700
            Re: Compression of random binary data Steven D'Aprano <steve@pearwood.info> - 2016-07-13 12:29 +1000
              Re: Compression of random binary data jonas.thornvall@gmail.com - 2016-07-13 02:46 -0700
                Re: Compression of random binary data Steven D'Aprano <steve@pearwood.info> - 2016-07-13 23:11 +1000
                Re: [OT] Compression of random binary data Michael Torrie <torriem@gmail.com> - 2016-07-13 13:03 -0600
                  Re: [OT] Compression of random binary data Marko Rauhamaa <marko@pacujo.net> - 2016-07-13 22:35 +0300
                    Re: [OT] Compression of random binary data Tim Delaney <timothy.c.delaney@gmail.com> - 2016-07-14 08:39 +1000
                Re: [OT] Compression of random binary data Grant Edwards <grant.b.edwards@gmail.com> - 2016-07-13 19:34 +0000
              Re: Compression of random binary data jonas.thornvall@gmail.com - 2016-07-13 03:04 -0700
                Re: Compression of random binary data jonas.thornvall@gmail.com - 2016-07-13 03:14 -0700
                Re: Compression of random binary data Steven D'Aprano <steve@pearwood.info> - 2016-07-13 22:13 +1000
    Re: Compression of random binary data Nobody <nobody@nowhere.invalid> - 2016-07-11 19:56 +0100
    Re: Compression of random binary data MRAB <python@mrabarnett.plus.com> - 2016-07-11 19:57 +0100
    Re: Compression of random binary data Terry Reedy <tjreedy@udel.edu> - 2016-07-11 15:31 -0400
    Re: Compression of random binary data Michael Selik <michael.selik@gmail.com> - 2016-07-12 00:36 +0000
    Re: Compression of random binary data Lawrence D’Oliveiro <lawrencedo99@gmail.com> - 2016-07-11 20:01 -0700
      Re: Compression of random binary data jonas.thornvall@gmail.com - 2016-07-12 07:29 -0700
        Re: Compression of random binary data Steven D'Aprano <steve@pearwood.info> - 2016-07-13 01:17 +1000
          Re: Compression of random binary data jonas.thornvall@gmail.com - 2016-07-12 10:46 -0700
            Re: Compression of random binary data Michael Torrie <torriem@gmail.com> - 2016-07-12 12:20 -0600
              Re: Compression of random binary data jonas.thornvall@gmail.com - 2016-07-12 12:31 -0700
              Re: Compression of random binary data jonas.thornvall@gmail.com - 2016-07-12 12:40 -0700
                Re: Compression of random binary data jonas.thornvall@gmail.com - 2016-07-12 12:42 -0700
        Re: Compression of random binary data mm0fmf <none@invalid.com> - 2016-07-12 17:32 +0100

Page 1 of 2  [1] 2  Next page →

#111276 — Compression of random binary data

What kind of statistic law or mathematical conjecture  or is it even a physical law is violated by compression of random binary data? 

I only know that Shanon theorised it could not be done, but were there any proof? 

What is to say that you can not do it if the symbolic representation is richer than the symbolic represenatation of the dataset. 

Isn't it a fact that the set of squareroots actually depict numbers in a shorter way than their actual representation. 

Now the inpretator or program must know the rules. And i have very good rules to make it happen. 

[toc] | [next] | [standalone]

#111277

On 11 July 2016 at 20:52,  <jonas.thornvall@gmail.com> wrote:
> What kind of statistic law or mathematical conjecture  or is it even a physical law is violated by compression of random binary data?
>
> I only know that Shanon theorised it could not be done, but were there any proof?

Compression relies on some items in the dataset being more frequent
than others, if you have some dataset that is completely random it
would be hard to compress as most items have very similar number of
occurrances.

> What is to say that you can not do it if the symbolic representation is richer than the symbolic represenatation of the dataset.
>
> Isn't it a fact that the set of squareroots actually depict numbers in a shorter way than their actual representation.

A square root may be smaller numerically than a number but it
definitely is not smaller in terms of entropy.

lets try to compress the number 2 for instance using square roots.
sqrt(2) = 1.4142
the square root actually takes more space in this case even tho it is
a smaller number. so having the square root would have negative
compression in this case.
with some rounding back and forth we can probably get around the fact
that sqrt(2) would take an infinite amout of memory to accurately
represent but that neccesarily means restricting the values we are
possible of encoding.

for sqrt(2) to not have worse space consumprion than the number 2
itself we basically have to trow away precision so sqrt(2) ~= 1
now i challenge you to get that 2 back out of that 1..

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

#111279

Den måndag 11 juli 2016 kl. 20:09:39 UTC+2 skrev Waffle:
> On 11 July 2016 at 20:52,  <jonas.thornvall@gmail.com> wrote:
> > What kind of statistic law or mathematical conjecture  or is it even a physical law is violated by compression of random binary data?
> >
> > I only know that Shanon theorised it could not be done, but were there any proof?
> 
> Compression relies on some items in the dataset being more frequent
> than others, if you have some dataset that is completely random it
> would be hard to compress as most items have very similar number of
> occurrances.
> 
> > What is to say that you can not do it if the symbolic representation is richer than the symbolic represenatation of the dataset.
> >
> > Isn't it a fact that the set of squareroots actually depict numbers in a shorter way than their actual representation.
> 
> A square root may be smaller numerically than a number but it
> definitely is not smaller in terms of entropy.
> 
> lets try to compress the number 2 for instance using square roots.
> sqrt(2) = 1.4142
> the square root actually takes more space in this case even tho it is
> a smaller number. so having the square root would have negative
> compression in this case.
> with some rounding back and forth we can probably get around the fact
> that sqrt(2) would take an infinite amout of memory to accurately
> represent but that neccesarily means restricting the values we are
> possible of encoding.
> 
> for sqrt(2) to not have worse space consumprion than the number 2
> itself we basically have to trow away precision so sqrt(2) ~= 1
> now i challenge you to get that 2 back out of that 1..

Well who it to say different kind of numbers isn't treated differently, i mean all numbers isn't squares. All numbers isn't naturals.

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

#111281

Den måndag 11 juli 2016 kl. 20:24:37 UTC+2 skrev jonas.t...@gmail.com:
> Den måndag 11 juli 2016 kl. 20:09:39 UTC+2 skrev Waffle:
> > On 11 July 2016 at 20:52,  <jonas.thornvall@gmail.com> wrote:
> > > What kind of statistic law or mathematical conjecture  or is it even a physical law is violated by compression of random binary data?
> > >
> > > I only know that Shanon theorised it could not be done, but were there any proof?
> > 
> > Compression relies on some items in the dataset being more frequent
> > than others, if you have some dataset that is completely random it
> > would be hard to compress as most items have very similar number of
> > occurrances.
> > 
> > > What is to say that you can not do it if the symbolic representation is richer than the symbolic represenatation of the dataset.
> > >
> > > Isn't it a fact that the set of squareroots actually depict numbers in a shorter way than their actual representation.
> > 
> > A square root may be smaller numerically than a number but it
> > definitely is not smaller in terms of entropy.
> > 
> > lets try to compress the number 2 for instance using square roots.
> > sqrt(2) = 1.4142
> > the square root actually takes more space in this case even tho it is
> > a smaller number. so having the square root would have negative
> > compression in this case.
> > with some rounding back and forth we can probably get around the fact
> > that sqrt(2) would take an infinite amout of memory to accurately
> > represent but that neccesarily means restricting the values we are
> > possible of encoding.
> > 
> > for sqrt(2) to not have worse space consumprion than the number 2
> > itself we basically have to trow away precision so sqrt(2) ~= 1
> > now i challenge you to get that 2 back out of that 1..
> 
> Well who it to say different kind of numbers isn't treated differently, i mean all numbers isn't squares. All numbers isn't naturals.

But it could be all numbers are foldable. Both the integer parts and the real parts.And be expressed by the folding differences.

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

#111280

On 2016-07-11 18:52, jonas.thornvall@gmail.com wrote:
> What kind of statistic law or mathematical conjecture  or is it even a physical law is violated by compression of random binary data?
>
> I only know that Shanon theorised it could not be done, but were there any proof?
>
> What is to say that you can not do it if the symbolic representation is richer than the symbolic represenatation of the dataset.
>
> Isn't it a fact that the set of squareroots actually depict numbers in a shorter way than their actual representation.
>
> Now the inpretator or program must know the rules. And i have very good rules to make it happen.
>
If you want a challenge:

The Enduring Challenge of Compressing Random Data
http://www.drdobbs.com/architecture-and-design/the-enduring-challenge-of-compressing-ra/240049914

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

#111282

On Tue, 12 Jul 2016 03:52 am, jonas.thornvall@gmail.com wrote:

> What kind of statistic law or mathematical conjecture  or is it even a
> physical law is violated by compression of random binary data?

The pigeon hole principle. If you have 100 pigeon holes, and 101 pigeons,
then clearly at least one pigeon hole must have two pigeons in it.

To keep the numbers small and manageable, let's say we are going to compress
one byte at a time. Now a byte has eight bits, so there are exactly 256
possible bytes:

0000 0000
0000 0001
0000 0010
...
1111 1110
1111 1111

Now, suppose I claim that I can LOSSLESSLY (that is, reversibly) compress
any random byte to just two bits. The lossless part is important: its not
hard to compress random data by irreversibly throwing some of it away, and
there's no violation there.

So I claim that you can give me any random byte, I will compress it to just
two bits:

00
01
10
11

and then be able to decompress it back again to give you the original byte
once more.

Obviously I'm trying to pull a fast one! There's no way I can do this. I can
squeeze 256 pigeons into just four pigeon holes, but only by doubling them
up. Suppose I compress these three bytes to 00:

0000 0000
0110 1001
1100 0110

Now when I go to uncompress 00, what should I return? There is no way for me
to know which of the three was the original value.

(If I'm cunning, I'll have sneakily stored some data *elsewhere*, say, in
the file name, or in a database, so that you need this extra hidden data to
uncompress the 00 back to a full byte. But then I'm not compressing eight
bits down to two. I'm compressing eight bits down to two bits plus
who-knows-how-many-bits of hidden data.)

So the pigeon hole principle tells us one of two things:

(1) If you compress random data, then it must be lossy; I can compress eight
bits to two, but then I can't uncompress it back again, at least not
without throwing away some data.

(2) Or, if the compression is lossless, then some data must be expanded
rather than compressed. If you pick data at random, some of it will be
expanded.

Suppose I have a compression algorithm that infallibly and reversibly
compresses as follows:

0000 0000 <--> 00
0000 0001 <--> 01
0000 0010 <--> 10
0000 0011 <--> 11

That part is fine. But what will my algorithm do with the other 252 bytes?
At *best* it will leave them untouched:

0000 0100 <--> 0000 0100
...
1111 1111 <--> 1111 1111

which is no compression at all, but at worst it will actually expand them
and make them bigger. (After all, it's likely that my compression format
has at least a bit of overhead.)

In practice, compression algorithms are designed to look for particular
kinds of order or structure in the data, and compress that. That's fine for
the sorts of non-random data we care about: pictures are rarely pictures of
static, text files are rarely random collections of bits. But if you do
throw a random set of bits at a lossless compression algorithm, it will at
best not compress it at all, and at worst actually make the file bigger.


> What is to say that you can not do it if the symbolic representation is
> richer than the symbolic represenatation of the dataset.
> 
> Isn't it a fact that the set of squareroots actually depict numbers in a
> shorter way than their actual representation.

Sure. But you need to know what √2 means. It *represents* the number
1.41421356237... but doesn't compress it. There's nothing you can do to the
symbol √2 that will uncompress back to the infinite series of digits. All
you can do is look it up somewhere to see what the digits are.

> Now the inpretator or program must know the rules. And i have very good
> rules to make it happen.

Right. How much information is in the rules? More than you save with
the "compression". Consider:

1.41421356237 compressed down to √2, that's 13 characters down to 2. Great!
But to *uncompress*, you need to store a rule:

√2=1.41421356237 

and that's *sixteen* characters. So your "compression" is:

original: 13
compressed to: 2
plus rule: 16

means you have "compressed" 13 characters to 18.

Now, this is still worth doing if you need to repeat the √2 many times, so
long as you don't have to repeat the rule. That's useful. But it's not
compression. It's more like keeping an index to a database, or a scrap of
paper with the title of a book written on it:

"See Lord Of The Rings, by J.R.R. Tolkien"

That's a lot smaller than the actual book: eight words, instead of who knows
how many tens of thousands. But you can't call it compression: you can't
sit down with the scrap of paper *and nothing else* and uncompress it back
to the entire LOTR trilogy.




-- 
Steven
“Cheer up,” they said, “things could be worse.” So I cheered up, and sure
enough, things got worse.

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

#111338

Den måndag 11 juli 2016 kl. 20:38:51 UTC+2 skrev Steven D'Aprano:
> On Tue, 12 Jul 2016 03:52 am, jonas.thornvall@gmail.com wrote:
> 
> > What kind of statistic law or mathematical conjecture  or is it even a
> > physical law is violated by compression of random binary data?
> 
> The pigeon hole principle. If you have 100 pigeon holes, and 101 pigeons,
> then clearly at least one pigeon hole must have two pigeons in it.
> 
> To keep the numbers small and manageable, let's say we are going to compress
> one byte at a time. Now a byte has eight bits, so there are exactly 256
> possible bytes:
> 
> 0000 0000
> 0000 0001
> 0000 0010
> ...
> 1111 1110
> 1111 1111
> 
> Now, suppose I claim that I can LOSSLESSLY (that is, reversibly) compress
> any random byte to just two bits. The lossless part is important: its not
> hard to compress random data by irreversibly throwing some of it away, and
> there's no violation there.
> 
> So I claim that you can give me any random byte, I will compress it to just
> two bits:
> 
> 00
> 01
> 10
> 11
> 
> and then be able to decompress it back again to give you the original byte
> once more.
> 
> Obviously I'm trying to pull a fast one! There's no way I can do this. I can
> squeeze 256 pigeons into just four pigeon holes, but only by doubling them
> up. Suppose I compress these three bytes to 00:
> 
> 0000 0000
> 0110 1001
> 1100 0110
> 
> Now when I go to uncompress 00, what should I return? There is no way for me
> to know which of the three was the original value.
> 
> (If I'm cunning, I'll have sneakily stored some data *elsewhere*, say, in
> the file name, or in a database, so that you need this extra hidden data to
> uncompress the 00 back to a full byte. But then I'm not compressing eight
> bits down to two. I'm compressing eight bits down to two bits plus
> who-knows-how-many-bits of hidden data.)
> 
> So the pigeon hole principle tells us one of two things:
> 
> (1) If you compress random data, then it must be lossy; I can compress eight
> bits to two, but then I can't uncompress it back again, at least not
> without throwing away some data.
> 
> (2) Or, if the compression is lossless, then some data must be expanded
> rather than compressed. If you pick data at random, some of it will be
> expanded.
> 
> Suppose I have a compression algorithm that infallibly and reversibly
> compresses as follows:
> 
> 0000 0000 <--> 00
> 0000 0001 <--> 01
> 0000 0010 <--> 10
> 0000 0011 <--> 11
> 
> That part is fine. But what will my algorithm do with the other 252 bytes?
> At *best* it will leave them untouched:
> 
> 0000 0100 <--> 0000 0100
> ...
> 1111 1111 <--> 1111 1111
> 
> which is no compression at all, but at worst it will actually expand them
> and make them bigger. (After all, it's likely that my compression format
> has at least a bit of overhead.)
> 
> In practice, compression algorithms are designed to look for particular
> kinds of order or structure in the data, and compress that. That's fine for
> the sorts of non-random data we care about: pictures are rarely pictures of
> static, text files are rarely random collections of bits. But if you do
> throw a random set of bits at a lossless compression algorithm, it will at
> best not compress it at all, and at worst actually make the file bigger.
> 
> 
> > What is to say that you can not do it if the symbolic representation is
> > richer than the symbolic represenatation of the dataset.
> > 
> > Isn't it a fact that the set of squareroots actually depict numbers in a
> > shorter way than their actual representation.
> 
> Sure. But you need to know what √2 means. It *represents* the number
> 1.41421356237... but doesn't compress it. There's nothing you can do to the
> symbol √2 that will uncompress back to the infinite series of digits. All
> you can do is look it up somewhere to see what the digits are.
> 
> > Now the inpretator or program must know the rules. And i have very good
> > rules to make it happen.
> 
> Right. How much information is in the rules? More than you save with
> the "compression". Consider:
> 
> 1.41421356237 compressed down to √2, that's 13 characters down to 2. Great!
> But to *uncompress*, you need to store a rule:
> 
> √2=1.41421356237 
> 
> and that's *sixteen* characters. So your "compression" is:
> 
> original: 13
> compressed to: 2
> plus rule: 16
> 
> means you have "compressed" 13 characters to 18.
> 
> Now, this is still worth doing if you need to repeat the √2 many times, so
> long as you don't have to repeat the rule. That's useful. But it's not
> compression. It's more like keeping an index to a database, or a scrap of
> paper with the title of a book written on it:
> 
> "See Lord Of The Rings, by J.R.R. Tolkien"
> 
> That's a lot smaller than the actual book: eight words, instead of who knows
> how many tens of thousands. But you can't call it compression: you can't
> sit down with the scrap of paper *and nothing else* and uncompress it back
> to the entire LOTR trilogy.
> 
> 
> 
> 
> -- 
> Steven
> “Cheer up,” they said, “things could be worse.” So I cheered up, and sure
> enough, things got worse.

But it seem your reasoning is based upon interpretation of the actual digits, bits and bytes value. There could be different interpretation worlds of course you would have to chose one using digits, An interpretationworld here could be reading out different word lengths of the dataset and maybe a lookup table.


But it could also be arithmetic rules that magically recreate a number from a number of folds or difference of folds.

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

#111341

On Wed, 13 Jul 2016 12:24 am, jonas.thornvall@gmail.com wrote:

> Den måndag 11 juli 2016 kl. 20:38:51 UTC+2 skrev Steven D'Aprano:
>> On Tue, 12 Jul 2016 03:52 am, jonas.thornvall@gmail.com wrote:
>> 
>> > What kind of statistic law or mathematical conjecture  or is it even a
>> > physical law is violated by compression of random binary data?
>> 
>> The pigeon hole principle. If you have 100 pigeon holes, and 101 pigeons,
>> then clearly at least one pigeon hole must have two pigeons in it.
[...]
> But it seem your reasoning is based upon interpretation of the actual
> digits, bits and bytes value.

Not at all. If you think that, you've misread my example. There's no
interpretation of the bytes: they are just 8-bit numbers from 0 to 255. You
cannot losslessly compress all 256 of them to just four 2-bit numbers.


> There could be different interpretation 
> worlds of course you would have to chose one using digits, An 
> interpretationworld here could be reading out different word lengths of
> the dataset and maybe a lookup table.

Any lookup table you have counts as part of the compressed data.


> But it could also be arithmetic rules that magically recreate a number
> from a number of folds or difference of folds.

Oh, sure, if you believe in magic, anything is possible. Just close your
eyes, click your heels together, and wish really, really hard.

Suppose I could compress ANY random data, no matter what, down to 10% of the
original size. Okay, let's start with a million bits of data. Compress it
down to 100,000 bits.

But I believe that I can compress *anything*, any random collection of data.
Okay, let me compress it again. Now I have 10,000 bits.

Compress it again. Now I have 1,000 bits.

Compress it again. Now I have 100 bits.

Compress it again. Now I have 10 bits.

Compress it again. Now I have 1 bit, either a 0 or a 1.


Can you not see how absurd this is? I have claimed that I can take *any*
random set of data, and by compressing it again and again and again,
compress it down to ONE BIT, either a 0 or a 1, WITHOUT LOSS. Somehow I
have to take that 0 bit and uncompress it back to the Complete Works Of
William Shakespeare, and *also* uncompress it back to the recent Deadpool
movie, AND uncompress it back to last year's Ant Man movie, AND uncompress
it back to some funny picture of a cat.

How can I possibly know which of the billions and billions of different
files this 0 bit represents?

If you pass me a 0 bit, and say "uncompress this", and I get The Lord Of The
Rings novels, and then you pass me another 0 bit, and I uncompress it and
get The Hobbit, well, how did I tell the two bits apart? They're both zero.



The alternative is to say, it doesn't matter how clever you are, you can't
compress *everything*. There are some things that simply won't compress.
Eventually you get something no longer compresses. If you could compress
EVERYTHING, then you could compress the compressed data, and compress the
compressed-compressed data, and so on, until you've got only a single bit.
And that is ridiculous.



-- 
Steven
“Cheer up,” they said, “things could be worse.” So I cheered up, and sure
enough, things got worse.

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

#111345

Den tisdag 12 juli 2016 kl. 17:12:01 UTC+2 skrev Steven D'Aprano:
> On Wed, 13 Jul 2016 12:24 am, jonas.thornvall@gmail.com wrote:
> 
> > Den måndag 11 juli 2016 kl. 20:38:51 UTC+2 skrev Steven D'Aprano:
> >> On Tue, 12 Jul 2016 03:52 am, jonas.thornvall@gmail.com wrote:
> >> 
> >> > What kind of statistic law or mathematical conjecture  or is it even a
> >> > physical law is violated by compression of random binary data?
> >> 
> >> The pigeon hole principle. If you have 100 pigeon holes, and 101 pigeons,
> >> then clearly at least one pigeon hole must have two pigeons in it.
> [...]
> > But it seem your reasoning is based upon interpretation of the actual
> > digits, bits and bytes value.
> 
> Not at all. If you think that, you've misread my example. There's no
> interpretation of the bytes: they are just 8-bit numbers from 0 to 255. You
> cannot losslessly compress all 256 of them to just four 2-bit numbers.
> 
> 
> > There could be different interpretation 
> > worlds of course you would have to chose one using digits, An 
> > interpretationworld here could be reading out different word lengths of
> > the dataset and maybe a lookup table.
> 
> Any lookup table you have counts as part of the compressed data.
> 
> 
> > But it could also be arithmetic rules that magically recreate a number
> > from a number of folds or difference of folds.
> 
> Oh, sure, if you believe in magic, anything is possible. Just close your
> eyes, click your heels together, and wish really, really hard.
> 
> Suppose I could compress ANY random data, no matter what, down to 10% of the
> original size. Okay, let's start with a million bits of data. Compress it
> down to 100,000 bits.
> 
> But I believe that I can compress *anything*, any random collection of data.
> Okay, let me compress it again. Now I have 10,000 bits.
> 
> Compress it again. Now I have 1,000 bits.
> 
> Compress it again. Now I have 100 bits.
> 
> Compress it again. Now I have 10 bits.
> 
> Compress it again. Now I have 1 bit, either a 0 or a 1.
> 
> 
> Can you not see how absurd this is? I have claimed that I can take *any*
> random set of data, and by compressing it again and again and again,
> compress it down to ONE BIT, either a 0 or a 1, WITHOUT LOSS. Somehow I
> have to take that 0 bit and uncompress it back to the Complete Works Of
> William Shakespeare, and *also* uncompress it back to the recent Deadpool
> movie, AND uncompress it back to last year's Ant Man movie, AND uncompress
> it back to some funny picture of a cat.
> 
> How can I possibly know which of the billions and billions of different
> files this 0 bit represents?
> 
> If you pass me a 0 bit, and say "uncompress this", and I get The Lord Of The
> Rings novels, and then you pass me another 0 bit, and I uncompress it and
> get The Hobbit, well, how did I tell the two bits apart? They're both zero.
> 
> 
> 
> The alternative is to say, it doesn't matter how clever you are, you can't
> compress *everything*. There are some things that simply won't compress.
> Eventually you get something no longer compresses. If you could compress
> EVERYTHING, then you could compress the compressed data, and compress the
> compressed-compressed data, and so on, until you've got only a single bit.
> And that is ridiculous.
> 
> 
> 
> -- 
> Steven
> “Cheer up,” they said, “things could be worse.” So I cheered up, and sure
> enough, things got worse.

No it is only compressible down to a limit given by the algorithm.

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

#111359

On Tue, Jul 12, 2016 at 11:35 AM,  <jonas.thornvall@gmail.com> wrote:
>
> No it is only compressible down to a limit given by the algorithm.

Then your algorithm does not compress random data as you claimed.

For some input, determine the limiting output that it ultimately
compresses down to. Take that output and feed it through your
algorithm as if it were the original input. If the data are to be
considered random, then this input is just as probable as the
original. What output does the algorithm now create? If it just
returns the input unchanged, then how do you discern the original
input from this input when decompressing? If it returns a different
output of the same size, then repeat the process with the new output.
Now there are *two* outputs of that size that can't be repeated. There
are only finitely many possible outputs of that size, so eventually
you're going to have to get to one that either repeats an output -- in
which case your algorithm produces the same output for two different
inputs and is therefore incorrect -- or you will get to an input that
produces an output *larger* in size than the original.

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

#111362

Den onsdag 13 juli 2016 kl. 00:24:23 UTC+2 skrev Ian:
> On Tue, Jul 12, 2016 at 11:35 AM,  <jonas.thornvall@gmail.com> wrote:
> >
> > No it is only compressible down to a limit given by the algorithm.
> 
> Then your algorithm does not compress random data as you claimed.
> 
> For some input, determine the limiting output that it ultimately
> compresses down to. Take that output and feed it through your
> algorithm as if it were the original input. If the data are to be
> considered random, then this input is just as probable as the
> original. What output does the algorithm now create? If it just
> returns the input unchanged, then how do you discern the original
> input from this input when decompressing? If it returns a different
> output of the same size, then repeat the process with the new output.
> Now there are *two* outputs of that size that can't be repeated. There
> are only finitely many possible outputs of that size, so eventually
> you're going to have to get to one that either repeats an output -- in
> which case your algorithm produces the same output for two different
> inputs and is therefore incorrect -- or you will get to an input that
> produces an output *larger* in size than the original.

The dataset must have a certain size that is the only requirment, of course you can not compress something into nothing, at least the arithmetic ruleset need to be encoded but what would be the point to just compress something less than a couple of bytes. And of course the number of rounds you applied the algorithm must be stored. But that is no problem for small datasets.

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

#111363

Den onsdag 13 juli 2016 kl. 00:24:23 UTC+2 skrev Ian:
> On Tue, Jul 12, 2016 at 11:35 AM,  <jonas.thornvall@gmail.com> wrote:
> >
> > No it is only compressible down to a limit given by the algorithm.
> 
> Then your algorithm does not compress random data as you claimed.
> 
> For some input, determine the limiting output that it ultimately
> compresses down to. Take that output and feed it through your
> algorithm as if it were the original input. If the data are to be
> considered random, then this input is just as probable as the
> original. What output does the algorithm now create? If it just
> returns the input unchanged, then how do you discern the original
> input from this input when decompressing? If it returns a different
> output of the same size, then repeat the process with the new output.
> Now there are *two* outputs of that size that can't be repeated. There
> are only finitely many possible outputs of that size, so eventually
> you're going to have to get to one that either repeats an output -- in
> which case your algorithm produces the same output for two different
> inputs and is therefore incorrect -- or you will get to an input that
> produces an output *larger* in size than the original.

The later sounds reasonable that is start toggle between states.

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

#111371

On Wed, 13 Jul 2016 03:35 am, jonas.thornvall@gmail.com wrote:

> No it is only compressible down to a limit given by the algorithm.

Right! Then there is data that you can't compress.

Suppose you have some data:

data = "ABABABABABAB...ABAB"

And you compress it "down to a limit":

x = compress(compress(compress(data)))
print(x)
=> prints "@nx7%k!b"

Now let's try again with something else:

data = "AABBBCCCCDDDDEEEE...ZZZZ"

And you compress it "down to a limit":

x = compress(compress(compress(compress(data))))
print(x)
=> prints "wu*$cS#k-pv32zx[&+r"


One more time:

data = "AABBAABBAABBAABBAABB"
x = compress(data)
print(x)
=> prints "g^x3@"


We agree on this. Now you say, "Give me some random data, anything at all,
and I'll compress it!", and I run a random number generator and out pops:

data = "@nx7%k!b"

or possibly:

data = "wu*$cS#k-pv32zx[&+r"

or:

data = "g^x3@"


and I say "Compress that!"

But we've already agreed that this is as compressed as you can possibly make
it. You can't compress it any more.

So there's *at least some* random data that you can't compress. Surely you
have to accept that. You don't get to say "Oh, I don't mean *that* data, I
mean only data that I can compress". Random data means its random, you
don't get to pick and choose between data you can compress and data that
you can't.

Now the tricky part is to realise that its not just short sequences of
random data that can't be compressed. The same applies for LONG sequences
to. If I give you a gigabyte of raw video, you can probably compress that a
fair bit. That's what things like x264 encoders do. The x265 encoder is
even better. But they're lossy, so you can't reverse them.

But if I give you a gigabyte of random data, you'll be lucky to find *any*
patterns or redundancies that allow compression. You might be able to
shrink the file by a few KB. And if you take that already compressed file,
and try to compress it again, well, you've already hit the limit of
compression. There no more redundancy left to remove.

It doesn't matter how clever you are, or what a "folding structure" is, or
how many times you iterate over the data. It's a matter of absolute
simplicity: the pigeonhole principle. You can't argue with the numbers.

If you start with a 100 digit decimal number, there are 10**100 different
pigeons. If you can compress down to a 6 digit decimal number, there are
10**6 pigeon holes. You cannot put 10*100 pigeons into 10**6 pigeon holes
without doubling up (which makes your compression lossly).

So either some numbers cannot be compressed, or some numbers are compressed
to the same result, and you can't tell which was the original. That's your
choice: a lossless encoder means some numbers can't be compressed, a lossy
encoder means you can't reverse the process exactly.





-- 
Steven
“Cheer up,” they said, “things could be worse.” So I cheered up, and sure
enough, things got worse.

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

#111384

Den onsdag 13 juli 2016 kl. 04:29:48 UTC+2 skrev Steven D'Aprano:
> On Wed, 13 Jul 2016 03:35 am, jonas.thornvall@gmail.com wrote:
> 
> > No it is only compressible down to a limit given by the algorithm.
> 
> Right! Then there is data that you can't compress.
> 
> Suppose you have some data:
> 
> data = "ABABABABABAB...ABAB"
> 
> And you compress it "down to a limit":
> 
> x = compress(compress(compress(data)))
> print(x)
> => prints "@nx7%k!b"
> 
> Now let's try again with something else:
> 
> data = "AABBBCCCCDDDDEEEE...ZZZZ"
> 
> And you compress it "down to a limit":
> 
> x = compress(compress(compress(compress(data))))
> print(x)
> => prints "wu*$cS#k-pv32zx[&+r"
> 
> 
> One more time:
> 
> data = "AABBAABBAABBAABBAABB"
> x = compress(data)
> print(x)
> => prints "g^x3@"
> 
> 
> We agree on this. Now you say, "Give me some random data, anything at all,
> and I'll compress it!", and I run a random number generator and out pops:
> 
> data = "@nx7%k!b"
> 
> or possibly:
> 
> data = "wu*$cS#k-pv32zx[&+r"
> 
> or:
> 
> data = "g^x3@"
> 
> 
> and I say "Compress that!"
> 
> But we've already agreed that this is as compressed as you can possibly make
> it. You can't compress it any more.
> 
> So there's *at least some* random data that you can't compress. Surely you
> have to accept that. You don't get to say "Oh, I don't mean *that* data, I
> mean only data that I can compress". Random data means its random, you
> don't get to pick and choose between data you can compress and data that
> you can't.
> 
> Now the tricky part is to realise that its not just short sequences of
> random data that can't be compressed. The same applies for LONG sequences
> to. If I give you a gigabyte of raw video, you can probably compress that a
> fair bit. That's what things like x264 encoders do. The x265 encoder is
> even better. But they're lossy, so you can't reverse them.
> 
> But if I give you a gigabyte of random data, you'll be lucky to find *any*
> patterns or redundancies that allow compression. You might be able to
> shrink the file by a few KB. And if you take that already compressed file,
> and try to compress it again, well, you've already hit the limit of
> compression. There no more redundancy left to remove.
> 
> It doesn't matter how clever you are, or what a "folding structure" is, or
> how many times you iterate over the data. It's a matter of absolute
> simplicity: the pigeonhole principle. You can't argue with the numbers.
> 
> If you start with a 100 digit decimal number, there are 10**100 different
> pigeons. If you can compress down to a 6 digit decimal number, there are
> 10**6 pigeon holes. You cannot put 10*100 pigeons into 10**6 pigeon holes
> without doubling up (which makes your compression lossly).
> 
> So either some numbers cannot be compressed, or some numbers are compressed
> to the same result, and you can't tell which was the original. That's your
> choice: a lossless encoder means some numbers can't be compressed, a lossy
> encoder means you can't reverse the process exactly.
> 
> 
> 
> 
> 
> -- 
> Steven
> “Cheer up,” they said, “things could be worse.” So I cheered up, and sure
> enough, things got worse.

It is not that the data is not compressible i just need more chunks or random data, it is the footprint of the algorithm that has a certain it is a structure afterall albeit richer in interpretation than the numerical field.

You exchange size for computational complexity, but that may be true for any compression algorithm.

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

#111398

On Wed, 13 Jul 2016 07:46 pm, jonas.thornvall@gmail.com wrote:

> It is not that the data is not compressible 

Yes it is.

Until you explain how you can *reversibly* pack 10**100 inputs into 10**6
outputs without loss of information, all your explanations about "folding"
and polynomials and structure is just cheap talk.



-- 
Steven
“Cheer up,” they said, “things could be worse.” So I cheered up, and sure
enough, things got worse.

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

#111406 — Re: [OT] Compression of random binary data

On 07/13/2016 03:46 AM, jonas.thornvall@gmail.com wrote:
> It is not that the data is not compressible i just need more chunks
> or random data, it is the footprint of the algorithm that has a
> certain it is a structure afterall albeit richer in interpretation
> than the numerical field.

Err, no, that does not apply to "random."  If the data is truly random
then it does not matter whether you have 5 bytes or 5 GB.  There is no
pattern to discern, and having more chunks of random data won't make it
possible to compress.

> You exchange size for computational complexity, but that may be true
> for any compression algorithm.

People are taking issue with your claim that you can compress random
data.  Clearly you cannot, by your own admission about requiring more
chunks of data (see above), and also by the irrefutable logical
principles Steven D'Aprano layed out.

Probably time to mute this thread. It's not related to Python.

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

#111409 — Re: [OT] Compression of random binary data

Michael Torrie <torriem@gmail.com>:
> If the data is truly random then it does not matter whether you have 5
> bytes or 5 GB. There is no pattern to discern, and having more chunks
> of random data won't make it possible to compress.

That's true if "truly random" means "evenly distributed". You might have
genuine random numbers with some other distribution, for example
Gaussian: <URL: https://www.random.org/gaussian-distributions/>. Such
sequences of random numbers may well be compressible.


Marko

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

#111417 — Re: [OT] Compression of random binary data

On 14 July 2016 at 05:35, Marko Rauhamaa <marko@pacujo.net> wrote:

> Michael Torrie <torriem@gmail.com>:
> > If the data is truly random then it does not matter whether you have 5
> > bytes or 5 GB. There is no pattern to discern, and having more chunks
> > of random data won't make it possible to compress.
>
> That's true if "truly random" means "evenly distributed". You might have
> genuine random numbers with some other distribution, for example
> Gaussian: <URL: https://www.random.org/gaussian-distributions/>. Such
> sequences of random numbers may well be compressible.
>

No one is saying that *all* random data is incompressible - in fact, some
random samples are *very* compressible. A single sample of random data
might look very much like the text of "A Midsummer Night's Dream"
(especially if your method of choosing the random sample was to pick a book
off a library shelf).

But unless otherwise qualified, a claim of being able to compress random
data is taken to mean any and all sets of random data.

Anyway, that's going to be my only contribution to this thread.

Tim Delaney

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

#111408 — Re: [OT] Compression of random binary data

On 2016-07-13, Michael Torrie <torriem@gmail.com> wrote:
> On 07/13/2016 03:46 AM, jonas.thornvall@gmail.com wrote:

>> It is not that the data is not compressible i just need more chunks
>> or random data, it is the footprint of the algorithm that has a
>> certain it is a structure afterall albeit richer in interpretation
>> than the numerical field.

Well, thanks for that.  Not only was it authentic frontier
gibberish...

> Err, no, that does not apply to "random."  If the data is truly
> random then it does not matter whether you have 5 bytes or 5 GB.
> There is no pattern to discern, and having more chunks of random
> data won't make it possible to compress.

You might as well be arguing with Ludwig Plutonium.

-- 
Grant Edwards               grant.b.edwards        Yow! I wonder if I should
                                  at               put myself in ESCROW!!
                              gmail.com            

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

#111385

Den onsdag 13 juli 2016 kl. 04:29:48 UTC+2 skrev Steven D'Aprano:
> On Wed, 13 Jul 2016 03:35 am, jonas.thornvall@gmail.com wrote:
> 
> > No it is only compressible down to a limit given by the algorithm.
> 
> Right! Then there is data that you can't compress.
> 
> Suppose you have some data:
> 
> data = "ABABABABABAB...ABAB"
> 
> And you compress it "down to a limit":
> 
> x = compress(compress(compress(data)))
> print(x)
> => prints "@nx7%k!b"
> 
> Now let's try again with something else:
> 
> data = "AABBBCCCCDDDDEEEE...ZZZZ"
> 
> And you compress it "down to a limit":
> 
> x = compress(compress(compress(compress(data))))
> print(x)
> => prints "wu*$cS#k-pv32zx[&+r"
> 
> 
> One more time:
> 
> data = "AABBAABBAABBAABBAABB"
> x = compress(data)
> print(x)
> => prints "g^x3@"
> 
> 
> We agree on this. Now you say, "Give me some random data, anything at all,
> and I'll compress it!", and I run a random number generator and out pops:
> 
> data = "@nx7%k!b"
> 
> or possibly:
> 
> data = "wu*$cS#k-pv32zx[&+r"
> 
> or:
> 
> data = "g^x3@"
> 
> 
> and I say "Compress that!"
> 
> But we've already agreed that this is as compressed as you can possibly make
> it. You can't compress it any more.
> 
> So there's *at least some* random data that you can't compress. Surely you
> have to accept that. You don't get to say "Oh, I don't mean *that* data, I
> mean only data that I can compress". Random data means its random, you
> don't get to pick and choose between data you can compress and data that
> you can't.
> 
> Now the tricky part is to realise that its not just short sequences of
> random data that can't be compressed. The same applies for LONG sequences
> to. If I give you a gigabyte of raw video, you can probably compress that a
> fair bit. That's what things like x264 encoders do. The x265 encoder is
> even better. But they're lossy, so you can't reverse them.
> 
> But if I give you a gigabyte of random data, you'll be lucky to find *any*
> patterns or redundancies that allow compression. You might be able to
> shrink the file by a few KB. And if you take that already compressed file,
> and try to compress it again, well, you've already hit the limit of
> compression. There no more redundancy left to remove.
> 
> It doesn't matter how clever you are, or what a "folding structure" is, or
> how many times you iterate over the data. It's a matter of absolute
> simplicity: the pigeonhole principle. You can't argue with the numbers.
> 
> If you start with a 100 digit decimal number, there are 10**100 different
> pigeons. If you can compress down to a 6 digit decimal number, there are
> 10**6 pigeon holes. You cannot put 10*100 pigeons into 10**6 pigeon holes
> without doubling up (which makes your compression lossly).
> 
> So either some numbers cannot be compressed, or some numbers are compressed
> to the same result, and you can't tell which was the original. That's your
> choice: a lossless encoder means some numbers can't be compressed, a lossy
> encoder means you can't reverse the process exactly.
> 
> 
> 
> 
> 
> -- 
> Steven
> “Cheer up,” they said, “things could be worse.” So I cheered up, and sure
> enough, things got worse.

Ok, try to see it this way ****very big**** numbers can be described as the sum or difference between a sequense of a few polynomials. Unfortunately we lack the computational skill/computing power to find them.

That is not the case using foldings/geometric series.

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

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | comp.lang.python

csiph-web