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

Groups > comp.compression > #2359 > unrolled thread

My codec: : possible impending breakthrough?

Back to article view | Back to comp.compression

Contents

  My codec: : possible impending breakthrough? Harry Potter <rose.joseph12@yahoo.com> - 2014-06-08 11:28 -0700
    Re: My codec: : possible impending breakthrough? Ernst <ernst_berg@sbcglobal.net> - 2014-06-08 15:06 -0700
      Re: My codec: : possible impending breakthrough? Ernst <ernst_berg@sbcglobal.net> - 2014-06-09 12:51 -0700
      Re: My codec: : possible impending breakthrough? Harry Potter <rose.joseph12@yahoo.com> - 2014-06-21 05:39 -0700
        Re: My codec: : possible impending breakthrough? BGB <cr88192@hotmail.com> - 2014-06-21 10:27 -0500
          Re: My codec: : possible impending breakthrough? Harry Potter <rose.joseph12@yahoo.com> - 2014-06-21 13:42 -0700
            Re: My codec: : possible impending breakthrough? BGB <cr88192@hotmail.com> - 2014-06-22 00:22 -0500
            Re: My codec: : possible impending breakthrough? Ernst <ernst_berg@sbcglobal.net> - 2014-06-22 17:46 -0700
        Re: My codec: : possible impending breakthrough? Ernst <ernst_berg@sbcglobal.net> - 2014-06-22 17:43 -0700
    Re: My codec: : possible impending breakthrough? Fibonacci Code <anglikai@gmail.com> - 2014-06-23 20:53 -0700
      Re: My codec: : possible impending breakthrough? Noob <root@127.0.0.1> - 2014-06-24 09:52 +0200
        Re: My codec: : possible impending breakthrough? Fibonacci Code <anglikai@gmail.com> - 2014-06-24 06:28 -0700
      Re: My codec: : possible impending breakthrough? jacko <jackokring@gmail.com> - 2014-06-28 08:42 -0700
        Re: My codec: : possible impending breakthrough? Fibonacci Code <anglikai@gmail.com> - 2014-06-28 22:08 -0700
          Re: My codec: : possible impending breakthrough? jacko <jackokring@gmail.com> - 2014-06-29 06:20 -0700
            Re: My codec: : possible impending breakthrough? jacko <jackokring@gmail.com> - 2014-06-29 06:22 -0700
            Re: My codec: : possible impending breakthrough? Richard Damon <Richard@Damon-Family.org> - 2014-06-29 14:06 -0400
              Re: My codec: : possible impending breakthrough? jacko <jackokring@gmail.com> - 2014-06-30 05:11 -0700
                Re: My codec: : possible impending breakthrough? jacko <jackokring@gmail.com> - 2014-06-30 05:22 -0700
                Re: My codec: : possible impending breakthrough? Robert Wessel <robertwessel2@yahoo.com> - 2014-06-30 10:31 -0500
                  Re: My codec: : possible impending breakthrough? jacko <jackokring@gmail.com> - 2014-06-30 08:39 -0700
                    Re: My codec: : possible impending breakthrough? Robert Wessel <robertwessel2@yahoo.com> - 2014-06-30 15:51 -0500
                      Re: My codec: : possible impending breakthrough? jacko <jackokring@gmail.com> - 2014-06-30 17:29 -0700
                        Re: My codec: : possible impending breakthrough? Robert Wessel <robertwessel2@yahoo.com> - 2014-06-30 19:44 -0500
                          Re: My codec: : possible impending breakthrough? Noob <root@127.0.0.1> - 2014-07-01 10:00 +0200
                    Re: My codec: : possible impending breakthrough? Richard Damon <Richard@Damon-Family.org> - 2014-06-30 22:25 -0400
                      Re: My codec: : possible impending breakthrough? jacko <jackokring@gmail.com> - 2014-06-30 19:57 -0700
                        Re: My codec: : possible impending breakthrough? Richard Damon <Richard@Damon-Family.org> - 2014-07-02 08:14 -0400
                          Re: My codec: : possible impending breakthrough? jacko <jackokring@gmail.com> - 2014-07-09 05:02 -0700

Page 2 of 2 — ← Prev page 1 [2]

#2413

> 
> It does not, however, matter if you get there in a single step, or by
> 
> multiple steps.  But of the general class of files only that tiny
> 
> fraction will be compressible to that size.
> 
the fact is you only need one to, and given time and randomness ...

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

#2414

On Mon, 30 Jun 2014 08:39:14 -0700 (PDT), jacko <jackokring@gmail.com>
wrote:

>
>> 
>> It does not, however, matter if you get there in a single step, or by
>> 
>> multiple steps.  But of the general class of files only that tiny
>> 
>> fraction will be compressible to that size.
>> 
>the fact is you only need one to, and given time and randomness ...


