<p>This is my (somewhat unorthodox) answer to the comparison between Huffman. Huffman and arithmetic codings. A Huffman code is only optimal if the frequency of the letters in the input alphabet are $2^{-k}$, for an integer $k$. Otherwise, there are internal nodes in the coding tree whose children have different weights. As a result, the output bit stream does not have an entropy of 1 bin/output bit. </p>

<p>One <i>solution</i> is to combine the input letters into groups and enlarge the alphabet. For example, instead of coding a byte stream (as is usually done), you can combine two bytes into a word and use a larger coding tree for the combined alphabet. The problem is that the size of the tree (e.g. instead of $2^8$ entries, now you have to deal with $2^{16}$ entries). And this is just the beginning. </p>

<p>One may view the arithmetic coding as taking this idea to the extreme. Instead of combining two input letters, here we combine all of them. Of course, now the coding tree is huge and cannot be explicitly built. The details of arithmetic coding deals with generating and traversing a virtual Huffman tree for this combined alphabet. </p>

CC BY-SA 3.0
2013-07-14T14:03:38.173Z
2013-07-14T14:03:38.173Z
siravan
<p>A Hufman code associates an "integer" number of bits to each message:
on some distributions this can sum up to a linear cost in the number of messages being sent (hence the $1$ in the $n(1+H)$ upper bound for the size of the sequence of bits produced.</p>

<p>My understanding is that arithmetic codes overcome this weakness, at the cost of a more complex algorithm to compute the codes, and encoding tables  (disclaimer: I am rusty on this, anyone should feel free to correct or complete), reaching $nH+O(1)$.</p>

<p>The difference between $n(1+H)$ and $nH+O(1)$ is more sensible for $H$ small of course, so arithmetical codes are prefered for low entropy distribution, if there are no constaints on the cost of encoding/decoding.</p>

CC BY-SA 3.0
2013-07-15T10:52:09.783Z
I think you mean "symbols" or "letters" and not "messages".
Peter Shor 
CC BY-SA 3.0
2013-07-15T12:30:14.213Z
@PeterShor No, I really did mean "messages", as in the orginal paper from Huffman in 1952. Prefix free codes have many other usages than compressing sequences of symbols or letters!!! :)  (e.g. http://arxiv.org/abs/0902.1038)
J.y B.y
CC BY-SA 3.0
2013-07-13T14:04:55.433Z
2013-07-13T14:04:55.433Z
J.y B.y
<p>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?</p>

<it.information-theory><coding-theory>
Comparison Huffman Encoding and Arithmetic Coding dependent on Entropy
RIshi Sharma
# Comparison Huffman Encoding and Arithmetic Coding dependent on Entropy

(Asked by: username_0 on 2013-07-13)

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?

**Tags:** it.information-theory, coding-theory

---

## 2 answers

### Answer by username_1 on 2013-07-14. Score: 4

This is my (somewhat unorthodox) answer to the comparison between Huffman. Huffman and arithmetic codings. A Huffman code is only optimal if the frequency of the letters in the input alphabet are $2^{-k}$, for an integer $k$. Otherwise, there are internal nodes in the coding tree whose children have different weights. As a result, the output bit stream does not have an entropy of 1 bin/output bit.

One *solution* is to combine the input letters into groups and enlarge the alphabet. For example, instead of coding a byte stream (as is usually done), you can combine two bytes into a word and use a larger coding tree for the combined alphabet. The problem is that the size of the tree (e.g. instead of $2^8$ entries, now you have to deal with $2^{16}$ entries). And this is just the beginning.

One may view the arithmetic coding as taking this idea to the extreme. Instead of combining two input letters, here we combine all of them. Of course, now the coding tree is huge and cannot be explicitly built. The details of arithmetic coding deals with generating and traversing a virtual Huffman tree for this combined alphabet.


---

### Answer by username_2 on 2013-07-13. Score: 2

A Hufman code associates an "integer" number of bits to each message:
on some distributions this can sum up to a linear cost in the number of messages being sent (hence the $1$ in the $n(1+H)$ upper bound for the size of the sequence of bits produced.

My understanding is that arithmetic codes overcome this weakness, at the cost of a more complex algorithm to compute the codes, and encoding tables (disclaimer: I am rusty on this, anyone should feel free to correct or complete), reaching $nH+O(1)$.

The difference between $n(1+H)$ and $nH+O(1)$ is more sensible for $H$ small of course, so arithmetical codes are prefered for low entropy distribution, if there are no constaints on the cost of encoding/decoding.

> **Comments:**
> **username_3**: I think you mean "symbols" or "letters" and not "messages".  
> **username_2**: @PeterShor No, I really did mean "messages", as in the orginal paper from Huffman in 1952. Prefix free codes have many other usages than compressing sequences of symbols or letters!!! :)  (e.g. http://arxiv.org/abs/0902.1038)  

---

