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 2 of 2 — ← Prev page 1 [2]

#111386

Den onsdag 13 juli 2016 kl. 12:05:03 UTC+2 skrev jonas.t...@gmail.com:
> 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.

The sum or difference of a few small polynomials would still of course be a polynomial. But as i say it is a case of enrich the interpretation of the symbolic set that you look at you replace digits bits/integers with arithmetic describing them.

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

#111389

On Wed, 13 Jul 2016 08:04 pm, jonas.thornvall@gmail.com wrote:

> 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.

*Any* number, big or small, can be given as the sum or difference of a few
polynomials:

15 = (25*x**2 - 2*x + 40) - (25*x**2 - 2*x + 25)

But... why am I wasting my time with the x**2 and x terms? They must
*always* cancel, because I'm trying to simplify to a constant. So I should
just write:

15 = 40 - 25

but that's a waste of time to. I should just write:

15 

and be done. The same applies for any number, no matter how big.


> Unfortunately we lack the computational skill/computing power to find
> them.
> 
> That is not the case using foldings/geometric series.

You still haven't explained how you are supposed to compress 10**100
possible inputs to just 10**6 outputs without any loss of information.






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

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

#111285

On Mon, 11 Jul 2016 10:52:08 -0700, jonas.thornvall wrote:

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

You can't create an invertable mapping between a set with 2^N elements
(e.g. the set of all N-bit binary sequences) and any set with fewer than
2^N elements (e.g. the set of all M-bit binary sequences for M<N).

Lossless compression requires an invertable mapping.

For any lossless compression algorithm, there will always be inputs where
the output is larger than the input, even if only by a single bit.

Practical lossless compression schemes operate by mapping likely inputs to
short outputs and unlikely inputs to longer outputs, resulting in outputs
which are /on average/ shorter than the inputs.

Lossy compression can achieve as much compression as you want, providing
that you're willing to tolerate the resulting loss of information.

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

#111286

On 2016-07-11 19:30, MRAB wrote:
> 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
>
It turns out there's a newsgroup for compression, and they're used to 
getting claims about compressing random data. In fact, so much so that 
it's in their FAQ:

comp.compression Frequently Asked Questions (part 1/3)
Section - [9] Compression of random data (WEB, Gilbert and others)
http://www.faqs.org/faqs/compression-faq/part1/section-8.html

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

#111288

On 7/11/2016 2:09 PM, Joonas Liik wrote:
> 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?

Off-topic, but...  It is unclear whether you mean 'random' in the 
technical sense of 'unpredictable' or the common sense that adds 'of 
equal probability'.

Bell engineers discovered that physical communication channels have a 
finite information transmission capacity that could be formalized as 
bits per second.  You should be able to find good articles on the web, 
and I suggest you read some.

If every message could be compressed, than every message could be 
compressed to 0 or 1, which is absurd.

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

Shannon meant random in the technical sense and explicitly considered 
unequal probabilities.  Random bit streams with unequal probabilities 
*can* be compressed by recoding.

> Compression relies on some items in the dataset being more frequent
> than others,

Perhaps better to say that compression relies on removing redundancy, 
*if there is any*.  The two ideas are related.

> if you have some dataset that is completely random it
> would be hard to compress as most items have very similar number of
> occurrances.

Assuming equal bit probabilities.  Uncorrelated bits of unequal 
probability results in blocks of whatever size having unequal 
probabilites and redundancy that can be removed by replacing blocks with 
coded blocks.  Huffman encoding does this by replacing blocks of equal 
size with code blocks of unequal size, with the size related to the 
probability of the block replaced.

-- 
Terry Jan Reedy

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

#111306

On Mon, Jul 11, 2016, 10:56 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?
>

If you get lucky, you might be able to achieve very good compression.

> http://dilbert.com/strip/2001-10-25

Or are you asking about an algorithm that reliably compresses random data
by a fairly constant percent?

>

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

#111309

On Tuesday, July 12, 2016 at 5:52:27 AM UTC+12, jonas.t...@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? 

Try compressing already-compressed data.

Does that answer your question?

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

#111339

