Question

a. Describe the Huffman coding algorithm for constructing an optimal code for a set of symbols, given the frequency of these symbols.

b. Use Huffman coding to find an optimal code for these symbols and frequencies: \({\bf{A}}:{\bf{0}}.{\bf{2}},{\bf{B}}:{\bf{0}}.{\bf{1}},{\bf{C}}:0.3,{\bf{D}}:{\bf{0}}.{\bf{4}}\).

Short answer

Huffman coding:

For every given symbol \(v\), we draw a tree consisting of a vertex \(v\) alone (these trees then form a forest).

The weight of the tree containing \(v\) is then the frequency of the symbol.

At every step of the Huffman coding algorithm, select the two trees \({T_1}\) and \({T_2}\) with the lowest frequencies (in case of a tie, arbitrarily chose one of the trees with the lowest or second lowest frequency).

We replace these two trees \({T_1}\) and \({T_2}\) by one new tree, which has a root with \({T_1}\) as its left child and \({T_2}\) as its right child (assuming that \({T_1}\) has a higher frequency than \({T_2}\)). The weight of the tree is the sum of the weight of \({T_1}\) and the weight of \({T_2}\). Repeat this procedure until the forest contains exactly one tree.

\(\begin{array}{c}A:000\\B:001\\C:01\\D:1\end{array}\)

Step-by-step solution

Definition

Huffman coding:

For every given symbol v, we draw a tree consisting of a vertex v alone (these trees then form a forest).

The weight of the tree containing \(v\) is then the frequency of the symbol.

At every step of the Huffman coding algorithm, select the two trees \({T_1}\) and \({T_2}\) with the lowest frequencies (in case of a tie, arbitrarily chose one of the trees with the lowest or second lowest frequency).

One replaces these two trees \({T_1}\) and \({T_2}\) by one new tree, which has a root with \({T_1}\) as its left child and \({T_2}\) as its right child (assuming that \({T_1}\) has a higher frequency than \({T_2}\)). The weight of the tree is the sum of the weight of \({T_1}\)and the weight of \({T_2}\). Repeat this procedure until the forest contains exactly one tree.

Huffman coding

Huffman coding

\(\begin{array}{c}A:{\bf{0}}{\bf{.2}}\\{\bf{B:0}}{\bf{.1}}\\{\bf{C:0}}{\bf{.3}}\\{\bf{D:0}}{\bf{.4}}\end{array}\)

One has been given \({\bf{4}}\) symbols. One will then draw a forest of \({\bf{4}}\) trees containing \({\bf{1}}\) vertex each, while the vertex has the above names and are labelled with the given values.

Weight of the edge

One notes that \(A\) and \(B\) have the smallest weights.

One will then replace their trees with a new tree that has a root with a left and right child. The edge to the left child is labeled \({\bf{0}}\) and the edge to the right child is labeled \({\bf{1}}\). The left child is named \(A\) (highest weight of the two) and the right child is named \(B\) (Iowest weight of the two).

The weight of the new tree is the sum of the weight of the trees that were replaced.

Step 4:Smallest weight of the edge

One notes that \(A + B\) and \({\bf{C}}\) have the smallest weights (note: \(A + B\) represents the tree with leaves \(A\) and \(B\)).

One will then replace their trees with a new tree that has a root with a left and right child. The edge to the left child is labeled \({\bf{0}}\) and the edge to the right child is labeled \({\bf{1}}\). The left child is named \(A + B\) (highest weight of the two) and the right child is named \({\bf{C}}\) (lowest weight of the two).

The weight of the new tree is the sum of the weight of the trees that were replaced.

Lowest weight of the tree

One notes that \(A + B\) and \({\bf{D}}\) have the smallest weights (note: \(A + B\) represents the tree with leaves \(A\) and \(B\)).

One will then replace their trees with a new tree that has a root with a left and right child. The edge to the left child is labeled \({\bf{0}}\) and the edge to the right child is labeled \({\bf{1}}\). The left child is named \(A + B\) (highest weight of the two) and the right child is named \({\bf{D}}\) (lowest weight of the two).

The weight of the new tree is the sum of the weight of the trees that were replaced.

Encoding

The encoding of the letters is then the sequence of labels of the edges in the path from the root to the letter.

\(\begin{array}{c}A:000\\B:001\\C:01\\D:1\end{array}\)