Hi,

I have a question about data compression. When i have a file with
multiple 256 byte blocks which contain exactly 256 different values.
And any order can occur. How much can i compress this file?

I think the maximum should be log2(256!)=211 bytes. And the most
practical way to encode it, is using 8 bits for the first 128 values,
7 bits for the next 64 , etc.

But maybe there are better methods and someone can point me in the
right direction. 

Any help would be much appreciated!

Grtz,
Eric

> 
> I have a question about data compression. When i have a file with
> multiple 256 byte blocks which contain exactly 256 different values.
> And any order can occur. How much can i compress this file?
> 
> I think the maximum should be log2(256!)=211 bytes. And the most
> practical way to encode it, is using 8 bits for the first 128 values,
> 7 bits for the next 64 , etc.
> 

log2(256!) is less than 210.5 bytes (per block), so if you have many
blocks in your file and you use some kind of arithmetic coder, you
can achieve slightly better result.

J.

Eric <n@m.com> wrote in news:hrkfe0l1dfipeldbh1q2lv4s6rffsfg9db@4ax.com:

> Hi,
> 
> I have a question about data compression. When i have a file with
> multiple 256 byte blocks which contain exactly 256 different values.
> And any order can occur. How much can i compress this file?
> 
> I think the maximum should be log2(256!)=211 bytes. And the most
> practical way to encode it, is using 8 bits for the first 128 values,
> 7 bits for the next 64 , etc.
> 
> But maybe there are better methods and someone can point me in the
> right direction. 
> 
> Any help would be much appreciated!
> 
> Grtz,
> Eric

 Your corrent the 211 byte would be the max length for bext compression.

You approach would yield a file alway greater than 220 bytes.
You approach would pracket the correct optimal solution if you use
8 bits for fist value than a changing huffman tree of depth 7 to 8
for next 127 vaules then a 7 bit tree for the 129th value then 7 to
6 bits for the next 63 values and so on. The code is not hard
exaim code from huffman vitter style page for how to do it.

  Yes arithmetic would be best then you would only have 210 and 211
byte segments.



David A. Scott
-- 
My Crypto code
http://cryptography.org/cgi-bin/crypto.cgi/Misc/scott19u.zip
http://cryptography.org/cgi-bin/crypto.cgi/Misc/scott16u.zip
http://www.jim.com/jamesd/Kong/scott19u.zip old version
My Compression code http://bijective.dogma.net/
**TO EMAIL ME drop the roman "five" **
Disclaimer:I am in no way responsible for any of the statements
 made in the above text. For all I know I might be drugged.
As a famous person once said "any cryptograhic
system is only as strong as its weakest link"

"Eric" <n@m.com> wrote in message
news:hrkfe0l1dfipeldbh1q2lv4s6rffsfg9db@4ax.com...
> Hi,
>
> I have a question about data compression. When i have a file with
> multiple 256 byte blocks which contain exactly 256 different values.
> And any order can occur. How much can i compress this file?
>
> I think the maximum should be log2(256!)=211 bytes. And the most
> practical way to encode it, is using 8 bits for the first 128 values,
> 7 bits for the next 64 , etc.
>
> But maybe there are better methods and someone can point me in the
> right direction.
>
> Any help would be much appreciated!
>
I would guess trying to figure out a way to compress the "order" of the
values might help.

eg, as an overly simplistic example:
assuming that the values start of as an even-height binary tree with the
leaves as the values 0-255, and at each point in the tree the valuespace can
be swapped (lower and upper halves), then any "basic" ordering (eg:
3,2,1,0,7,6,5,4,11,10,9,8,... 1,0,3,2,5,4,...) could be represented in 8
bits, and slightly more complex patterns (allowing a swap at every point in
the tree) could be represented in 255 bits (32 bytes).

a rough guess would make me think that extending this approach to allow "all
possible patterns" would require 65536 bits (effectively a 2d swap grid),
which would not be at all effective (it is much smaller just to store the
values).
one could take into account that there would likely be long runs of 0 bits
with only a single 1 bit at each spot (though many other possibilities
exist, the path may not be straight). any form of rle compression would
likely end up with results larger than the original (arithmatic coding would
also likely be ineffective).

maybe bubblesort could be modified into a compressor (reversing the sort
would lead to the input, though I am doubtful of the effectiveness).

the problem is "any order" does not make it seem like this kind of approach
could offer that much, relying on something like this would probably be
better for "patterns"...

dunno, this whole idea may be pointless...

