Re: Still on the Arithmetic coder

"Sachin Garg" <schngrg@xxxxxxxxx> wrote in
news:1138618596.947241.174160@xxxxxxxxxxxxxxxxxxxxxxxxxxxx:

>> I assume the right probability for the symbol is known ... then
>> arithmetic coding would just produce the right amount of bits.
>> Huffman would produce full bits and in an optimal case this could
>> be the rounded number of bits ...

Are you sure its just the rounded number of bits. What rules
of rounding are we using here.

>
> Agreed on this too.
>
> Sachin Garg [India]
> http://www.sachingarg.com
>
> ps. Discussions are so boring without disagreements :-)
>

Then lets make a case to disagre on. Lets go the two symbols
case. That way the huffman produce 'ONE BIT" a 0 and 1 each exactly
1 bit in lenght. We have several files in each case the symbols have
fixed probability put symbol A varies uniformily between files from
0 to 1. For the file where A is .5 there is zero error the huffman
and arithmetic are the same at A .25 the A is 2 bits while the other
B is ,42 bit rounded up so here the error is already 1 for the A and
,58 for the B. Once we go to A ,75 and B ,25 the error again is the
same and that half the time A is .25 or less or .75 or more so and it
only gets worse when A is less than ,25 Example when A is .1 the length
is over 3 bits for A and rouglhy ,15 bits for B so respective error for
A over 2 full bits and roughly .85 bits for the B so clearly the average
error is larger then .25 bits per symbol in the case.

Of course this is not the only way to view this. Take a file of 999
A's and 1 B the compressed would be 1000 for huffman and the sum of
1.442 for the A's and 9.967 for the B take (1000 - ( 1,442 + 9,967))/1000
and you get by this method .989 bits of error based on length of compressed
data so assuming max errors .5 per symbol is not true the rounding is
not true.




David A. Scott
--
My Crypto code
http://bijective.dogma.net/crypto/scott19u.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"

.

Relevant Pages

  • Re: Jarek Dudas Asymmetric binary system
    ... Huffman coding due to the patent situation. ... encoding and arithmetic coding, ... the key patents in the field. ... encoder which is optimal for probability distribution q, ...
    (comp.compression)
  • Re: Jarek Dudas Asymmetric binary system
    ... It's from wikipedia for 'arithmetic coding' ... Huffman coding due to the patent situation. ... encoding option, due to patent concerns; the result is that nearly all ... While encoding symbols of given probability distribution, ...
    (comp.compression)
  • Re: Still on the Arithmetic coder
    ... >>> I assume the right probability for the symbol is known ... ... >>> arithmetic coding would just produce the right amount of bits. ... >>> Huffman would produce full bits and in an optimal case this could ... > of rounding are we using here. ...
    (comp.compression)
  • Next set of vetting
    ... Harrington's Compression Method, ... The First Fundamental is the Huffman. ... Pascals triangle has applications in many many different fields. ... possible outcomes of that many bits, ...
    (comp.compression)
  • Re: Next set of vetting
    ... design a model for a data source that fits to that. ... In typical compression the usage ... You forget here that the input of the huffman must be "out of balance" ... you will find that the result is in balance. ...
    (comp.compression)