Question

Question: Suppose the symbols a,b,c,d,e occur with frequencies $\frac{\mathbf{1}}{\mathbf{2}}\mathbf{,}\frac{\mathbf{1}}{\mathbf{4}}\mathbf{,}\frac{\mathbf{1}}{\mathbf{8}}\mathbf{,}\frac{\mathbf{1}}{\mathbf{16}}\mathbf{,}\frac{\mathbf{1}}{\mathbf{16}}\mathbf{,}$respectively.

(a) What is the Huffman encoding of the alphabet?

(b) If this encoding is applied to a file consisting of$\mathbf{1}\mathbf{,}\mathbf{000}\mathbf{,}\mathbf{1000}$ characters with the given frequencies, what is the length of the encoded file in bits?

Short answer

Answers

1. Huffman encoding of the symbols a,b,c,d,e, is$0,10,110,1110,1111$

   
   

   respectively.

2. The length of the encoded file in bits is 1875000 .

Step-by-step solution

Define Huffman Encoding 

Huffman Encoding is represented by a full binary tree. A binary tree in which every node has zero or two children is called a full binary tree. Alphabets are at the leaves, and each codeword is generated by a path from the root to leaf where left is represented as and right is represented as .

Determine Huffman encoding of given alphabets.

(a)

Given frequencies are sorted in increasing order.

After sorting, a full binary tree representation of the given frequencies is made as follows:

Huffman Encoding is done from the root node to each leaf node. So, codeword of is , codeword of is . Similarly, codewords of other alphabets are also found as shown in the table.

Alphabet	Codeword
a	0
b	10
c	110
d	1110
e	1111

Thus, Huffman encoding of the given alphabets are 0,10,110,1110,1111.

Calculate of length of encoded file and the number of bits 

(b)

Number of bits needed to encode is calculated by multiplying the number of characters in the file and the entropy of the distribution. A measure of how much randomness a distribution contains is called its Entropy.

$Entropy=\sum _{i=1}^n{p}_{i}log\left(\frac{1}{p_i}\right)$

Here, is the number of possible outcomes, is the probability of each outcome.

Consider the formula for the number of bits.

$Numberofbits,N=\sum _{i=1}^{n}m{p}_{i}log\left(\frac{1}{p_i}\right)$

Here, is the number of characters in the file

$$\begin{gathered} N=\sum _{i=1}^n{p}_i\log \left(\frac{1}{p_i}\right) \\ =m\times \sum _{i=1}^5{p}_i\log \left(\frac{1}{p_i}\right) \\ =m\times \left(\frac{1}{2}\log \left(2\right)+\frac{1}{4}\log \left(4\right)+\frac{1}{8}\log \left(8\right)+\frac{1}{16}\log \left(16\right)+\frac{1}{16}\log \left(16\right)\right) \\ =1000000\times \left(\frac{1}{2}\times 1+\frac{1}{4}\times 2+\frac{1}{8}\times 3+\frac{1}{16}\times 4+\frac{1}{2}\times 4\right) \end{gathered}$$

N is further solved as:

$$\begin{gathered} N=1000000\times \left(\frac{1}{2}+\frac{1}{2}+\frac{3}{8}+\frac{1}{4}+\frac{1}{4}\right) \\ =1000000\times \left(\frac{3}{2}+\frac{3}{8}\right) \\ =1000000\times \frac{15}{8} \\ =1875000 \end{gathered}$$

Therefore, the length of encoded file in bits is 1875000.