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

Groups > comp.lang.c > #89596

Re: [sOT] compression 1 GB downto 100 MB

From Ben Bacarisse <ben.usenet@bsb.me.uk>
Newsgroups comp.lang.c
Subject Re: [sOT] compression 1 GB downto 100 MB
Date 2016-06-19 03:20 +0100
Organization A noiseless patient Spider
Message-ID <87fus9syvh.fsf@bsb.me.uk> (permalink)
References (6 earlier) <be950b83-2eab-48aa-9616-ccc2174bf61c@googlegroups.com> <nk46d0$3oa$1@dont-email.me> <nk488q$94m$2@dont-email.me> <87r3burp3l.fsf@bsb.me.uk> <nk4s4f$pbh$1@dont-email.me>

Show all headers | View raw

Richard Heathfield <rjh@cpax.org.uk> writes:

> On 19/06/16 01:37, Ben Bacarisse wrote:
>> Richard Heathfield <rjh@cpax.org.uk> writes:
>>
>>> On 18/06/16 20:11, Bill Cunningham wrote:
>>> <snip>
>>>>
>>>>       Truely random can't be compressed?
>>>
>>> Right.
>>>
>>>> If there's a header indicating the
>>>> algorithm of randomness,  or encryption why not?
>>>
>>> If you can generate it via an algorithm, it isn't truly random.
>>
>> Technically you always can.  It's when the algorithm is significantly
>> shorter than the data that the sequence is far from truly random.
>
> I think that's only true if the algorithm can reliably predict the
> next bit with better than 50% accuracy.

The premise is that the sequence can be "generated by an algorithm".
There's no probability involved.

> Whether a sequence is random can depend on what you know about that
> sequence. I can easily predict the next nybble that follows
>
> 2FDE529A3274C649
>
> but can anyone else? To those who can, the sequence is not random. To
> those who can't, it would certainly appear to be random.

I've no been clear.

There is a very useful definition of "random" based on the theory of
computation.  Take your favourite model of computation -- Turing
machines for example -- and define the algorithmic complexity of a
sequence as the size of the smallest TM that generates that sequence.
For any sequence there are infinitely many algorithms -- TMs in this
case -- that generate it.  One of these is the smallest, but there is
also an obvious upper bound since the machine can simply have the
sequence coded into it's state transition function.

By this definition, random data has algorithmic complexity that is (or
approaches) this upper bound.  The bound is usually called the "size of
the input" but of course the model will include overheads so it many in
fact be some fixed multiple of the size (plus a fixed constant too).

This has only marginally less hand-waving than my original remark, but
it can all be formalised.

-- 
Ben.

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

Thread

