[daala] New generation entropy coder

[Yann Collet]

Good point.
If what is required is an entropy coder which adapts its model (i.e. its
probability estimations) on the fly, per symbol,
then my first choice would be a Binary Arithmetic Coder. It's really best
in class for that.

Huffman, FSE and even full-symbol Range Coder tend to be used in
block-mode, that is, with a header (or a rule) describing the probabilities
within the block.

One point is : BAC only delivers 0/1 results.
Sure, it's enough to emulate larger number of symbols, either sequentially,
or with a binary search. But that's nonetheless several loops to deliver a
single symbol. This mechanically translates into slower speed.


BAC also typically requires a multiplication (but no division). Apparently
your version doesn't, so I'll definitely look into it.


Regards



2013/12/29 Timothy B. Terriberry <tterribe at xiph.org>

> I got to here:
>
> "The advantage of Huffman is that we can adaptively modify the tree on
> the run, but we could also do it in ANS - switch some appearances
> between symbols and renumerate the following ones ... but it would be
> costly for a large table."
>
> ...and stopped. That's probably going to be a deal-breaker. The whole
> point of arithmetic coding is the flexibility in the modeling (which
> puts adaptive Huffman to shame), and we rely on this extensively. For
> the record, the entropy coder in Daala does not require multiplications
> or divisions, nor large tables. I encourage you to check it out.
> _______________________________________________
> daala mailing list
> daala at xiph.org
> http://lists.xiph.org/mailman/listinfo/daala
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.xiph.org/pipermail/daala/attachments/20131229/ac8be997/attachment.htm