maybe cool:
you view the space for decompression as a list;
you have an array of 256 bytes indicating the relative position in the list
for the insert (eg, 0..127 for insert from the start, -128..-1 for positions
relative to the end);
you go through the list inserting the values 0 through 255, with the list
getting longer after each insert.

for compression you start off with an empty list, and figure the indices for
the occurance of the values.
you insert each item in it's respective spot relative to adjacent members,
choosing the 'shortest' path in each case.

this will lead to output the same size as the input, and should have most of
the values a lot closer to 0, which will make it at least succeptible to
huffman or aritmatic coding...

eg: all values in descending order will lead to an output of all 0's, and
all values in ascending order will lead to an output of all -1's...

dunno how well this will work in practice, at least the output can't get any
bigger with this...

dunno if this will help any.

cr88192 wrote:
)
) "Eric" wrote:
)> I have a question about data compression. When i have a file with
)> multiple 256 byte blocks which contain exactly 256 different values.
)> And any order can occur. How much can i compress this file?

  <snip>

) I would guess trying to figure out a way to compress the "order" of the
) values might help.

  <snip>

) the problem is "any order" does not make it seem like this kind of approach
) could offer that much, relying on something like this would probably be
) better for "patterns"...

Exactly.  In the case of 'any order', arithmetic encoding will approach the
theoretical limit.  (The theoretical limit is log256(256!) = 210.5 bytes.)


Side note: An approach where you (virtually) define a list of all possible
permutations, and then can quickly determine at what position in the list
any given permutation would be would get you the theoretical limit.
(You would also have to be able to generate the Nth permutation.)


SaSW, Willem
-- 
Disclaimer: I am in no way responsible for any of the statements
            made in the above text. For all I know I might be
            drugged or something..
            No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

"Willem" <willem@stack.nl> wrote in message
news:slrncegbr3.19l8.willem@toad.stack.nl...
> cr88192 wrote:
> )
> ) "Eric" wrote:
> )> I have a question about data compression. When i have a file with
> )> multiple 256 byte blocks which contain exactly 256 different values.
> )> And any order can occur. How much can i compress this file?
>
>   <snip>
>
> ) I would guess trying to figure out a way to compress the "order" of the
> ) values might help.
>
>   <snip>
>
> ) the problem is "any order" does not make it seem like this kind of
approach
> ) could offer that much, relying on something like this would probably be
> ) better for "patterns"...
>
> Exactly.  In the case of 'any order', arithmetic encoding will approach
the
> theoretical limit.  (The theoretical limit is log256(256!) = 210.5 bytes.)
>
I would guess though that within this situation (only one occurance of a
certain value), the traditional theoretical limit does not apply, and some
lesser value exists (for which I am unsure).

I am expecting that it will not be that difficult to break this limit for
this kind of data...

>
> Side note: An approach where you (virtually) define a list of all possible
> permutations, and then can quickly determine at what position in the list
> any given permutation would be would get you the theoretical limit.
> (You would also have to be able to generate the Nth permutation.)
>
yes. I still figure that this would be a bit smaller than 211 bytes though
(this is not an arbitrary bytestream either...).

this is a special case, and I now have ideas for how this can be better (eg:
by breaking from the "single unique value" concept to another one, eg, that
of "distance"...).

of course, I can't say anything really without experimentation (and the
always likely resultant failure).
in my case, I can't really imagine how this would be generally useful, so it
doesn't really justify experimentation imo.

cr88192 wrote:
)> Exactly.  In the case of 'any order', arithmetic encoding will approach
) the
)> theoretical limit.  (The theoretical limit is log256(256!) = 210.5 bytes.)
)>
) I would guess though that within this situation (only one occurance of a
) certain value), the traditional theoretical limit does not apply, and some
) lesser value exists (for which I am unsure).

I already accounted for the single occurrance of a certain value in my
calculation of the theoretical limit.  What part of log256(256!) did you
not understand ?

) I am expecting that it will not be that difficult to break this limit for
) this kind of data...

You expect wrongly.

)> Side note: An approach where you (virtually) define a list of all possible
)> permutations, and then can quickly determine at what position in the list
)> any given permutation would be would get you the theoretical limit.
)> (You would also have to be able to generate the Nth permutation.)
)>
) yes. I still figure that this would be a bit smaller than 211 bytes though
) (this is not an arbitrary bytestream either...).

It would be 210.5 bytes, exactly, because this scheme rounds up to the
nearest whole amount of bits.  There are 256! possible permutations.
This means that the generated number would fall between 0 and 256!, meaning
you need log2(256!) bits to represent the number minimally.

) ...
) in my case, I can't really imagine how this would be generally useful, so it
) doesn't really justify experimentation imo.

