Question

Huffman coding to encode these symbols with given frequencies: \({\bf{A}}:{\rm{ }}{\bf{0}}.{\bf{10}},{\rm{ }}{\bf{B}}:{\rm{ }}{\bf{0}}.{\bf{25}},{\rm{ }}{\bf{C}}:{\rm{ }}{\bf{0}}.{\bf{05}},{\rm{ }}{\bf{D}}:{\rm{ }}{\bf{0}}.{\bf{15}},{\rm{ }}{\bf{E}}:{\rm{ }}{\bf{0}}.{\bf{30}},{\rm{ }}{\bf{F}}:{\rm{ }}{\bf{0}}.{\bf{07}},{\rm{ }}{\bf{G}}:{\rm{ }}{\bf{0}}.{\bf{08}}\). What is the average number of bits required to encode a symbol?

Short answer

\({\bf{A = 011, B = 01, C = 1110, D = 010, E = 00, F = 0110 and G = 111}}\). The average number of bits required is 2.57 bits.

Step-by-step solution

Huffman coding is a fundamental algorithm in data compression, the subject devoted to reducing the number of bits required to represent information.

Huffman coding is a greedy algorithm. Replacing the two subtrees with the smallest weight at each step leads to an optimal code in the sense that no binary prefix code for these symbols can encode these symbols using fewer bits.

Use Huffman coding to encode these symbols with given frequencies

Huffman coding is an algorithm that supports the frequency of the occurrence of knowledge items. Assign variable-length codes to input characters and also the length of the assigned code depends on the frequencies of corresponding characters. The foremost frequent characters get the littlest code while the least frequent characters get the biggest code. There are mainly two things in Huffman coding:

1) Build a Huffman tree from input characters.

2) Traverse the Huffman tree and assign codes to nature.

Steps to build Huffman tree

Step1.Create a leaf node for each unique character and founded a min heap of all leaf nodes.

Step2.Extract two nodes of least frequency from the min heap.

Step3. Replace the rooted trees \({\bf{T}}\) and \({\bf{r}}\) of least frequency from the min heap with having a new root that has \({\bf{T}}\) as its left sub-tree and \({\bf{f}}\) as its right sub-tree.

Step4. Assign the left level to \({\bf{0}}\) and the right level to \({\bf{1}}\).

Step5. Repeat step 2, step 3 and step 4 until there is only one node in the heap so that tree is complete.

The symbols with frequencies mentioned within the problem are:

\({\bf{A:0}}{\bf{.10, B:0}}{\bf{.25, C:0}}{\bf{.05, D:0}}{\bf{.15, E:0}}{\bf{.30, F:0}}{\bf{.07, G:0}}{\bf{.08}}\)

Now again steps to build Huffman tree

Step1. Build a min heap which contains \({\bf{7}}\) nodes where each node may be a root of a tree with single node

Step2.Extract two nodes of least frequency from min heap. Add a replacement internal node with the sum of their frequency.

The frequency of new node is: \({\bf{0}}{\bf{.05 + 0}}{\bf{.07 = 0}}{\bf{.12}}\).

Therefore, the heap becomes

Step3.Extract two nodes of least frequency from min heap. Add a replacement internal node with the sum of their frequency.

The frequency of new node is:\({\bf{0}}{\bf{.10 + 0}}{\bf{.08 = 0}}{\bf{.18}}\).

Hence, the heap becomes

Step4.Extract two nodes of least frequency from min heap. Add a replacement internal node with the sum of their frequency.

The frequency of new node is: \({\bf{0}}{\bf{.12 + 0}}{\bf{.15 = 0}}{\bf{.27}}\).

Consequently, the heap becomes

Step5.Extract two nodes of least frequency from min heap. Add a replacement internal node with the sum of their frequency.

The frequency of new node is:\({\bf{0}}{\bf{.18 + 0}}{\bf{.25 = 0}}{\bf{.42}}\).

So, the heap becomes

Step6.Extract two nodes of least frequency from min heap. Add a replacement internal node with the sum of their frequency.

The frequency of new node is:\({\bf{0}}{\bf{.27 + 0}}{\bf{.30 = 0}}{\bf{.57}}\).

Thereafter, the heap becomes

Step7.Finally, Extract two nodes of least frequency from min heap. Add a replacement internal node with the sum of their frequency.

The frequency of new node is\({\bf{0}}{\bf{.43 + 0}}{\bf{.57 = 1}}{\bf{.00}}\).

Therefore, the final heap becomes.

Final conclusion, the average numbers of bits

The encodings produced by the symbols are:

\({\bf{A = 011, B = 01, C = 1110, D = 010, E = 00, F = 0110 and G = 111}}\)

So, the average numbers of bits similar withencode anemblem with the encoded symbols are:

\(\begin{array}{l}{\bf{3 x 0}}{\bf{.10 + 2 x 0}}{\bf{.25 + 4 x 0}}{\bf{.05 + 3 x 0}}{\bf{.15 + 2 x 0}}{\bf{.30 + 4 x 0}}{\bf{.07 + 3x 0}}{\bf{.08 }}\\{\bf{ = 0}}{\bf{.30 + 0}}{\bf{.50 + 0}}{\bf{.20 + 0}}{\bf{.45 + 0}}{\bf{.60 + 0}}{\bf{.28 + 0}}{\bf{.24 }}\\{\bf{ = 2}}{\bf{.57}}\end{array}\)

Hence, the average number of bits required to encode the symbol is \({\bf{2}}{\bf{.57}}\).