Den tisdag 12 juli 2016 kl. 05:01:20 UTC+2 skrev Lawrence D’Oliveiro:
> On Tuesday, July 12, 2016 at 5:52:27 AM UTC+12, jonas.t...@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? 
> 
> Try compressing already-compressed data.
> 
> Does that answer your question?

Yes that is my question, and also a claim i can do it.

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

#111342

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

> Den tisdag 12 juli 2016 kl. 05:01:20 UTC+2 skrev Lawrence D’Oliveiro:
>> On Tuesday, July 12, 2016 at 5:52:27 AM UTC+12, jonas.t...@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?
>> 
>> Try compressing already-compressed data.
>> 
>> Does that answer your question?
> 
> Yes that is my question, and also a claim i can do it.

Can you also make a perpetual motion machine, square the circle, and find an
exact rational fraction equal to pi?


What gets me is the people who *say* that they can compress already
compressed data. We know they can't, because if they could, they could
compress it again and again and again and again until there was only a
single bit, AND STILL REVERSE IT, using no external storage. Your lookup
tables are part of the compressed data. If the "compressed file" plus the
lookup table is bigger than the original file, then you haven't really
compressed anything. You've just moved some of it from the file into a
lookup table.

So why do people claim that they can compress already compressed data? Who
are they fooling? Themselves?



-- 
Steve

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

#111346

Den tisdag 12 juli 2016 kl. 17:19:54 UTC+2 skrev Steven D'Aprano:
> On Wed, 13 Jul 2016 12:29 am, jonas.thornvall@gmail.com wrote:
> 
> > Den tisdag 12 juli 2016 kl. 05:01:20 UTC+2 skrev Lawrence D’Oliveiro:
> >> On Tuesday, July 12, 2016 at 5:52:27 AM UTC+12, jonas.t...@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?
> >> 
> >> Try compressing already-compressed data.
> >> 
> >> Does that answer your question?
> > 
> > Yes that is my question, and also a claim i can do it.
> 
> Can you also make a perpetual motion machine, square the circle, and find an
> exact rational fraction equal to pi?
> 
> 
> What gets me is the people who *say* that they can compress already
> compressed data. We know they can't, because if they could, they could
> compress it again and again and again and again until there was only a
> single bit, AND STILL REVERSE IT, using no external storage. Your lookup
> tables are part of the compressed data. If the "compressed file" plus the
> lookup table is bigger than the original file, then you haven't really
> compressed anything. You've just moved some of it from the file into a
> lookup table.
> 
> So why do people claim that they can compress already compressed data? Who
> are they fooling? Themselves?
> 
> 
> 
> -- 
> Steve

Well the algorithm start with looking up a suitable folding structure "close enough to the number", then it works down the folding structure finding the fold where the difference or sum between the folds closest to zero.

You do the same prinicple with the remainder until zero is achieved.

So our first fold can either be bigger or smaller, and it seek a configuration for the fold that close in max on the actual random number. The second fold could be a fold that depending upon our first fold was bigger or smaller than number either will add or subtract lower layers of the fold. 

There will come out a difference that need to be folded, the process is repeated until there is nothing to fold.

It is basicly a search algorithm looking for suitable folding structures.

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

#111347

On 07/12/2016 11:46 AM, jonas.thornvall@gmail.com wrote:
> Well the algorithm start with looking up a suitable folding structure
> "close enough to the number", then it works down the folding
> structure finding the fold where the difference or sum between the
> folds closest to zero.
> 
> You do the same prinicple with the remainder until zero is achieved.
> 
> So our first fold can either be bigger or smaller, and it seek a
> configuration for the fold that close in max on the actual random
> number. The second fold could be a fold that depending upon our first
> fold was bigger or smaller than number either will add or subtract
> lower layers of the fold.
> 
> There will come out a difference that need to be folded, the process
> is repeated until there is nothing to fold.
> 
> It is basicly a search algorithm looking for suitable folding
> structures.

Better patent it quickly then.  And you will win a noble prize for math
if you could do what you say you could.

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

#111351