The fact that with arithmetic encoding you can easily approach the
theoretical limit, which actually *is* the theoretical limit for this kind
of data, because I *did* account for everything known about the data, means
that experimentation with harebrained schemes in useless.

Fact of life (well, of compression at least): if you can model the
probabilities accurately, arithmetic encoding approaches the theoretical
limit, and you can not do better.

In case of 'each value occurs once', the probability of a symbol is either
1/N or 0, depending on if the symbol has already been seen.

An ideal arithcoder would need log2(256) + log2(255) + ... + log2(1) bits.
I think you'll find that this equates to 1684.0 bits.


SaSW, Willem
-- 
Disclaimer: I am in no way responsible for any of the statements
            made in the above text. For all I know I might be
            drugged or something..
            No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

On Mon, 5 Jul 2004 01:49:14 +1000, "cr88192"
<cr88192@protect.hotmail.com> wrote:

--8<--

>> But maybe there are better methods and someone can point me in the
>> right direction.
>>
>> Any help would be much appreciated!
>>
>I would guess trying to figure out a way to compress the "order" of the
>values might help.
>
>eg, as an overly simplistic example:
>assuming that the values start of as an even-height binary tree with the
>leaves as the values 0-255, and at each point in the tree the valuespace can

--8<--

>maybe bubblesort could be modified into a compressor (reversing the sort
>would lead to the input, though I am doubtful of the effectiveness).
>
>the problem is "any order" does not make it seem like this kind of approach
>could offer that much, relying on something like this would probably be
>better for "patterns"...

Creating an optimum conversion from 0..255 lists to the data blocks
sounds like a cool AI project to implement. That's kind of like,
looking for the fastest way to unsort it. But i'm not sure if there is
any point in trying (maybe 210.5 is an absolute best) and which method
would be best to search for it. Also i don't know if such a thing
doesn't already exist. If not maybe i'm going to give it a try.

btw: thanks at everyone for your ideas!

Eric <n@m.com> wrote:

> Creating an optimum conversion from 0..255 lists to the data blocks
> sounds like a cool AI project to implement. That's kind of like,
> looking for the fastest way to unsort it. But i'm not sure if there is
> any point in trying (maybe 210.5 is an absolute best) and which method
> would be best to search for it. Also i don't know if such a thing
> doesn't already exist. If not maybe i'm going to give it a try.

If all the orderings are equally likely, then 210.5 *is* the absolute
best you can do -- it doesn't matter how you look at the problem:  as
"unsorting" or straight coding or whatever.  No matter what, you won't
ever do better than 210.5 bytes on average....

-- 

That's News To Me!
newstome@comcast.net

"Willem" <willem@stack.nl> wrote in message
news:slrnceghtk.1vmu.willem@toad.stack.nl...
> cr88192 wrote:
> )> Exactly.  In the case of 'any order', arithmetic encoding will approach
> ) the
> )> theoretical limit.  (The theoretical limit is log256(256!) = 210.5
bytes.)
> )>
> ) I would guess though that within this situation (only one occurance of a
> ) certain value), the traditional theoretical limit does not apply, and
some
> ) lesser value exists (for which I am unsure).
>
> I already accounted for the single occurrance of a certain value in my
> calculation of the theoretical limit.  What part of log256(256!) did you
> not understand ?
>
it was because I didn't really accept it.

initially I thought you meant "with all possible algortihms", not "all
possible permutations".
now I am thinking "the difference is not that important".

this is likely the densest possible encoding. the only possible increase I
would think would be to try to eliminate some branches in some cases, but
this itself would likely be problematic.

maybe one could try using different permutation algoritms, choosing the
smallest one which still holds for the given data (eg: so simple patterns
would be smaller).

I am stupid, I don't really have much grasp on the theory (or math for that
matter).

> ) I am expecting that it will not be that difficult to break this limit
for
> ) this kind of data...
>
> You expect wrongly.
>
and it seems I did.

> )> Side note: An approach where you (virtually) define a list of all
possible
> )> permutations, and then can quickly determine at what position in the
list
> )> any given permutation would be would get you the theoretical limit.
> )> (You would also have to be able to generate the Nth permutation.)
> )>
> ) yes. I still figure that this would be a bit smaller than 211 bytes
though
> ) (this is not an arbitrary bytestream either...).
>
> It would be 210.5 bytes, exactly, because this scheme rounds up to the
> nearest whole amount of bits.  There are 256! possible permutations.
> This means that the generated number would fall between 0 and 256!,
meaning
> you need log2(256!) bits to represent the number minimally.
>
yes.

