Consider the alphabet $\mathcal{A}=\{a_0,a_1,a_2,a_3\}$ with the the following corresponding probabilities:

  1. $\, p_{A,1}=\{0.5,0.3,0.15,0.05\}$
  2. $\, p_{A,2}=\{0.5,0.25,0.125,0.125\}$

The entropy for the first case is $H(A,1)= 1.65$, and for the second is $H(A,2)=1.75$. The Huffman code for both can be $\{0, 10, 110, 111 \}$ or $\{1, 01, 001, 000 \}$. The average lengths are $\bar{L_{A,1}}=1.7$ and $\bar{L_{A,2}}=1.75$. The efficiencies are $97.14 \%$ and $100 \%$ for case $1$ and $2$ respectively. Why is that? The only reasonable explanation is the probabilities themselves. In the second case, it is somehow equally divided. Can anyone explain?

  • $\begingroup$ "The efficiencies are $97.14%$ and $100%$ for case $1$ and $2$ respectively." Ahem. Shorter means more efficient. And, well, the formula for average length itself is a clue: if all probabilties are equal, you have the worst case. When one symbol encoded by a single bit becomes dominating, we are moving towards the best case. $\endgroup$
    – rus9384
    Sep 29 '18 at 0:08
  • $\begingroup$ @rus9384 I understand that equal probabilities result in worst case scenario, and one dominating symbol result in the best case. However, neither of these is the case here. Both case one and two have symbol $a_0$ as the most dominant with probability $0.5$, and then the rest of the symbols have different probabilities. I don't see why would the second case have an efficiency of $100\%$. $\endgroup$
    – Lod
    Sep 29 '18 at 0:25

First off, though the codes you gave are what the Huffman coding process produces, they aren't the only possible prefix codes for those two cases of sources.

For example, imagine if you used the code $\{\texttt{00}, \texttt{01}, \texttt{10}, \texttt{11}\}$ - then the average length is $2$ and the efficiencies drop to $82.5\%$ (case 1) and $87.5\%$ (case 2).

What the Huffman coding process guarantees is the most efficient prefix code possible for a given source, not a perfectly efficient code for every source.

So your question really is "why is it possible with some sources to make 100% efficient Huffman codes, and with other sources the most efficient possible Huffman code is less than 100% efficient?"

The answer there is that if you have a perfectly efficient Huffman code, then it's impossible to tell the difference between a stream of (source -> Huffman code) and a stream of uniformly random $\texttt{0}$s and $\texttt{1}$s. In your case number 2, with the first Huffman code, you have that situation: a stream of the source encoded by the Huffman code begins with $\texttt{0}$ half the time, and with $\texttt{1}$ half the time. When it starts with $\texttt{0}$, you start a new character from the source and so the next digit naturally is also evenly distributed. When it starts with $\texttt{1}$, half the time the next digit is $\texttt{0}$, half the time $\texttt{1}$, etc. This property (that after any sequence of bits, the chance of the next bit being $\texttt{0}$ or $\texttt{1}$ is $\frac{1}{2}$) means that the resulting binary stream has an entropy of 1 bit of entropy per output bit. (The same as a random binary source)

However, in case 1, (again using the first Huffman code) after seeing a $\texttt{1}$ in the stream, you're more likely to see a $\texttt{0}$ than a $\texttt{1}$. This means that the binary stream you get by connecting your source to the Huffman code has an entropy of less than 1 bit of entropy per output bit. (and therefore, that the binary stream is carrying less information per output bit than a random binary source)

The perfect match in case 2 happens because the probabilities of the source are all (negative) powers of $2$ and the probability of each output symbol matches the probability that a uniformly random noise source would output the symbol's Huffman string. Basically, the maximum possible efficiency for a Huffman code is a measure of how well a source's output probabilities can be approximated in binary.

Note that if we took your case 1 source and considered outputs two at a time, we'd be able to better approximate the probabilities in binary, and therefore get a more efficient Huffman code:

$$ \begin{array}{|c|l|l|} \hline \mathrm{output}& p & \mathrm{Huffman}\,\mathrm{code} \\ \hline a_0a_0 & 0.25 & \texttt{10} \\ \hline a_0a_1 & 0.15 & \texttt{000} \\ \hline a_0a_2 & 0.075 & \texttt{0100} \\ \hline a_0a_3 & 0.025 & \texttt{01110} \\ \hline a_1a_0 & 0.15 & \texttt{001} \\ \hline a_1a_1 & 0.09 & \texttt{110} \\ \hline a_1a_2 & 0.045 & \texttt{1110} \\ \hline a_1a_3 & 0.015 & \texttt{011010} \\ \hline a_2a_0 & 0.075 & \texttt{0101} \\ \hline a_2a_1 & 0.045 & \texttt{1111} \\ \hline a_2a_2 & 0.0225 & \texttt{011000} \\ \hline a_2a_3 & 0.0075 & \texttt{0110011} \\ \hline a_3a_0 & 0.025 & \texttt{01111} \\ \hline a_3a_1 & 0.015 & \texttt{011011} \\ \hline a_3a_2 & 0.0075 & \texttt{01100100} \\ \hline a_3a_3 & 0.0025 & \texttt{01100101} \\ \hline \end{array} $$

This has an average code length of $3.3275$, whereas the double-output source has an entropy of $3.30$ for an efficiency of $99.04\%$.

If you continued this process to 3 symbols at a time, you'd be able to get a $99.24\%$ efficient code. To 4 symbols, $99.43\%$ efficient.

  • $\begingroup$ How is it that you found the efficiency without actually constructing the code? Is there a way to give a rough estimate of the amount of concatenation needed to achieve a certain efficiency? $\endgroup$
    – Lod
    Oct 14 '18 at 15:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.