Re: Still on the Arithmetic coder


David A. Scott wrote:
> "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.

Oh, I didn't looked at his example carefully enough, thanks for
pointing that out. His 0.25 result was based on his probablity
distribution assumptions (and flawed rounding trick). This ofcourse
varies depending upon file and model.

IMHO, his other comments were all fine and general, or did I missed
something there too?

Sachin Garg

.

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. ... For the file where A is .5 there is zero error the huffman ... My Compression code http://bijective.dogma.net/ ...
    (comp.compression)
  • Re: Jarek Dudas Asymmetric binary system
    ... It's because both arithmetic coding and ABS approximate the wanted ... To encode bit d (0 or 1, choosing 1 with probability p), I first write ... p -> q (table lookup) ...
    (comp.compression)
  • Re: how to find the best ADC step size?
    ... > symbol doesn't change the probability of the symbol occurring. ... The Huffman problem and the quantization problem are related in they both ... theoretical answer is the entropy, but the practical answer (comes from ...
    (sci.math)