And a probability so close to zero that it's meaningless.  What's the
point if it's so unlikely to be useful that it'll probably never
happen even a single time in a billion, billion, billion lifetimes of
the universe?  And while you're waiting to profit from that, you're
paying for it on all the other files you tried to "compress".

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

#2415

> And a probability so close to zero that it's meaningless.  What's the
> point if it's so unlikely to be useful that it'll probably never
> happen even a single time in a billion, billion, billion lifetimes of
> the universe?  And while you're waiting to profit from that, you're
> paying for it on all the other files you tried to "compress".

A proof is not an implementation. Simple proofs may have apparently useless implementations, a useful implementation (still quite slow but usable) may have a much more complex proof.

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

#2416

On Mon, 30 Jun 2014 17:29:32 -0700 (PDT), jacko <jackokring@gmail.com>
wrote:

>
>> And a probability so close to zero that it's meaningless.  What's the
>> point if it's so unlikely to be useful that it'll probably never
>> happen even a single time in a billion, billion, billion lifetimes of
>> the universe?  And while you're waiting to profit from that, you're
>> paying for it on all the other files you tried to "compress".
>
>A proof is not an implementation. Simple proofs may have apparently useless implementations, a useful implementation (still quite slow but usable) may have a much more complex proof.


I'm baffled...

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

#2422

On 01/07/2014 02:44, Robert Wessel wrote:

> I'm baffled...

And God Created Killfile.

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

#2417

On 6/30/14, 11:39 AM, jacko wrote:
>
>>
>> It does not, however, matter if you get there in a single step, or by
>>
>> multiple steps.  But of the general class of files only that tiny
>>
>> fraction will be compressible to that size.
>>
> the fact is you only need one to, and given time and randomness ...
>

So your compression algorithm will only take SOME of the m (> n) bit 
patterns and compress them to n bit (and fail to do anything on the 
rest). THAT is doable (but not generally useful)

Or is it that you are converting the m bit pattern to n bits, but it 
isn't reversible?

Or is the time that the compression happened important (but you are not 
counting the bits needed to express the time in your encoding)? (That's 
cheating).

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

#2419

On Tuesday, 1 July 2014 03:25:49 UTC+1, Richard Damon  wrote:
> On 6/30/14, 11:39 AM, jacko wrote:
> 
> >
> 
> >>
> 
> >> It does not, however, matter if you get there in a single step, or by
> 
> >>
> 
> >> multiple steps.  But of the general class of files only that tiny
> 
> >>
> 
> >> fraction will be compressible to that size.
> 
> >>
> 
> > the fact is you only need one to, and given time and randomness ...
> 
> >
> 
> 
> 
> So your compression algorithm will only take SOME of the m (> n) bit 
> 
> patterns and compress them to n bit (and fail to do anything on the 
> 
> rest). THAT is doable (but not generally useful)
> 
> 
> 
> Or is it that you are converting the m bit pattern to n bits, but it 
> 
> isn't reversible?
> 
> 
> 
> Or is the time that the compression happened important (but you are not 
> 
> counting the bits needed to express the time in your encoding)? (That's 
> 
> cheating).

"Linked lists and Compression" thread for an algorithm. So after expanding the n bit pattern to m bits, giving m-n bits, why would you not split this into (out = m-n bits, recycle n bits) -> (out = m-n bits, (out = m-n bits, recycle n bits)) = (out = 2*(m-n) bits, recycle n bits).

Maybe somehow you don't think the m-n bits can be bit values of your choice by some means?

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

#2426

On 6/30/14, 10:57 PM, jacko wrote:

> "Linked lists and Compression" thread for an algorithm. So after expanding the n bit pattern to m bits, giving m-n bits, why would you not split this into (out = m-n bits, recycle n bits) -> (out = m-n bits, (out = m-n bits, recycle n bits)) = (out = 2*(m-n) bits, recycle n bits).
>
> Maybe somehow you don't think the m-n bits can be bit values of your choice by some means?
>

Maybe you don't understand what (reversible) compression IS.

To claim you have have a compression which will always produce a small 
result. This means that for ANY m-bit pattern, you will produce an n-bit 
compressed version with n < m. Being reversible, says that you can take 
an n-bit result, and get back the original m-bit result.

It is allowed that some n-bit results might not be used, but a proper 
compression algorithm will take in every m-bit value. It is also allowed 
that n may vary from input pattern to input pattern, and in real 
practical compression it normally will vary, and the desired value is 
that the average value of n, over a weighted average of expected inputs 
will be smaller than the size of the input. It will be bigger in some 
cases, but we are using the non-uniformity of the distribution of input 
patterns to get a reduction in output side.