> ) ...
> ) in my case, I can't really imagine how this would be generally useful,
so it
> ) doesn't really justify experimentation imo.
>
> The fact that with arithmetic encoding you can easily approach the
> theoretical limit, which actually *is* the theoretical limit for this kind
> of data, because I *did* account for everything known about the data,
means
> that experimentation with harebrained schemes in useless.
>
grr, I trust experimentation, even if it proves me wrong...

> Fact of life (well, of compression at least): if you can model the
> probabilities accurately, arithmetic encoding approaches the theoretical
> limit, and you can not do better.
>
> In case of 'each value occurs once', the probability of a symbol is either
> 1/N or 0, depending on if the symbol has already been seen.
>
> An ideal arithcoder would need log2(256) + log2(255) + ... + log2(1) bits.
> I think you'll find that this equates to 1684.0 bits.
>
yes.
I agree now.

I wrote an encoder for a different algo, and found that the change was
minimal (the statistical distribution of values was a little better, but not
signifigantly...).

the 'encoded' data compresses a little better (eg: I passed it to gzip). 256
blocks of randomized sequences (64kB), encoded will compress to about 60kB,
unencoded will compress to slightly larger than the input.

bzip2 did worse...


grr, I dislike these kind of constraints, eg: some kind of invisible wall
that makes certain things impossible...
I guess this kind of thing exists in lots of places, but I didn't think it
would be *that* easy to predict.

"Eric" <n@m.com> wrote in message
news:2ehge0p4dvo76civqlj7ug2dj6iotf229h@4ax.com...
> On Mon, 5 Jul 2004 01:49:14 +1000, "cr88192"
> <cr88192@protect.hotmail.com> wrote:
>
> --8<--
>
> >> But maybe there are better methods and someone can point me in the
> >> right direction.
> >>
> >> Any help would be much appreciated!
> >>
> >I would guess trying to figure out a way to compress the "order" of the
> >values might help.
> >
> >eg, as an overly simplistic example:
> >assuming that the values start of as an even-height binary tree with the
> >leaves as the values 0-255, and at each point in the tree the valuespace
can
>
> --8<--
>
> >maybe bubblesort could be modified into a compressor (reversing the sort
> >would lead to the input, though I am doubtful of the effectiveness).
> >
> >the problem is "any order" does not make it seem like this kind of
approach
> >could offer that much, relying on something like this would probably be
> >better for "patterns"...
>
> Creating an optimum conversion from 0..255 lists to the data blocks
> sounds like a cool AI project to implement. That's kind of like,
> looking for the fastest way to unsort it. But i'm not sure if there is
> any point in trying (maybe 210.5 is an absolute best) and which method
> would be best to search for it. Also i don't know if such a thing
> doesn't already exist. If not maybe i'm going to give it a try.
>
> btw: thanks at everyone for your ideas!
>

I am feeling stupid...
I tried fiddling with a different algo (modifying positional insert into a
kind of compressor), with less than awe-inspiring results...

I am thinking now maybe 210.5 is the best...

hi !

cr88192 wrote:
> I wrote an encoder for a different algo, and found that the change was
> minimal (the statistical distribution of values was a little better, but not
> signifigantly...).
> 
> the 'encoded' data compresses a little better (eg: I passed it to gzip). 256
> blocks of randomized sequences (64kB), encoded will compress to about 60kB,
> unencoded will compress to slightly larger than the input.
> 
> bzip2 did worse...
> 
> 
> grr, I dislike these kind of constraints, eg: some kind of invisible wall
> that makes certain things impossible...
> I guess this kind of thing exists in lots of places, but I didn't think it
> would be *that* easy to predict.

a pen and paper, plus some basic maths are enough
to see where the catch is. Well, at least, that's what
helped me in y2001 when i did some investigations in
that field.

I have tried to deal with "256!" permutations
and did not use arithmetic encoding but
plain old divides and multiplies over 1681 bit-wide
integers. That's quite heavy and troublesome.

Maybe arithcodes do almost as well with less troubles
with large-precision integers. but still it's quite heavy
in my understanding.

Now, this thread has triggered an idea that i could implement
in a few hours if i had time. It is almost as good as arithcodes
but uses an "integer" number of bits per encoded nmber.

If anyone is interested, let me know (by personal email
for faster answer) and i'll post the source code here.
It uses algorithmics from a compression algo that i am
developping now, in a special combination of
"range reduction" and "phasing-in coding".

Given random data, the resulting bitstream should
be around the log2(256!) limit, but extreme cases
(permutations like 255, 254, 253, 252, 251 ....
and 0,1,2,3,4,5,6,7,8...) probably add or remove around 200 bits
(1/8 of the total size).

