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

Groups > comp.compression > #1691 > unrolled thread

Question about compression with conditions

Back to article view | Back to comp.compression

Contents

  Question about compression with conditions "peter.c" <peter.c@invalid.invalid> - 2013-01-19 11:41 +0100
    Re: Question about compression with conditions John Reiser <jreiserfl@comcast.net> - 2013-01-19 07:10 -0800
      Re: Question about compression with conditions "peter.c" <peter.c@invalid.invalid> - 2013-01-19 19:08 +0100
      Re: Question about compression with conditions glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2013-01-19 18:59 +0000
        Re: Question about compression with conditions John Reiser <jreiserfl@comcast.net> - 2013-01-19 13:15 -0800
          Re: Question about compression with conditions glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2013-01-19 22:41 +0000
        Re: Question about compression with conditions "peter.c" <peter.c@invalid.invalid> - 2013-01-19 23:23 +0100

#1691 — Question about compression with conditions

hi,

I would like to know if there is an algorithm which does compression 
with conditions.

As an example, let's imagine I have chunks of 128 bytes, that is to say 
1024 bits.

In these chunks I always have at least 522 bits to "1" (and it can go up 
to 532 bits).

How can this kind of data be compressed ?

Thank you

Peter

[toc] | [next] | [standalone]

#1692

> As an example, let's imagine I have chunks of 128 bytes, that is to say 1024 bits.
> 
> In these chunks I always have at least 522 bits to "1" (and it can go up to 532 bits).

The number of distinct allowed chunks is C(1024,522) + C(1024,523) + ... + C(1024,532)
where C(n,k) is the number of combinations of n things (bits) taken k at a time (the
'1' bits).  The sum is a small fraction of 2**1024, which is the number of all subsets
of the 1024 bits.  Therefore: logically enumerate the allowed chunks into a single
ordered list.  Encode any particular allowed chunk as its position in the list.
For a sequence of chunks, the corresponding sequence of position ordinals
may be compressed further using ordinary techniques based on entropy.

-- 

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

#1693

Le 19/01/2013 16:10, John Reiser a écrit :
>> As an example, let's imagine I have chunks of 128 bytes, that is to say 1024 bits.
>>
>> In these chunks I always have at least 522 bits to "1" (and it can go up to 532 bits).
>
> The number of distinct allowed chunks is C(1024,522) + C(1024,523) + ... + C(1024,532)
> where C(n,k) is the number of combinations of n things (bits) taken k at a time (the
> '1' bits).  The sum is a small fraction of 2**1024, which is the number of all subsets
> of the 1024 bits.  Therefore: logically enumerate the allowed chunks into a single
> ordered list.  Encode any particular allowed chunk as its position in the list.
> For a sequence of chunks, the corresponding sequence of position ordinals
> may be compressed further using ordinary techniques based on entropy.
>

Thank you for your answer, it's ok for me.
I have a second question, about combinations:
what if I have a second condition ? As an example, I can't have more 
then "n" consecutive "1".
for example, in my chunks I can't have more than 12 consecutive "1"
So, the general formula with C(n,p) gives more possibilities than necessary.

Is there somewhere a formula to get fast the number of possible 
combinations, or are we supposed to do that with additions and/or 
subtractions ?

Thank you

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

#1694

John Reiser <jreiserfl@comcast.net> wrote:
>> As an example, let's imagine I have chunks of 128 bytes, that is to say 1024 bits.
 
>> In these chunks I always have at least 522 bits to "1" (and it can go up to 532 bits).
 
> The number of distinct allowed chunks is C(1024,522) + C(1024,523) + ... + C(1024,532)
> where C(n,k) is the number of combinations of n things (bits) taken k at a time (the
> '1' bits).  The sum is a small fraction of 2**1024, which is the number of all subsets
> of the 1024 bits.  Therefore: logically enumerate the allowed chunks into a single
> ordered list.  Encode any particular allowed chunk as its position in the list.
> For a sequence of chunks, the corresponding sequence of position ordinals
> may be compressed further using ordinary techniques based on entropy.

Is it really that small?

I was trying to guesstimate it, but I didn't come up with anything.

My thought was that it wasn't quite as small as you might hope.

If you compute the logs of the factorials, it might be easier.

-- glen

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

#1695

