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

Groups > comp.lang.c > #89274 > unrolled thread

[sOT] compression 1 GB downto 100 MB

Back to article view | Back to comp.lang.c

Contents

  [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

Page 4 of 5 — ← Prev page 1 2 3 [4] 5  Next page →

#89661

On Saturday, June 18, 2016 at 1:59:17 PM UTC-7, James R. Kuyper wrote:
> On 06/18/2016 04:22 PM, Keith Thompson wrote:
> > Richard Heathfield <> writes:
> >> On 18/06/16 20:11, Bill Cunningham wrote:
> >> <snip>
> >>>
> >>>      Truely random can't be compressed?
> >>
> >> Right.
> 
> That's true, but only on average, and it's not clear to me whether Bill
> understands that fact. He probably doesn't, and probably won't even
> after I explain it, but I'll give it a try.
> 
> A compression algorithm maps a set of input files to a set of output
> files, and if the algorithm is lossless, any randomly selected member of
> the first set will most likely be mapped to an output file that has, at
> best, the same exact size. The usefulness of a compression algorithm
> depends upon the fact that the files that are chosen for compression are
> not selected at random from among all possible files - a useful
> compression algorithm compresses the files most likely to be selected to
> small sizes, at the expense of achieving no compression at all on less
> likely input files, and negative amounts of compression on the least
> likely input files.
> 
> Any source of truly random data must have a finite, (if very small)
> chance of generating a file that happens to fall into the set that a
> given algorithm compresses very efficiently. However, that happens so
> infrequently that, on average, a truly random file will not be
> compressed at all.

I vaguely recall a quote along the lines of:

"A compression algorithm is an 'expansion' algorithm that
happens to fail spectacularly for a very small set of input
files"

=)

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

#89669

crisdunbar@gmail.com writes:
<snip>
> I vaguely recall a quote along the lines of:
>
> "A compression algorithm is an 'expansion' algorithm that
> happens to fail spectacularly for a very small set of input
> files"

Very nice.  Any idea where it's from?  I feel I will have to quote it at
some point in the future and I'd like to give credit.  (A quick search
thew up nothing to go on.)

-- 
Ben.

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

#89680

On Monday, June 20, 2016 at 1:22:46 PM UTC-7, Ben Bacarisse wrote:
> cris writes:
> <snip>
> > I vaguely recall a quote along the lines of:
> >
> > "A compression algorithm is an 'expansion' algorithm that
> > happens to fail spectacularly for a very small set of input
> > files"
> 
> Very nice.  Any idea where it's from?  I feel I will have to quote it at
> some point in the future and I'd like to give credit.  (A quick search
> thew up nothing to go on.)

Sorry, can't recall at all. I looked before I first posted as well, to
no avail. I'm pretty sure the original was more eloquent  =)

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

#89712

Ben Bacarisse <ben.usenet@bsb.me.uk> writes:

> crisdunbar@gmail.com writes:
> <snip>
>> I vaguely recall a quote along the lines of:
>>
>> "A compression algorithm is an 'expansion' algorithm that
>> happens to fail spectacularly for a very small set of input
>> files"
>
> Very nice.  Any idea where its from?  I feel I will have to quote it at
> some point in the future and I'd like to give credit.  (A quick search
> thew up nothing to go on.)

Perhaps here:

    http://stackoverflow.com/questions/2643932/md5-purpose-or-uses

    "A 'compression algorithm' is actually an 'expansion
    algorithm' with some interesting failure cases :)"

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

#89721

Tim Rentsch <txr@alumni.caltech.edu> writes:

> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
>
>> crisdunbar@gmail.com writes:
>> <snip>
>>> I vaguely recall a quote along the lines of:
>>>
>>> "A compression algorithm is an 'expansion' algorithm that
>>> happens to fail spectacularly for a very small set of input
>>> files"
>>
>> Very nice.  Any idea where its from?  I feel I will have to quote it at
>> some point in the future and I'd like to give credit.  (A quick search
>> thew up nothing to go on.)
>
> Perhaps here:
>
>     http://stackoverflow.com/questions/2643932/md5-purpose-or-uses
>
>     "A 'compression algorithm' is actually an 'expansion
>     algorithm' with some interesting failure cases :)"

Thanks.  No sign that they are quoting but I don't suppose that is
definitive.

-- 
Ben.

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

#89736

