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

Groups > comp.compression > #1694

Re: Question about compression with conditions

Show all headers | View raw

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

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

Thread

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

csiph-web