[sOT] compression 1 GB downto 100 MB fir <profesor.fir@gmail.com> - 2016-06-16 07:25 -0700
  Re: [sOT] compression 1 GB downto 100 MB mark.bluemel@gmail.com - 2016-06-16 08:08 -0700
    Re: [sOT] compression 1 GB downto 100 MB Lynn McGuire <lmc@winsim.com> - 2016-06-17 12:04 -0500
      Re: [sOT] compression 1 GB downto 100 MB Malcolm McLean <malcolm.mclean5@btinternet.com> - 2016-06-17 10:16 -0700
        Re: [sOT] compression 1 GB downto 100 MB "Chris M. Thomasson" <nospam@nospam.invalid> - 2016-06-17 23:08 -0700
  Re: [sOT] compression 1 GB downto 100 MB Malcolm McLean <malcolm.mclean5@btinternet.com> - 2016-06-16 08:09 -0700
    Re: [sOT] compression 1 GB downto 100 MB fir <profesor.fir@gmail.com> - 2016-06-16 08:15 -0700
      Re: [sOT] compression 1 GB downto 100 MB fir <profesor.fir@gmail.com> - 2016-06-16 08:18 -0700
        Re: [sOT] compression 1 GB downto 100 MB mark.bluemel@gmail.com - 2016-06-17 01:28 -0700
          Re: [sOT] compression 1 GB downto 100 MB Malcolm McLean <malcolm.mclean5@btinternet.com> - 2016-06-17 02:03 -0700
            Re: [sOT] compression 1 GB downto 100 MB Richard Heathfield <rjh@cpax.org.uk> - 2016-06-17 10:34 +0100
              Re: [sOT] compression 1 GB downto 100 MB BartC <bc@freeuk.com> - 2016-06-17 10:44 +0100
                Re: [sOT] compression 1 GB downto 100 MB Richard Heathfield <rjh@cpax.org.uk> - 2016-06-17 11:03 +0100
                Re: [sOT] compression 1 GB downto 100 MB Malcolm McLean <malcolm.mclean5@btinternet.com> - 2016-06-17 03:51 -0700
                Re: [sOT] compression 1 GB downto 100 MB fir <profesor.fir@gmail.com> - 2016-06-18 02:16 -0700
                Re: [sOT] compression 1 GB downto 100 MB fir <profesor.fir@gmail.com> - 2016-06-18 02:29 -0700
                Re: [sOT] compression 1 GB downto 100 MB "Osmium" <r124c4u102@comcast.net> - 2016-06-17 08:19 -0500
                Re: [sOT] compression 1 GB downto 100 MB fir <profesor.fir@gmail.com> - 2016-06-18 03:17 -0700
              Re: [sOT] compression 1 GB downto 100 MB Gareth Owen <gwowen@gmail.com> - 2016-06-17 18:32 +0100
      Re: [sOT] compression 1 GB downto 100 MB Malcolm McLean <malcolm.mclean5@btinternet.com> - 2016-06-16 08:43 -0700
        Re: [sOT] compression 1 GB downto 100 MB fir <profesor.fir@gmail.com> - 2016-06-16 08:48 -0700
      Re: [sOT] compression 1 GB downto 100 MB "Osmium" <r124c4u102@comcast.net> - 2016-06-16 10:49 -0500
        Re: [sOT] compression 1 GB downto 100 MB fir <profesor.fir@gmail.com> - 2016-06-16 09:10 -0700
          Re: [sOT] compression 1 GB downto 100 MB Malcolm McLean <malcolm.mclean5@btinternet.com> - 2016-06-16 09:36 -0700
            Re: [sOT] compression 1 GB downto 100 MB Keith Thompson <kst-u@mib.org> - 2016-06-16 11:18 -0700
          Re: [sOT] compression 1 GB downto 100 MB "Osmium" <r124c4u102@comcast.net> - 2016-06-16 13:13 -0500
            Re: [sOT] compression 1 GB downto 100 MB Gareth Owen <gwowen@gmail.com> - 2016-06-16 20:18 +0100
              Re: [sOT] compression 1 GB downto 100 MB Richard Heathfield <rjh@cpax.org.uk> - 2016-06-16 22:07 +0100
                Re: [sOT] compression 1 GB downto 100 MB Gareth Owen <gwowen@gmail.com> - 2016-06-17 06:04 +0100
              Re: [sOT] compression 1 GB downto 100 MB Robert Wessel <robertwessel2@yahoo.com> - 2016-06-16 23:21 -0500
                Re: [sOT] compression 1 GB downto 100 MB "Osmium" <r124c4u102@comcast.net> - 2016-06-17 07:49 -0500
                Re: [sOT] compression 1 GB downto 100 MB Robert Wessel <robertwessel2@yahoo.com> - 2016-06-17 12:47 -0500
                Re: [sOT] compression 1 GB downto 100 MB "Osmium" <r124c4u102@comcast.net> - 2016-06-17 14:47 -0500
                Re: [sOT] compression 1 GB downto 100 MB Robert Wessel <robertwessel2@yahoo.com> - 2016-06-17 23:32 -0500
                Re: [sOT] compression 1 GB downto 100 MB fir <profesor.fir@gmail.com> - 2016-06-18 01:33 -0700
            Re: [sOT] compression 1 GB downto 100 MB fir <profesor.fir@gmail.com> - 2016-06-17 14:51 -0700
      Re: [sOT] compression 1 GB downto 100 MB BartC <bc@freeuk.com> - 2016-06-16 16:50 +0100
        Re: [sOT] compression 1 GB downto 100 MB BartC <bc@freeuk.com> - 2016-06-17 16:20 +0100
    Re: [sOT] compression 1 GB downto 100 MB fir <profesor.fir@gmail.com> - 2016-06-16 08:34 -0700
  Re: [sOT] compression 1 GB downto 100 MB Les Cargill <lcargill99@comcast.com> - 2016-06-16 12:55 -0500
  Re: [sOT] compression 1 GB downto 100 MB "Chris M. Thomasson" <nospam@nospam.invalid> - 2016-06-16 11:53 -0700
    Re: [sOT] compression 1 GB downto 100 MB "Chris M. Thomasson" <nospam@nospam.invalid> - 2016-06-16 12:14 -0700
    Re: [sOT] compression 1 GB downto 100 MB "Chris M. Thomasson" <nospam@nospam.invalid> - 2016-06-17 12:33 -0700
      Re: [sOT] compression 1 GB downto 100 MB "Chris M. Thomasson" <nospam@nospam.invalid> - 2016-06-17 12:46 -0700
    Re: [sOT] compression 1 GB downto 100 MB fir <profesor.fir@gmail.com> - 2016-06-17 15:04 -0700
      Re: [sOT] compression 1 GB downto 100 MB "Chris M. Thomasson" <nospam@nospam.invalid> - 2016-06-17 22:55 -0700
        Re: [sOT] compression 1 GB downto 100 MB fir <profesor.fir@gmail.com> - 2016-06-18 01:38 -0700
          Re: [sOT] compression 1 GB downto 100 MB BartC <bc@freeuk.com> - 2016-06-18 10:41 +0100
            Re: [sOT] compression 1 GB downto 100 MB fir <profesor.fir@gmail.com> - 2016-06-18 02:55 -0700
            Re: [sOT] compression 1 GB downto 100 MB Malcolm McLean <malcolm.mclean5@btinternet.com> - 2016-06-18 05:08 -0700
              Re: [sOT] compression 1 GB downto 100 MB "Bill Cunningham" <nospam@nspam.invalid> - 2016-06-18 15:11 -0400
                Re: [sOT] compression 1 GB downto 100 MB "Bill Cunningham" <nospam@nspam.invalid> - 2016-06-18 15:13 -0400
                Re: [sOT] compression 1 GB downto 100 MB luser droog <luser.droog@gmail.com> - 2016-06-18 12:43 -0700
                Re: [sOT] compression 1 GB downto 100 MB Richard Heathfield <rjh@cpax.org.uk> - 2016-06-18 20:43 +0100
                Re: [sOT] compression 1 GB downto 100 MB "Chris M. Thomasson" <nospam@nospam.invalid> - 2016-06-18 12:53 -0700
                Re: [sOT] compression 1 GB downto 100 MB "Chris M. Thomasson" <nospam@nospam.invalid> - 2016-06-20 20:32 -0700
                Re: [sOT] compression 1 GB downto 100 MB Keith Thompson <kst-u@mib.org> - 2016-06-18 13:22 -0700
                Re: [sOT] compression 1 GB downto 100 MB Jerry Stuckle <jstucklex@attglobal.net> - 2016-06-18 16:35 -0400
                Re: [sOT] compression 1 GB downto 100 MB Jerry Stuckle <jstucklex@attglobal.net> - 2016-06-18 21:37 -0400
                Re: [sOT] compression 1 GB downto 100 MB "James R. Kuyper" <jameskuyper@verizon.net> - 2016-06-18 16:59 -0400
                Re: [sOT] compression 1 GB downto 100 MB crisdunbar@gmail.com - 2016-06-20 09:55 -0700
                Re: [sOT] compression 1 GB downto 100 MB Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-06-20 21:22 +0100
                Re: [sOT] compression 1 GB downto 100 MB cris <crisdunbar@gmail.com> - 2016-06-20 17:13 -0700
                Re: [sOT] compression 1 GB downto 100 MB Tim Rentsch <txr@alumni.caltech.edu> - 2016-06-21 10:42 -0700
                Re: [sOT] compression 1 GB downto 100 MB Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-06-21 20:09 +0100
                Re: [sOT] compression 1 GB downto 100 MB crisdunbar@gmail.com - 2016-06-21 13:39 -0700
                Re: [sOT] compression 1 GB downto 100 MB Keith Thompson <kst-u@mib.org> - 2016-06-22 08:34 -0700
                Re: [sOT] compression 1 GB downto 100 MB Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-06-22 19:48 +0100
                Re: [sOT] compression 1 GB downto 100 MB Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-06-19 01:37 +0100
                Re: [sOT] compression 1 GB downto 100 MB Richard Heathfield <rjh@cpax.org.uk> - 2016-06-19 02:22 +0100
                Re: [sOT] compression 1 GB downto 100 MB Jerry Stuckle <jstucklex@attglobal.net> - 2016-06-18 21:30 -0400
                Re: [sOT] compression 1 GB downto 100 MB Richard Heathfield <rjh@cpax.org.uk> - 2016-06-19 02:41 +0100
                Re: [sOT] compression 1 GB downto 100 MB Jerry Stuckle <jstucklex@attglobal.net> - 2016-06-18 21:55 -0400
                Re: [sOT] compression 1 GB downto 100 MB Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-06-19 03:20 +0100
                Re: [sOT] compression 1 GB downto 100 MB fir <profesor.fir@gmail.com> - 2016-06-19 02:53 -0700
                Re: [sOT] compression 1 GB downto 100 MB Malcolm McLean <malcolm.mclean5@btinternet.com> - 2016-06-18 16:05 -0700
                Re: [sOT] compression 1 GB downto 100 MB "J. Clarke" <j.clarke.873638@gmail.com> - 2016-06-19 06:59 -0400
                Re: [sOT] compression 1 GB downto 100 MB fir <profesor.fir@gmail.com> - 2016-06-19 05:55 -0700
                Re: [sOT] compression 1 GB downto 100 MB Malcolm McLean <malcolm.mclean5@btinternet.com> - 2016-06-19 06:13 -0700
                Re: [sOT] compression 1 GB downto 100 MB "J. Clarke" <j.clarke.873638@gmail.com> - 2016-06-26 12:26 -0400
                Re: [sOT] compression 1 GB downto 100 MB Malcolm McLean <malcolm.mclean5@btinternet.com> - 2016-06-26 09:53 -0700
              Re: [sOT] compression 1 GB downto 100 MB Richard Heathfield <rjh@cpax.org.uk> - 2016-06-18 20:41 +0100
              Re: [sOT] compression 1 GB downto 100 MB "J. Clarke" <j.clarke.873638@gmail.com> - 2016-06-19 06:45 -0400
            Re: [sOT] compression 1 GB downto 100 MB Robert Wessel <robertwessel2@yahoo.com> - 2016-06-18 14:42 -0500
            Re: [sOT] compression 1 GB downto 100 MB gordonb.vnsk1@burditt.org (Gordon Burditt) - 2016-06-20 01:13 -0500
              Re: [sOT] compression 1 GB downto 100 MB Keith Thompson <kst-u@mib.org> - 2016-06-20 12:16 -0700
                Re: [sOT] compression 1 GB downto 100 MB David Brown <david.brown@hesbynett.no> - 2016-06-20 21:27 +0200
                Re: [sOT] compression 1 GB downto 100 MB Xaltonon <xaltonon@gmail.com> - 2016-06-20 21:25 -0700

csiph-web