Re: Compression of random binary data

From	Terry Reedy <tjreedy@udel.edu>
Newsgroups	comp.lang.python
Subject	Re: Compression of random binary data
Date	2016-07-11 15:31 -0400
Message-ID	<mailman.189.1468265516.2295.python-list@python.org> (permalink)
References	<d6053eeb-bb1b-49d7-95e2-9f15028746e5@googlegroups.com> <CAB1GNpQ3++s1mfFrzHObWMAEfxgA-SuH4Sx7pfRP72obWCKNWQ@mail.gmail.com> <nm0s74$j2j$1@ger.gmane.org>

Show all headers | View raw

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

Thread

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

csiph-web