On Tuesday, June 21, 2016 at 12:09:34 PM UTC-7, Ben Bacarisse wrote:
> Tim Rentsch <> writes:
> 
> > Ben Bacarisse <> writes:
> >
> >> Cris writes:
> >> <snip>
> >>> I vaguely recall a quote along the lines of:
> >>>
> >>> "A compression algorithm is an 'expansion' algorithm that
> >>> happens to fail spectacularly for a very small set of input
> >>> files"
> >>
> >> Very nice.  Any idea where its from?  I feel I will have to quote it at
> >> some point in the future and I'd like to give credit.  (A quick search
> >> thew up nothing to go on.)
> >
> > Perhaps here:
> >
> >     http://stackoverflow.com/questions/2643932/md5-purpose-or-uses
> >
> >     "A 'compression algorithm' is actually an 'expansion
> >     algorithm' with some interesting failure cases :)"
> 
> Thanks.  No sign that they are quoting but I don't suppose that is
> definitive.

I don't remember that SO post as my source, but it could be the original.

Finally, probably my favourite xkcd is somewhat apropos:

https://xkcd.com/1381/

-- 
Cris

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

#89754

Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
> Tim Rentsch <txr@alumni.caltech.edu> writes:
>> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
>>> crisdunbar@gmail.com writes:
>>> <snip>
>>>> I vaguely recall a quote along the lines of:
>>>>
>>>> "A compression algorithm is an 'expansion' algorithm that
>>>> happens to fail spectacularly for a very small set of input
>>>> files"
>>>
>>> Very nice.  Any idea where its from?  I feel I will have to quote it at
>>> some point in the future and I'd like to give credit.  (A quick search
>>> thew up nothing to go on.)
>>
>> Perhaps here:
>>
>>     http://stackoverflow.com/questions/2643932/md5-purpose-or-uses
>>
>>     "A 'compression algorithm' is actually an 'expansion
>>     algorithm' with some interesting failure cases :)"
>
> Thanks.  No sign that they are quoting but I don't suppose that is
> definitive.

I asked the commenter (user "caf") whether that was an original quote.
His reply:

    No, I was paraphrasing something I'd heard many years before. I'm
    afraid I don't have much recollection of the original source - it
    may have been on comp.compression?

-- 
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
Working, but not speaking, for JetHead Development, Inc.
"We must do something.  This is something.  Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"

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

#89758

Keith Thompson <kst-u@mib.org> writes:

> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
>> Tim Rentsch <txr@alumni.caltech.edu> writes:
>>> Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
>>>> crisdunbar@gmail.com writes:
>>>> <snip>
>>>>> I vaguely recall a quote along the lines of:
>>>>>
>>>>> "A compression algorithm is an 'expansion' algorithm that
>>>>> happens to fail spectacularly for a very small set of input
>>>>> files"
>>>>
>>>> Very nice.  Any idea where its from?  I feel I will have to quote it at
>>>> some point in the future and I'd like to give credit.  (A quick search
>>>> thew up nothing to go on.)
>>>
>>> Perhaps here:
>>>
>>>     http://stackoverflow.com/questions/2643932/md5-purpose-or-uses
>>>
>>>     "A 'compression algorithm' is actually an 'expansion
>>>     algorithm' with some interesting failure cases :)"
>>
>> Thanks.  No sign that they are quoting but I don't suppose that is
>> definitive.
>
> I asked the commenter (user "caf") whether that was an original quote.
> His reply:
>
>     No, I was paraphrasing something I'd heard many years before. I'm
>     afraid I don't have much recollection of the original source - it
>     may have been on comp.compression?

Thanks for asking.  I don't have a stackoverflow login or I would have
done so myself.

-- 
Ben.

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

#89586

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.

-- 
Ben.

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

#89589

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.

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.

-- 
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

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

#89590

On 6/18/2016 9:22 PM, Richard Heathfield wrote:
> 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.
> 
> 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.
> 

What you're missing is the difference between generating a random
sequence and compressing one.

When generating a random sequence, the next value in the sequence is
unpredictable.  However, when compressing a random sequence, the values
have already been generated, and the only requirement is to be able to
recover the original values from a compressed value.

-- 
==================
Remove the "x" from my email address
Jerry Stuckle
jstucklex@attglobal.net
==================

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

#89592

On 19/06/16 02:30, Jerry Stuckle wrote:
> On 6/18/2016 9:22 PM, Richard Heathfield wrote:
>> 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.
>>
>> 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.
>>
>
> What you're missing is the difference between generating a random
> sequence and compressing one.