But i guess it's more interesting in steg
than in compression.

YG

YG wrote:
> If anyone is interested, let me know (by personal email
> for faster answer) and i'll post the source code here.
> It uses algorithmics from a compression algo that i am
> developping now, in a special combination of
> "range reduction" and "phasing-in coding".

silly me.

range reduction is not even needed,
only phasing-in codes.

how simple.

YG

"YG" <whygee@f-cpu.org> wrote in message
news:40e9f411$0$308$7a628cd7@news.club-internet.fr...
> hi !
>
> cr88192 wrote:
> > I wrote an encoder for a different algo, and found that the change was
> > minimal (the statistical distribution of values was a little better, but
not
> > signifigantly...).
> >
> > the 'encoded' data compresses a little better (eg: I passed it to gzip).
256
> > blocks of randomized sequences (64kB), encoded will compress to about
60kB,
> > unencoded will compress to slightly larger than the input.
> >
> > bzip2 did worse...
> >
> >
> > grr, I dislike these kind of constraints, eg: some kind of invisible
wall
> > that makes certain things impossible...
> > I guess this kind of thing exists in lots of places, but I didn't think
it
> > would be *that* easy to predict.
>
> a pen and paper, plus some basic maths are enough
> to see where the catch is. Well, at least, that's what
> helped me in y2001 when i did some investigations in
> that field.
>
ok.
I am not used to using maths, or pen and paper. usually I run into something
with some vague idea of what I am doing and seeing if anything interesting
comes out.
of course, I typically don't really do anything compression (or math)
related, and when I do it is usually a "oh crap, wtf is this" and later "ok,
I it understand now" type situation (eg: this occured not too long ago when
I ran into the subject of quaternions...).

> I have tried to deal with "256!" permutations
> and did not use arithmetic encoding but
> plain old divides and multiplies over 1681 bit-wide
> integers. That's quite heavy and troublesome.
>
hmm, this problem has general uses?... (otherwise why would it have shown up
before?).

> Maybe arithcodes do almost as well with less troubles
> with large-precision integers. but still it's quite heavy
> in my understanding.
>
ok.

> Now, this thread has triggered an idea that i could implement
> in a few hours if i had time. It is almost as good as arithcodes
> but uses an "integer" number of bits per encoded nmber.
>
ok.

> If anyone is interested, let me know (by personal email
> for faster answer) and i'll post the source code here.
> It uses algorithmics from a compression algo that i am
> developping now, in a special combination of
> "range reduction" and "phasing-in coding".
>
> Given random data, the resulting bitstream should
> be around the log2(256!) limit, but extreme cases
> (permutations like 255, 254, 253, 252, 251 ....
> and 0,1,2,3,4,5,6,7,8...) probably add or remove around 200 bits
> (1/8 of the total size).
>
> But i guess it's more interesting in steg
> than in compression.
>
dunno...

I have just been hanging around this group recently, realizing that, sadly,
I don't really understand this kind of stuff very well...
at least I am fammiliarizing myself with some new stuff (different algo's,
rules, ...).

Hello, cr88192!
You wrote:

> 
> "Willem" <willem@stack.nl> wrote in message
> news:slrnceghtk.1vmu.willem@toad.stack.nl...
> > cr88192 wrote:
> > )> Exactly.  In the case of 'any order', arithmetic encoding
will approach
> > ) the
> > )> theoretical limit.  (The theoretical limit is log256(256!)
= 210.5
> bytes.)
> > )>
> > ) I would guess though that within this situation (only one
occurance of a
> > ) certain value), the traditional theoretical limit does not
apply, and
> some
> > ) lesser value exists (for which I am unsure).
> >
> > I already accounted for the single occurrance of a certain
value in my
> > calculation of the theoretical limit.  What part of
log256(256!) did you
> > not understand ?
> >
> it was because I didn't really accept it.
> 
> initially I thought you meant "with all possible algortihms",
not "all
> possible permutations".
> now I am thinking "the difference is not that important".
> 
> this is likely the densest possible encoding. the only possible
increase I
> would think would be to try to eliminate some branches in some
cases, but
> this itself would likely be problematic.
> 
> maybe one could try using different permutation algoritms,
choosing the
> smallest one which still holds for the given data (eg: so
simple patterns
> would be smaller).

The question you have to ask is why you would make simpler
patterns more likely and what would that buy you? Under the
assumption that every on of the 256! permutations is equally
likely it would actually increase the average encoded length.

