[daala] New generation entropy coder
yann.collet.73 at gmail.com
Sun Dec 29 11:27:35 PST 2013
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
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the daala