<shrug> We already discussed compression. I was reflecting on Ben's 
point about 'true' randomness.

> When generating a random sequence, the next value in the sequence is
> unpredictable.

And therefore whether a sequence is random can depend on what you know 
about the mechanism by which the sequence is generated, which was the 
point I was making.

> However, when compressing a random sequence, the values
> have already been generated, and the only requirement is to be able to
> recover the original values from a compressed value.

And if you can, then the random sequence may not have been that random 
after all. For it to be compressible, there must be some element of 
structure or redundancy in its make-up.

-- 
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

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

#89594

On 6/18/2016 9:41 PM, Richard Heathfield wrote:
> On 19/06/16 02:30, Jerry Stuckle wrote:
>> On 6/18/2016 9:22 PM, Richard Heathfield wrote:
>>> 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.
>>>
>>> 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.
>>>
>>
>> What you're missing is the difference between generating a random
>> sequence and compressing one.
> 
> <shrug> We already discussed compression. I was reflecting on Ben's
> point about 'true' randomness.
> 
>> When generating a random sequence, the next value in the sequence is
>> unpredictable.
> 
> And therefore whether a sequence is random can depend on what you know
> about the mechanism by which the sequence is generated, which was the
> point I was making.
>

A "generated sequence" is, by definition, not random.  The only truly
random sequence is one which is derived from a random occurrence.  There
are two currently in general use - the decay of a radioactive element,
and (more common) the noise generated by semiconductors.   Both are
capable of creating truly random sequences, but neither is used much in
computers.

>> However, when compressing a random sequence, the values
>> have already been generated, and the only requirement is to be able to
>> recover the original values from a compressed value.
> 
> And if you can, then the random sequence may not have been that random
> after all. For it to be compressible, there must be some element of
> structure or redundancy in its make-up.
> 

Whether it is random or not is immaterial.  *Any* non-infinite sequence
can be generated by an algorithm.  And even some infinite sequences (i.e
pi, 2(1/2)) can be generated by algorithms.  But those are immaterial
since in computing, there is no such thing as an infinite sequence (or
infinite anything else).

-- 
==================
Remove the "x" from my email address
Jerry Stuckle
jstucklex@attglobal.net
==================

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

#89596

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.

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

#89607

randomness is boring topic here (imo?) - compression is okay

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

#89577

On Saturday, June 18, 2016 at 8:11:37 PM UTC+1, Bill Cunningham wrote:
> 
>     Truely random can't be compressed? If there's a header indicating the 
> algorithm of randomness, or encryption why not?
> 
Compression works because when we've got two data items, the first tells
us something about what the second is likely to be. Assuming that
any sequence of bits for item two is possible, but some more likely
than others (you can have the sequence qx in English text, and in
fact you just saw it, but almost always q is followed by u), you take
the probability distribution of data item two, given data item one,
and allocate bits according to that distribution. So the sequence "qu"
compresses well, the inevitable price is that the very rare sequence 
"qx" expands.
As long as our estimation of the probability distribution of data 
item two given item one is perfect, we can have no better compression,
but that's very hard to achieve. So there's usually some scope for
improvement in compression algorithms, but not much.

Random data, by definition, has uniform probability. Data item
one doesn't predict or tell us anything about data item two.
So we can't compress it. But only if it is truly random.  
  

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

#89610

In article <455ed59d-5eac-4933-98fd-d616c253daa4@googlegroups.com>, 
malcolm.mclean5@btinternet.com says...
> 
> On Saturday, June 18, 2016 at 8:11:37 PM UTC+1, Bill Cunningham wrote:
> > 
> >     Truely random can't be compressed? If there's a header indicating the 
> > algorithm of randomness, or encryption why not?
> > 
> Compression works because when we've got two data items, the first tells
> us something about what the second is likely to be. Assuming that
> any sequence of bits for item two is possible, but some more likely
> than others (you can have the sequence qx in English text, and in
> fact you just saw it, but almost always q is followed by u), you take
> the probability distribution of data item two, given data item one,
> and allocate bits according to that distribution. So the sequence "qu"
> compresses well, the inevitable price is that the very rare sequence 
> "qx" expands.
> As long as our estimation of the probability distribution of data 
> item two given item one is perfect, we can have no better compression,
> but that's very hard to achieve. So there's usually some scope for
> improvement in compression algorithms, but not much.
> 
> Random data, by definition, has uniform probability. Data item
> one doesn't predict or tell us anything about data item two.
> So we can't compress it. But only if it is truly random.  
>   