The only reason you would consider it is if the assumption that
each permutation was equally likely were not really true and we
expect permutations with simple patterns to be more likely. The
210.5 bit limit only applies to the assumption that all
permutations are equally likely. If the probabilities are skewed
you can do better than that.

Consider an example with only four messages A, B, C, & D. If all
are equally likely (the probability of each is 1/4) then the best
we can do is 2 bits for each.

What if we made one of them 1bit? Then we end up having to use 2
bits for another and 3 bits for the remaining two. That ends up
being an average of 4.5 bits  per.

But let's say we know that the probabilities are instead 1/2,
1/4, and 1/8 for the remaining two then the encoding I described
using 1, 2, or 3 bits is optimal. The average is not 4.5 in that
case becaus you have to weight the average acording to the
probabilities. We expect to use 1 bit 1/2 the time, 2 bits 1/4 of
the time, and 3 bits 1/4 of the time (1/8 + 1/8). That is an
averag of 1.75 bits.

So you will not improv on the 210.5 bits by trying different
algotihms. The only way to improve on it is to refine your
probability model.
-- 
 Dale King
 My Blog: http://daleking.homedns.org/Blog

"Dale King" <DaleKing@newsrvr.tce.com> wrote in message
news:BD116528yf@newsrvr.tce.com...
> Hello, cr88192!
> You wrote:
>
> >
> > "Willem" <willem@stack.nl> wrote in message
> > news:slrnceghtk.1vmu.willem@toad.stack.nl...
> > > cr88192 wrote:
> > > )> Exactly.  In the case of 'any order', arithmetic encoding
> will approach
> > > ) the
> > > )> theoretical limit.  (The theoretical limit is log256(256!)
> = 210.5
> > bytes.)
> > > )>
> > > ) I would guess though that within this situation (only one
> occurance of a
> > > ) certain value), the traditional theoretical limit does not
> apply, and
> > some
> > > ) lesser value exists (for which I am unsure).
> > >
> > > I already accounted for the single occurrance of a certain
> value in my
> > > calculation of the theoretical limit.  What part of
> log256(256!) did you
> > > not understand ?
> > >
> > it was because I didn't really accept it.
> >
> > initially I thought you meant "with all possible algortihms",
> not "all
> > possible permutations".
> > now I am thinking "the difference is not that important".
> >
> > this is likely the densest possible encoding. the only possible
> increase I
> > would think would be to try to eliminate some branches in some
> cases, but
> > this itself would likely be problematic.
> >
> > maybe one could try using different permutation algoritms,
> choosing the
> > smallest one which still holds for the given data (eg: so
> simple patterns
> > would be smaller).
>
> The question you have to ask is why you would make simpler
> patterns more likely and what would that buy you? Under the
> assumption that every on of the 256! permutations is equally
> likely it would actually increase the average encoded length.
>
maybe, however, it depends a little on how the model is selected.
assuming 1 byte is used to select among a number of algos, then the cost is
probably about 1/211.

of course, as noted, this is not likely to save much of anything in the
general case...

> The only reason you would consider it is if the assumption that
> each permutation was equally likely were not really true and we
> expect permutations with simple patterns to be more likely. The
> 210.5 bit limit only applies to the assumption that all
> permutations are equally likely. If the probabilities are skewed
> you can do better than that.
>
> Consider an example with only four messages A, B, C, & D. If all
> are equally likely (the probability of each is 1/4) then the best
> we can do is 2 bits for each.
>
> What if we made one of them 1bit? Then we end up having to use 2
> bits for another and 3 bits for the remaining two. That ends up
> being an average of 4.5 bits  per.
>
> But let's say we know that the probabilities are instead 1/2,
> 1/4, and 1/8 for the remaining two then the encoding I described
> using 1, 2, or 3 bits is optimal. The average is not 4.5 in that
> case becaus you have to weight the average acording to the
> probabilities. We expect to use 1 bit 1/2 the time, 2 bits 1/4 of
> the time, and 3 bits 1/4 of the time (1/8 + 1/8). That is an
> averag of 1.75 bits.
>
> So you will not improv on the 210.5 bits by trying different
> algotihms. The only way to improve on it is to refine your
> probability model.

ok, makes sense...

just my mind tends not to fully accept the idea of "entropy", and keeps
trying to assume that more simplistic and repetitive patterns would be more
common than more arbitrary ones...

afaik the cost was 210.5 bytes though...

Hello, cr88192!
You wrote:

