[daala] New generation entropy coder

Yann Collet yann.collet.73 at gmail.com
Sun Dec 29 11:27:35 PST 2013

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.


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 

More information about the daala mailing list