>> The number of distinct allowed chunks is C(1024,522) + C(1024,523) + ... + C(1024,532)
>> where C(n,k) is the number of combinations of n things (bits) taken k at a time (the
>> '1' bits).  The sum is a small fraction of 2**1024, which is the number of all subsets
>> of the 1024 bits.

> Is it really that small?

#include <math.h>
#include <stdio.h>

double lf[1025];

int
main(int argc, char *argv[])
{
	int j;
	for (j=1; j < 1025; ++j)
		lf[j] = log(j) + lf[-1+ j];
	double t;
	for (t=0.0, j=522; j<=532; ++j)
		t += exp(lf[1024] - lf[j] - lf[1024 - j]);
	double const two_1024 = exp(1024*log(2));
	printf("        t = %g\n"
	       "  2**1024 = %g\n"
	       "t/2**1024 = %g\n",
		t, two_1024, t / two_1024);
	printf("  savings = %g bits\n", - log2(t / two_1024));
	return 0;
}

        t = 3.16949e+307
  2**1024 = 1.79769e+308
t/2**1024 = 0.176309
  savings = 2.50382 bits

-- 

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

#1697

John Reiser <jreiserfl@comcast.net> wrote:
>>> The number of distinct allowed chunks is C(1024,522) + C(1024,523) + ... + C(1024,532)
>>> where C(n,k) is the number of combinations of n things (bits) taken k at a time (the
>>> '1' bits).  The sum is a small fraction of 2**1024, which is the number of all subsets
>>> of the 1024 bits.
 
>> Is it really that small?
 
> #include <math.h>
> #include <stdio.h>
 
> double lf[1025];
 
> int
> main(int argc, char *argv[])
> {
>        int j;
>        for (j=1; j < 1025; ++j)
>                lf[j] = log(j) + lf[-1+ j];
>        double t;
>        for (t=0.0, j=522; j<=532; ++j)
>                t += exp(lf[1024] - lf[j] - lf[1024 - j]);
>        double const two_1024 = exp(1024*log(2));
>        printf("        t = %g\n"
>               "  2**1024 = %g\n"
>               "t/2**1024 = %g\n",
>                t, two_1024, t / two_1024);
>        printf("  savings = %g bits\n", - log2(t / two_1024));
>        return 0;
> }
 
>        t = 3.16949e+307
>  2**1024 = 1.79769e+308
> t/2**1024 = 0.176309
>  savings = 2.50382 bits

So, 1024 bits goes down to 1021. Sometimes that might be worthwhile,
but most of the time not.

That is about what I was going to guess.

-- glen

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

#1696

Le 19/01/2013 19:59, glen herrmannsfeldt a écrit :
> John Reiser <jreiserfl@comcast.net> wrote:
>>> As an example, let's imagine I have chunks of 128 bytes, that is to say 1024 bits.
>
>>> In these chunks I always have at least 522 bits to "1" (and it can go up to 532 bits).
>
>> The number of distinct allowed chunks is C(1024,522) + C(1024,523) + ... + C(1024,532)
>> where C(n,k) is the number of combinations of n things (bits) taken k at a time (the
>> '1' bits).  The sum is a small fraction of 2**1024, which is the number of all subsets
>> of the 1024 bits.  Therefore: logically enumerate the allowed chunks into a single
>> ordered list.  Encode any particular allowed chunk as its position in the list.
>> For a sequence of chunks, the corresponding sequence of position ordinals
>> may be compressed further using ordinary techniques based on entropy.
>
> Is it really that small?
>
> I was trying to guesstimate it, but I didn't come up with anything.
>
> My thought was that it wasn't quite as small as you might hope.
>
> If you compute the logs of the factorials, it might be easier.
>
> -- glen
>

Hi Glenn,

type the formula in the website of mathematica :
ln(exp(1024*ln(2))/(sum(C(1024,x)) from x=522 to 532))/ln(2)

or copy in your browser this link:
http://www.wolframalpha.com/input/?i=ln%28exp%281024*ln%282%29%29%2F%28sum%28C%281024%2Cx%29%29+from+x%3D522+to+532%29%29%2Fln%282%29

the result is displayed : 2.50382

so, the result is about 5.6 times smaller than the original interval

exp(2.50382*ln(2))

http://www.wolframalpha.com/input/?i=exp%282.50382*ln%282%29%29

result = 5.67185...

it is not really that small, but it's ok, simply based on mathematics

bye

peter

[toc] | [prev] | [standalone]

Back to top | Article view | comp.compression

csiph-web