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

Groups > comp.lang.python > #111359

Re: Compression of random binary data

Path csiph.com!fu-berlin.de!uni-berlin.de!not-for-mail
From Ian Kelly <ian.g.kelly@gmail.com>
Newsgroups comp.lang.python
Subject Re: Compression of random binary data
Date Tue, 12 Jul 2016 16:23:23 -0600
Lines 20
Message-ID <mailman.23.1468362251.21009.python-list@python.org> (permalink)
References <d6053eeb-bb1b-49d7-95e2-9f15028746e5@googlegroups.com> <5783e7a6$0$1608$c3e8da3$5496439d@news.astraweb.com> <2a412b20-925c-4778-a71d-fad6266feab8@googlegroups.com> <578508ad$0$1614$c3e8da3$5496439d@news.astraweb.com> <bf5286ef-b091-4f3f-ace3-13a7002dbec3@googlegroups.com> <CALwzidnFO82VOUKb3hWi-XdL9sCXceEKiaS5LgOD=RyKud9iCw@mail.gmail.com>
Mime-Version 1.0
Content-Type text/plain; charset=UTF-8
X-Trace news.uni-berlin.de BJtllCsMYgFHHdszu5lKdwTOKiiLvo0CCwPUNWZlMIcQ==
Return-Path <ian.g.kelly@gmail.com>
X-Original-To python-list@python.org
Delivered-To python-list@mail.python.org
X-Spam-Status OK 0.035
X-Spam-Evidence '*H*': 0.93; '*S*': 0.00; 'incorrect': 0.09; 'input,': 0.09; 'output': 0.13; 'size,': 0.13; '2016': 0.16; 'algorithm.': 0.16; 'compress': 0.16; 'input.': 0.16; 'inputs': 0.16; 'outputs': 0.16; 'received:io': 0.16; 'received:psf.io': 0.16; 'subject:random': 0.16; 'unchanged,': 0.16; 'wrote:': 0.16; 'input': 0.18; 'algorithm': 0.20; 'produces': 0.22; 'am,': 0.23; 'header:In-Reply-To:1': 0.24; 'message-id:@mail.gmail.com': 0.27; 'random': 0.29; "can't": 0.32; 'tue,': 0.34; 'received:google.com': 0.35; 'feed': 0.35; 'there': 0.36; 'possible': 0.36; 'to:addr:python-list': 0.36; 'subject:: ': 0.37; 'two': 0.37; '12,': 0.37; 'data': 0.39; 'does': 0.39; 'to:addr:python.org': 0.40; 'some': 0.40; 'your': 0.60; 'determine': 0.61; 'different': 0.63; 'limit': 0.65; 'repeat': 0.67; 'therefore': 0.67; 'jul': 0.72; 'original.': 0.84; 'probable': 0.84; 'random,': 0.84; 'to:name:python': 0.84
DKIM-Signature v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:from:date:message-id:subject:to; bh=IhJcEcBXrX5nEWKigftGNJimMOtayBpkC1L7jYzZG4s=; b=uAJVmjyXmbVjbe4nh8F2sYm58Pm6v9P4Pq0czzTwM9932PejOA21bOteg6K07PXy9K Wrzmn+zTyQzHl6Xxf0+cA/vDJoaN30Js19ik/Qtu1v7fqeQmQGmXDpDPaMhjh8BVzGaT BVuDrm8LK+qa/2O28GUR5ecRmolcZloGFQznV1cwBv5hQQARbTvZoDcgFTgKIwCnL/hP dV4eYVV8140fNS1uUTb0wfuIdoKIz4uzZdBM+T0Q1608vO31TtJdvhQMqSx5i/RlgYDl Ctp7cZUYHDOLX4QAW/nPoRcnXgQyfc25884emXpnAjAWV52/WxL5fisE9IddXzOP4GN2 cDlQ==
X-Google-DKIM-Signature v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to; bh=IhJcEcBXrX5nEWKigftGNJimMOtayBpkC1L7jYzZG4s=; b=eYIWvUIDCcZ07WMHre5nLUwONG7OGmvuAB8IyB6oMms5dZ/XJFEKIeimJRVP+ERzT4 R2yHLWzFmP/HOLQJeyGqKvmpt0A3boyz03AbW8uGyFSprJt04xS0bXHmyDcWa5x/vbUz /O+sUgcEyRRQAESxOKYT66NBTA89EpKLqJ9Kjciisf7pzZ17Kgzklhvh5//BqLqaPSq6 Vw7fwINoVfaCqV/yGErLQQFGP2RlTZIpjcm9qrowBOkea9tTWyin44Ei1EwysH0YAvta EZE9vrBRLjNCpsIiOzdAGWxKioxvMihnR/p8qowxv/MwEI1VVztuLBJWe5oJJeh7dUwc AjOQ==
X-Gm-Message-State ALyK8tLekPt1IrATqKReEht+OpgqLQhKFC5E8lcDclzlmHdx3o2K6pVAqVUtK1EMAVjv7fIp02SQr4YBswAqbg==
X-Received by 10.157.37.119 with SMTP id j52mr2982987otd.115.1468362243395; Tue, 12 Jul 2016 15:24:03 -0700 (PDT)
In-Reply-To <bf5286ef-b091-4f3f-ace3-13a7002dbec3@googlegroups.com>
X-BeenThere python-list@python.org
X-Mailman-Version 2.1.22
Precedence list
List-Id General discussion list for the Python programming language <python-list.python.org>
List-Unsubscribe <https://mail.python.org/mailman/options/python-list>, <mailto:python-list-request@python.org?subject=unsubscribe>
List-Archive <http://mail.python.org/pipermail/python-list/>
List-Post <mailto:python-list@python.org>
List-Help <mailto:python-list-request@python.org?subject=help>
List-Subscribe <https://mail.python.org/mailman/listinfo/python-list>, <mailto:python-list-request@python.org?subject=subscribe>
X-Mailman-Original-Message-ID <CALwzidnFO82VOUKb3hWi-XdL9sCXceEKiaS5LgOD=RyKud9iCw@mail.gmail.com>
X-Mailman-Original-References <d6053eeb-bb1b-49d7-95e2-9f15028746e5@googlegroups.com> <5783e7a6$0$1608$c3e8da3$5496439d@news.astraweb.com> <2a412b20-925c-4778-a71d-fad6266feab8@googlegroups.com> <578508ad$0$1614$c3e8da3$5496439d@news.astraweb.com> <bf5286ef-b091-4f3f-ace3-13a7002dbec3@googlegroups.com>
Xref csiph.com comp.lang.python:111359

Show key headers only | View raw

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.

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

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