> 
> "Dale King" <DaleKing@newsrvr.tce.com> wrote in message
> news:BD116528yf@newsrvr.tce.com...
> > Hello, cr88192!
> > You wrote:
> >
> > >
> > > "Willem" <willem@stack.nl> wrote in message
> > > news:slrnceghtk.1vmu.willem@toad.stack.nl...
> > > > cr88192 wrote:
> > > > )> Exactly.  In the case of 'any order', arithmetic
encoding
> > will approach
> > > > ) the
> > > > )> theoretical limit.  (The theoretical limit is
log256(256!)
> > = 210.5
> > > bytes.)
> > > > )>
> > > > ) I would guess though that within this situation (only
one
> > occurance of a
> > > > ) certain value), the traditional theoretical limit does
not
> > apply, and
> > > some
> > > > ) lesser value exists (for which I am unsure).
> > > >
> > > > I already accounted for the single occurrance of a
certain
> > value in my
> > > > calculation of the theoretical limit.  What part of
> > log256(256!) did you
> > > > not understand ?
> > > >
> > > it was because I didn't really accept it.
> > >
> > > initially I thought you meant "with all possible
algortihms",
> > not "all
> > > possible permutations".
> > > now I am thinking "the difference is not that important".
> > >
> > > this is likely the densest possible encoding. the only
possible
> > increase I
> > > would think would be to try to eliminate some branches in
some
> > cases, but
> > > this itself would likely be problematic.
> > >
> > > maybe one could try using different permutation algoritms,
> > choosing the
> > > smallest one which still holds for the given data (eg: so
> > simple patterns
> > > would be smaller).
> >
> > The question you have to ask is why you would make simpler
> > patterns more likely and what would that buy you? Under the
> > assumption that every on of the 256! permutations is equally
> > likely it would actually increase the average encoded length.
> >
> maybe, however, it depends a little on how the model is
selected.
> assuming 1 byte is used to select among a number of algos, then
the cost is
> probably about 1/211.

No it doesn't depend. The optimal encoding for a message with
probability p is -log p where the base of the log is given by the
size of the output alphabet (2 for output in bits).

If all outputs are equally likely then they each have a
probability of 1/256! so the optimal encoding in bits is
-log2(1/256!) = log2 256!

> of course, as noted, this is not likely to save much of
anything in the
> general case...

It is guaranteed to make things worse if all permutations are
equally likely

> > The only reason you would consider it is if the assumption
that
> > each permutation was equally likely were not really true and
we
> > expect permutations with simple patterns to be more likely.
The
> > 210.5 bit limit only applies to the assumption that all
> > permutations are equally likely. If the probabilities are
skewed
> > you can do better than that.
> >
> > Consider an example with only four messages A, B, C, & D. If
all
> > are equally likely (the probability of each is 1/4) then the
best
> > we can do is 2 bits for each.
> >
> > What if we made one of them 1bit? Then we end up having to
use 2
> > bits for another and 3 bits for the remaining two. That ends
up
> > being an average of 4.5 bits  per.
> >
> > But let's say we know that the probabilities are instead 1/2,
> > 1/4, and 1/8 for the remaining two then the encoding I
described
> > using 1, 2, or 3 bits is optimal. The average is not 4.5 in
that
> > case becaus you have to weight the average acording to the
> > probabilities. We expect to use 1 bit 1/2 the time, 2 bits
1/4 of
> > the time, and 3 bits 1/4 of the time (1/8 + 1/8). That is an
> > averag of 1.75 bits.
> >
> > So you will not improv on the 210.5 bits by trying different
> > algotihms. The only way to improve on it is to refine your
> > probability model.
> 
> ok, makes sense...
> 
> just my mind tends not to fully accept the idea of "entropy",
and keeps
> trying to assume that more simplistic and repetitive patterns
would be more
> common than more arbitrary ones...

And there is actually mathematical reasoning that says that is
more likely. The point was that instead of making assumptions you
would be better-off trying to characterize what the data is
really like
-- 
 Dale King
 My Blog: http://daleking.homedns.org/Blog

