Where can I get an understanding of how Arithmetic Coding and Huffman Encoding compare as entropy increases. I know Arithmetic Coding is better for low entropy distributions, but how can I get a sense of HOW the two scale as you increase entropy? Is this a silly question because I'm missing some piece of the puzzle?
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
They're not really comparable as Huffman coding assumes a fixed alphabet and arithmetic coding can use arbitrarily complex probabilistic models of the data (maybe even non-causal, I'm not sure). Anyway it's not a research-level question. You could read a book on data compression, e.g. Bell, Cleary and Witten, "Text Compression" is elementary and readable, though maybe a little bit old by now.
$\begingroup$
$\endgroup$
Huffman out bits for each symbol, like 0101 then 1100 = 01011100 and so on. Arithmetic coder computes numbers on each step and add them with shift, like 0101 + 001100 = 1000000. So each step in arithmetic coding is to compute integer, to compute shift and add. This shift and provide compression to a fraction of bit. The details are here http://ezcodesample.com/reanatomy.html