Why are you on about "predicting"?  Compression doesn't require that one 
item predict another item, only that there be identifiable patterns that 
can be replaced with shorter patterns.

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

#89614

W dniu niedziela, 19 czerwca 2016 12:59:14 UTC+2 użytkownik J. Clarke napisał:
> In article <455ed59d-5eac-4933-98fd-d616c253daa4@googlegroups.com>, 
> malcolm.mclean5@btinternet.com says...
> > 
> > On Saturday, June 18, 2016 at 8:11:37 PM UTC+1, Bill Cunningham wrote:
> > > 
> > >     Truely random can't be compressed? If there's a header indicating the 
> > > algorithm of randomness, or encryption why not?
> > > 
> > Compression works because when we've got two data items, the first tells
> > us something about what the second is likely to be. Assuming that
> > any sequence of bits for item two is possible, but some more likely
> > than others (you can have the sequence qx in English text, and in
> > fact you just saw it, but almost always q is followed by u), you take
> > the probability distribution of data item two, given data item one,
> > and allocate bits according to that distribution. So the sequence "qu"
> > compresses well, the inevitable price is that the very rare sequence 
> > "qx" expands.
> > As long as our estimation of the probability distribution of data 
> > item two given item one is perfect, we can have no better compression,
> > but that's very hard to achieve. So there's usually some scope for
> > improvement in compression algorithms, but not much.
> > 
> > Random data, by definition, has uniform probability. Data item
> > one doesn't predict or tell us anything about data item two.
> > So we can't compress it. But only if it is truly random.  
> >   
> 
> Why are you on about "predicting"?  Compression doesn't require that one 
> item predict another item, only that there be identifiable patterns that 
> can be replaced with shorter patterns.

i do nt know how compression works (know the basics of huffman and jpg/mpg only)
It would be ok if someone would write on some details in simple words - then discussion on it could appear
as to thos patterns, this is all much about the patterns (and only patterns?) but i am not sure but guess that today only most primitive patterns are searched or detected 
- i mean stright blocks or the same in frequenzy domains when in reality data
could represent a myriad of hidden patterns
- just not as plain as byte blocks

Isnt it like that? Do today used algorithms
explore that ? 

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

#89615

On Sunday, June 19, 2016 at 11:59:14 AM UTC+1, J. Clarke wrote
> 
> Why are you on about "predicting"?  Compression doesn't require that one 
> item predict another item, only that there be identifiable patterns that 
> can be replaced with shorter patterns.

.
That's the same way of saying the same thing.
You can think of the problem as there being two data items, A and B,
with B following and before the program starts, we have no clue
what A will be, but after A arrives, we've got an estimate of
the probability distribution of B.
Or you can think of the problem as most of the input having regular
patterns, e.g. repeated runs of equal bytes or repeated substrings
which you can detect and replace with more compact representations.

Ultimately those are just two different ways of making the same
observation. 

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

#89801

In article <96631b37-a326-4a3e-9eab-bf67279b82d5@googlegroups.com>, 
malcolm.mclean5@btinternet.com says...
> 
> On Sunday, June 19, 2016 at 11:59:14 AM UTC+1, J. Clarke wrote
> > 
> > Why are you on about "predicting"?  Compression doesn't require that one 
> > item predict another item, only that there be identifiable patterns that 
> > can be replaced with shorter patterns.
> 
> .
> That's the same way of saying the same thing.
> You can think of the problem as there being two data items, A and B,
> with B following and before the program starts, we have no clue
> what A will be, but after A arrives, we've got an estimate of
> the probability distribution of B.
> Or you can think of the problem as most of the input having regular
> patterns, e.g. repeated runs of equal bytes or repeated substrings
> which you can detect and replace with more compact representations.
> 
> Ultimately those are just two different ways of making the same
> observation. 

Why do we have no clue what A will be?  If we are dealing with a 
situation in which it is sufficiently important that compression be 
achieved, we may look at the entire dataset and examine and analyze it 
at length before we even start to write code.  Compression doesn't have 
to be on-the-fly in realtime with freshly acquired data to be useful.

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

Page 4 of 5 — ← Prev page 1 2 3 [4] 5  Next page →

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

csiph-web