Path: csiph.com!fu-berlin.de!uni-berlin.de!not-for-mail From: Terry Reedy Newsgroups: comp.lang.python Subject: Re: Compression of random binary data Date: Mon, 11 Jul 2016 15:31:46 -0400 Lines: 45 Message-ID: References: Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 7bit X-Trace: news.uni-berlin.de E3H+ydGhkB+9itY1A1TViQamjkJsgjRc4odXQmxXq+ug== Return-Path: X-Original-To: python-list@python.org Delivered-To: python-list@mail.python.org X-Spam-Status: OK 0.001 X-Spam-Evidence: '*H*': 1.00; '*S*': 0.00; 'binary': 0.05; 'bits': 0.07; 'shannon': 0.07; 'compression': 0.09; 'finite': 0.09; 'received:80.91': 0.09; 'received:80.91.229': 0.09; 'received:gmane.org': 0.09; 'received:list': 0.09; 'second.': 0.09; 'jan': 0.11; 'size,': 0.13; 'suggest': 0.15; 'encoding': 0.15; 'explicitly': 0.15; '2016': 0.16; 'compress': 0.16; 'joonas': 0.16; 'liik': 0.16; 'received:80.91.229.3': 0.16; 'received:io': 0.16; 'received:plane.gmane.org': 0.16; 'received:psf.io': 0.16; 'redundancy': 0.16; 'reedy': 0.16; 'replaced.': 0.16; 'subject:random': 0.16; 'unequal': 0.16; 'violated': 0.16; 'wrote:': 0.16; 'meant': 0.22; 'assuming': 0.22; 'bit': 0.23; 'replacing': 0.23; 'header:In-Reply-To:1': 0.24; 'header:User-Agent:1': 0.26; 'header:X-Complaints-To:1': 0.26; 'sense': 0.26; 'mathematical': 0.27; "skip:' 10": 0.28; 'coded': 0.29; 'relies': 0.29; 'random': 0.29; 'code': 0.30; 'related': 0.32; 'common': 0.33; 'done,': 0.33; 'similar': 0.33; 'equal': 0.34; 'could': 0.35; 'but': 0.36; 'should': 0.36; 'there': 0.36; 'web,': 0.36; 'to:addr:python-list': 0.36; 'pm,': 0.36; 'subject:: ': 0.37; 'two': 0.37; 'being': 0.37; 'say': 0.37; 'received:org': 0.37; 'mean': 0.38; 'whatever': 0.39; 'does': 0.39; 'to:addr:python.org': 0.40; 'some': 0.40; 'per': 0.62; 'received:96': 0.63; 'more': 0.63; 'information': 0.63; 'results': 0.66; 'articles': 0.67; 'physical': 0.72; 'discovered': 0.83; '*if': 0.84; 'streams': 0.84; 'unclear': 0.84; 'received:fios.verizon.net': 0.91 X-Injected-Via-Gmane: http://gmane.org/ X-Gmane-NNTP-Posting-Host: pool-96-227-207-81.phlapa.fios.verizon.net User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:45.0) Gecko/20100101 Thunderbird/45.2.0 In-Reply-To: X-BeenThere: python-list@python.org X-Mailman-Version: 2.1.22 Precedence: list List-Id: General discussion list for the Python programming language List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Mailman-Original-Message-ID: X-Mailman-Original-References: Xref: csiph.com comp.lang.python:111288 On 7/11/2016 2:09 PM, Joonas Liik wrote: > On 11 July 2016 at 20:52, 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