<div dir="ltr">Good point.<div>If what is required is an entropy coder which adapts its model (i.e. its probability estimations) on the fly, per symbol,</div><div style>then my first choice would be a Binary Arithmetic Coder. It's really best in class for that.</div>
<div style><br></div><div style>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.</div><div style><br></div><div style>
One point is : BAC only delivers 0/1 results.</div><div style>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.</div>
<div style><br></div><div style><br></div><div style>BAC also typically requires a multiplication (but no division). Apparently your version doesn't, so I'll definitely look into it.</div><div style><br></div><div style>
<br></div><div style>Regards</div><div style><br></div></div><div class="gmail_extra"><br><br><div class="gmail_quote">2013/12/29 Timothy B. Terriberry <span dir="ltr"><<a href="mailto:tterribe@xiph.org" target="_blank">tterribe@xiph.org</a>></span><br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">I got to here:<br>
<br>
"The advantage of Huffman is that we can adaptively modify the tree on<br>
the run, but we could also do it in ANS - switch some appearances<br>
between symbols and renumerate the following ones ... but it would be<br>
costly for a large table."<br>
<br>
...and stopped. That's probably going to be a deal-breaker. The whole<br>
point of arithmetic coding is the flexibility in the modeling (which<br>
puts adaptive Huffman to shame), and we rely on this extensively. For<br>
the record, the entropy coder in Daala does not require multiplications<br>
or divisions, nor large tables. I encourage you to check it out.<br>
_______________________________________________<br>
daala mailing list<br>
<a href="mailto:daala@xiph.org">daala@xiph.org</a><br>
<a href="http://lists.xiph.org/mailman/listinfo/daala" target="_blank">http://lists.xiph.org/mailman/listinfo/daala</a><br>
</blockquote></div><br></div>