Question

A long string consists of the four characters $\mathbf{}\mathbf{A}\mathbf{,}\mathbf{C}\mathbf{,}\mathbf{G}\mathbf{,}\mathbf{T}$ ; they appear with frequency $\mathbf{}\mathbf{31}\mathbf{\%}\mathbf{,}\mathbf{20}\mathbf{\%}\mathbf{,}\mathbf{9}\mathbf{\%}\mathbf{}$and$\mathbf{40}\mathbf{\%}\mathbf{}$ respectively. What is the Huffman encoding of these four characters?

Short answer

Huffman encoding of the characters$\mathrm{A},\mathrm{C},\mathrm{G},\mathrm{T}$ is$01,001,000,1$ respectively.

Step-by-step solution

Frequencies of the characters are sorted in increasing order

Write the given frequency distribution in the form of a table, in increasing order.

Represent the frequencies in a full binary tree

A binary tree in which every node has zero or two children is called a full binary tree.

Characters along with their frequencies in sorted order are placed at the leaf nodes, and Huffman encoding is done by following a path from the root to leaf where every left node is represented as 0 and every right node is represented as 1.Full binary tree created is shown:

Huffman encoding of alphabets

White the Huffman encoding of the given frequency distribution.

Thus, Huffman encoding of the given characters are $01,000,001,1$.