"Dale King" <DaleKing@newsrvr.tce.com> wrote in message
news:BD18D1C1yf@newsrvr.tce.com...
> Hello, cr88192!
> You wrote:
>
> >
> > "Dale King" <DaleKing@newsrvr.tce.com> wrote in message
> > news:BD116528yf@newsrvr.tce.com...
> > > Hello, cr88192!
> > > You wrote:
> > >
> > > >
> > > > "Willem" <willem@stack.nl> wrote in message
> > > > news:slrnceghtk.1vmu.willem@toad.stack.nl...
> > > > > cr88192 wrote:
> > > > > )> Exactly.  In the case of 'any order', arithmetic
> encoding
> > > will approach
> > > > > ) the
> > > > > )> theoretical limit.  (The theoretical limit is
> log256(256!)
> > > = 210.5
> > > > bytes.)
> > > > > )>
> > > > > ) I would guess though that within this situation (only
> one
> > > occurance of a
> > > > > ) certain value), the traditional theoretical limit does
> not
> > > apply, and
> > > > some
> > > > > ) lesser value exists (for which I am unsure).
> > > > >
> > > > > I already accounted for the single occurrance of a
> certain
> > > value in my
> > > > > calculation of the theoretical limit.  What part of
> > > log256(256!) did you
> > > > > not understand ?
> > > > >
> > > > it was because I didn't really accept it.
> > > >
> > > > initially I thought you meant "with all possible
> algortihms",
> > > not "all
> > > > possible permutations".
> > > > now I am thinking "the difference is not that important".
> > > >
> > > > this is likely the densest possible encoding. the only
> possible
> > > increase I
> > > > would think would be to try to eliminate some branches in
> some
> > > cases, but
> > > > this itself would likely be problematic.
> > > >
> > > > maybe one could try using different permutation algoritms,
> > > choosing the
> > > > smallest one which still holds for the given data (eg: so
> > > simple patterns
> > > > would be smaller).
> > >
> > > The question you have to ask is why you would make simpler
> > > patterns more likely and what would that buy you? Under the
> > > assumption that every on of the 256! permutations is equally
> > > likely it would actually increase the average encoded length.
> > >
> > maybe, however, it depends a little on how the model is
> selected.
> > assuming 1 byte is used to select among a number of algos, then
> the cost is
> > probably about 1/211.
>
> No it doesn't depend. The optimal encoding for a message with
> probability p is -log p where the base of the log is given by the
> size of the output alphabet (2 for output in bits).
>
> If all outputs are equally likely then they each have a
> probability of 1/256! so the optimal encoding in bits is
> -log2(1/256!) = log2 256!
>
yes, this would be a worst (and most likely) case.
however, if things are changed such that simpler permutations are possible
(and indicated, eg, with a prefix byte), and if those simpler patterns are
made to be much more likely (eg: lots of predictable sequences, etc...).
then there might be a savings, eg, because patterns like 0..255 ascending
get represented as a single byte...

> > of course, as noted, this is not likely to save much of
> anything in the
> > general case...
>
> It is guaranteed to make things worse if all permutations are
> equally likely
>
yes.

> > > The only reason you would consider it is if the assumption
> that
> > > each permutation was equally likely were not really true and
> we
> > > expect permutations with simple patterns to be more likely.
> The
> > > 210.5 bit limit only applies to the assumption that all
> > > permutations are equally likely. If the probabilities are
> skewed
> > > you can do better than that.
> > >
> > > Consider an example with only four messages A, B, C, & D. If
> all
> > > are equally likely (the probability of each is 1/4) then the
> best
> > > we can do is 2 bits for each.
> > >
> > > What if we made one of them 1bit? Then we end up having to
> use 2
> > > bits for another and 3 bits for the remaining two. That ends
> up
> > > being an average of 4.5 bits  per.
> > >
> > > But let's say we know that the probabilities are instead 1/2,
> > > 1/4, and 1/8 for the remaining two then the encoding I
> described
> > > using 1, 2, or 3 bits is optimal. The average is not 4.5 in
> that
> > > case becaus you have to weight the average acording to the
> > > probabilities. We expect to use 1 bit 1/2 the time, 2 bits
> 1/4 of
> > > the time, and 3 bits 1/4 of the time (1/8 + 1/8). That is an
> > > averag of 1.75 bits.
> > >
> > > So you will not improv on the 210.5 bits by trying different
> > > algotihms. The only way to improve on it is to refine your
> > > probability model.
> >
> > ok, makes sense...
> >
> > just my mind tends not to fully accept the idea of "entropy",
> and keeps
> > trying to assume that more simplistic and repetitive patterns
> would be more
> > common than more arbitrary ones...
>
> And there is actually mathematical reasoning that says that is
> more likely. The point was that instead of making assumptions you
> would be better-off trying to characterize what the data is
> really like

however, I live in a world of assumptions and approximations (much of
software...).
something that works better "as a rule of thumb" is considered better than
something that works better "in all cases".

one tries to make he common cases faster/easier/... at the cost of
everything else. take c style-syntax for example, in general many syntactic
constructs are quite awkward, but there is just such nifty syntax and
semantics for pointers (vs. many other languages, where if the have pointers
at all then using them was made quite awkward...), or something (ok, this
was pointless...).