Note that in the proof of the impossibility of universal compression, 
the n-bit patterns are OUTPUTS of the compression engine, and are 
applied to the decompression engine. The m-bit patterns are the set of 
original inputs to the compression. You are not allowed to restrict the 
value of the m-n bits, because the compression algorithm is expected to 
accept EVERY m-bit input pattern.

The essence of the proof is that if a mapping takes a larger set to a 
smaller set, it is impossible for it to be reversible, as there isn't 
enough information in the output set to get back to every element of the 
input set.

In simpler words, given M input messages being mapped into N output 
messages N < M, the mapping can not be reversible without loss, as 
reverse mapping could only generate N of M possible messages, and M-N 
messages have been "lost".

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

#2431

On Wednesday, 2 July 2014 13:14:37 UTC+1, Richard Damon  wrote:
> On 6/30/14, 10:57 PM, jacko wrote:
> 
> 
> 
> > "Linked lists and Compression" thread for an algorithm. So after expanding the n bit pattern to m bits, giving m-n bits, why would you not split this into (out = m-n bits, recycle n bits) -> (out = m-n bits, (out = m-n bits, recycle n bits)) = (out = 2*(m-n) bits, recycle n bits).
> 
> >
> 
> > Maybe somehow you don't think the m-n bits can be bit values of your choice by some means?
> 
> >
> 
> 
> 
> Maybe you don't understand what (reversible) compression IS.
> 
> 
> 
> To claim you have have a compression which will always produce a small 
> 
> result. This means that for ANY m-bit pattern, you will produce an n-bit 
> 
> compressed version with n < m. Being reversible, says that you can take 
> 
> an n-bit result, and get back the original m-bit result.
> 
> 
> 
> It is allowed that some n-bit results might not be used, but a proper 
> 
> compression algorithm will take in every m-bit value. It is also allowed 
> 
> that n may vary from input pattern to input pattern, and in real 
> 
> practical compression it normally will vary, and the desired value is 
> 
> that the average value of n, over a weighted average of expected inputs 
> 
> will be smaller than the size of the input. It will be bigger in some 
> 
> cases, but we are using the non-uniformity of the distribution of input 
> 
> patterns to get a reduction in output side.
> 
> 
> 
> Note that in the proof of the impossibility of universal compression, 
> 
> the n-bit patterns are OUTPUTS of the compression engine, and are 
> 
> applied to the decompression engine. The m-bit patterns are the set of 
> 
> original inputs to the compression. You are not allowed to restrict the 
> 
> value of the m-n bits, because the compression algorithm is expected to 
> 
> accept EVERY m-bit input pattern.
> 
> 
> 
> The essence of the proof is that if a mapping takes a larger set to a 
> 
> smaller set, it is impossible for it to be reversible, as there isn't 
> 
> enough information in the output set to get back to every element of the 
> 
> input set.
> 

Maybe you don't understand what a set is? The set representation is not necessarily the set, but maybe a different set.

> 
> In simpler words, given M input messages being mapped into N output 
> 
> messages N < M, the mapping can not be reversible without loss, as 
> 
> reverse mapping could only generate N of M possible messages, and M-N 
> 
> messages have been "lost".

So in the simplest case given N input messages and N output messages, the number of possible outputs for any input is N. Pick 2 of these N, so that one represents 0 and a second represents 1. by knowing both the N input and the N output, a 0 or 1 can be inferred. All that is required is N+N bits to be stored, and to have a reversible function which can be reapplied to any N giving another N. By dropping N bits through the function making another N bits leaves storage at 2*N bits.

This is true. The existence of a reversible function F (and it's reverse R) is the remainder of the proof.

The function must take the following form
F: if(not_uniquely_decodable) N->NU else if(inferred) N->N1 else N->N0;

The question then becomes is not_uniquely_decodable ALWAYS true for ALL iterations of F? The opposite would imply some inferable information requiring no bit space.

function decompress() {
    if(Rev0StrictShort) { 
        RevTravel0();
        if(For1StrictLong) { emit(0); ForTravel0(); return; }
        ForTravel0();
        if(Rev1StrictLong) { 
            RevTravel1();
            if(!For0StrictShort) { emit(1); return; }
            else { ForTravel1(); RevTravel0(); return; }
    } else { RevTravel0(); return; }
}   

and

function compress() {
    if(For1StrictLong) { 
        if(For0StrictShort) {
            if(absorb()) { ForTravel1(); return;}
            else { ForTravel0(); return; }
        } else {
            ForTravel1(); return;
        }
    } else { ForTravel0(); return; }
}    

The necessity for introducing strictly long and strictly short as concepts on the the zero and one paths followed between the N nodes is to ensure unique decoding. A strictly short path is a path which has all short paths into the terminal node of the path. Also if the long path is zero, the short path has to be one, and vice versa.

[toc] | [prev] | [standalone]

Page 2 of 2 — ← Prev page 1 [2]

Back to top | Article view | comp.compression

csiph-web