4.2 Huffman Coding

Huffman Coding

Huffman coding is the optimal scheme for encoding a discrete random variable $X$ using prefix free codewords, such that no codeword is a prefix of another codeword.

It constructs a binary tree, where the leaves correspond to symbols, by greedily combining the lowest probability nodes first and building the tree in a bottom-up fashion. This ensures that higher probability symbols are assigned shorter codewords, while lower probability symbols receive longer codewords:

\usepackage{tikz}
 
\begin{document}
 
\begin{tikzpicture}[ 
 level distance=1.5cm,
 level 1/.style={sibling distance=3cm},
 level 2/.style={sibling distance=3cm},
 level 3/.style={sibling distance=3cm},
 scale=0.75
]
 
% Root node
\node {} 
   child { node {\( p_1 \)} 
       edge from parent node[above left] {0} }
   child { node {} 
       child { node {\( p_2 \)} 
           edge from parent node[above left] {0} }
       child { node {  } 
          child { node {}
              child { node {\( p_{n-1} \)} 
                  edge from parent node[above left] {0} }
              child { node {\( p_{n} \)} 
                  edge from parent node[above right] {1} }
              edge from parent[draw=none] node[midway] {\( \vdots \)}
          }
          edge from parent node[above right] {1}
       }
       edge from parent node[above right] {1}
   };
 
\end{tikzpicture}
 
\end{document}

Huffman coding achieves an expected codeword length that is always at least the entropy $H(X)$ and at most $H(X)+1$ , ensuring near-optimal compression while maintaining a prefix-free structure.

Examples

Four Symbols

Consider the alphabet $\mathcal{X}=\{a,b,c,d\}$, where each symbol occurs at probabilities $(0.6,0.3,0.05,0.05)$. Then,

• The naive coding approach leaves our expected length at $2$ bits per symbol (i.e. $w_N=(00,01,10,11)$).
• The Huffman codewords are $w=(0,10,110,111)$ (note that they are prefix free). Given the probabilities of each symbol, as well as their codeword lengths, is $0.6\cdot 1+0.3\cdot 2+0.05\cdot 3+0.05\cdot 3=1.5$ bits per symbol.

However, the Shannon Entropy is $H(X)=0.6{\log }_2\frac{1}{0.6}+0.3{\log }_2\frac{1}{0.3}+0.1{\log }_2\frac{1}{0.05}\approx 1.395$, where $1.5\gg 1.395+ϵ$. Therefore, by Shannon’s source coding theorem, there are more efficient source coding algorithms than Huffman code.