Den tisdag 12 juli 2016 kl. 20:20:52 UTC+2 skrev Michael Torrie:
> On 07/12/2016 11:46 AM, jonas.thornvall@gmail.com wrote:
> > Well the algorithm start with looking up a suitable folding structure
> > "close enough to the number", then it works down the folding
> > structure finding the fold where the difference or sum between the
> > folds closest to zero.
> > 
> > You do the same prinicple with the remainder until zero is achieved.
> > 
> > So our first fold can either be bigger or smaller, and it seek a
> > configuration for the fold that close in max on the actual random
> > number. The second fold could be a fold that depending upon our first
> > fold was bigger or smaller than number either will add or subtract
> > lower layers of the fold.
> > 
> > There will come out a difference that need to be folded, the process
> > is repeated until there is nothing to fold.
> > 
> > It is basicly a search algorithm looking for suitable folding
> > structures.
> 
> Better patent it quickly then.  And you will win a noble prize for math
> if you could do what you say you could.

I doubt it i never got anyone before for my ideas.

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

#111352

Den tisdag 12 juli 2016 kl. 20:20:52 UTC+2 skrev Michael Torrie:
> On 07/12/2016 11:46 AM, jonas.thornvall@gmail.com wrote:
> > Well the algorithm start with looking up a suitable folding structure
> > "close enough to the number", then it works down the folding
> > structure finding the fold where the difference or sum between the
> > folds closest to zero.
> > 
> > You do the same prinicple with the remainder until zero is achieved.
> > 
> > So our first fold can either be bigger or smaller, and it seek a
> > configuration for the fold that close in max on the actual random
> > number. The second fold could be a fold that depending upon our first
> > fold was bigger or smaller than number either will add or subtract
> > lower layers of the fold.
> > 
> > There will come out a difference that need to be folded, the process
> > is repeated until there is nothing to fold.
> > 
> > It is basicly a search algorithm looking for suitable folding
> > structures.
> 
> Better patent it quickly then.  And you will win a noble prize for math
> if you could do what you say you could.

I must stress when i say number here i really mean +100000 decimal digit. So i basicly search in on big numbers that i compress. So i divide the dataset into suitable sizes for compression.

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

#111353

Den tisdag 12 juli 2016 kl. 21:40:36 UTC+2 skrev jonas.t...@gmail.com:
> Den tisdag 12 juli 2016 kl. 20:20:52 UTC+2 skrev Michael Torrie:
> > On 07/12/2016 11:46 AM, jonas.thornvall@gmail.com wrote:
> > > Well the algorithm start with looking up a suitable folding structure
> > > "close enough to the number", then it works down the folding
> > > structure finding the fold where the difference or sum between the
> > > folds closest to zero.
> > > 
> > > You do the same prinicple with the remainder until zero is achieved.
> > > 
> > > So our first fold can either be bigger or smaller, and it seek a
> > > configuration for the fold that close in max on the actual random
> > > number. The second fold could be a fold that depending upon our first
> > > fold was bigger or smaller than number either will add or subtract
> > > lower layers of the fold.
> > > 
> > > There will come out a difference that need to be folded, the process
> > > is repeated until there is nothing to fold.
> > > 
> > > It is basicly a search algorithm looking for suitable folding
> > > structures.
> > 
> > Better patent it quickly then.  And you will win a noble prize for math
> > if you could do what you say you could.
> 
> I must stress when i say number here i really mean +100000 decimal digit. So i basicly search in on big numbers that i compress. So i divide the dataset into suitable sizes for compression.

And the dataset chunks that comes out from the process can also be treated like a new datafile, so the compression is iterative down to a limit. 

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

#111344

On 12/07/2016 15:29, jonas.thornvall@gmail.com wrote:
> Den tisdag 12 juli 2016 kl. 05:01:20 UTC+2 skrev Lawrence D’Oliveiro:
>> On Tuesday, July 12, 2016 at 5:52:27 AM UTC+12, jonas.t...@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?
>>
>> Try compressing already-compressed data.
>>
>> Does that answer your question?
>
> Yes that is my question, and also a claim i can do it.
>

*plonk*

[toc] | [prev] | [standalone]

Page 2 of 2 — ← Prev page 1 [2]

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

csiph-web