Problem 4 - Huffman Codes

Answer following questions regarding Huffman codes.

1.

Consider a string that consists of four characters $a$, $b$, $c$, and $d$. Assume that $a$, $b$, $c$, and $d$ appear with probabilities 0.5, 0.25, 0.125, 0.125, respectively. Write the Huffman codes for $a$, $b$, $c$, and $d$.

2.

Compute the expected length of the codes.

3.

Consider a string consisting of $c_i$, with $i= 1, \dots, n$. $c_i$ appears with probability $p_i$ where $\sum_{i=1}^n p_i = 1$ and $p_k \geq p_{k+1}$, with $k = 1, \dots, n-1$. Write an algorithm that computes their Huffman codes.

1.

$$\includegraphics{huffman2.ps}$$

2.

The expected length of the codes is:

$$\bar{L} = 1\times 0.5 + 2\times 0.25 + 3\times 0.125 + 3\times 0.125 = 1.75$$

3.

$c_1 = 0$
$c_2 = 10$
$c_3 = 110$
$\vdots$
$c_{n-1} = 1\cdots10$ with $n-2$ 1's
$c_n = 1\cdots1$ with $n-1$ 1's