a₁ A source has an alphabet with probabilities (0.1, 0.23, 0.25, 0.05, 0.15, 0.22). 1. Find the entropy of this source. 2. Compare this entropy with the entropy of a uniformly distributed source with the same alphabet. 3. Compute the compression ratio and the coding efficiency. a₂ a3 a4 26 a5 Alphabet Probabilities 0.1 0.23 0.25 0.05 0.15 0.22 Equal Probabilities 1/6 1/6 1/6 1/6 1/6 1/6 Code 1 Code 2
Huffman coding assigns variable-length codes to input characters. The assigned code length is based on the frequency of the corresponding letter. The most common characters get the lowest codes, and the rarest characters get the highest codes.
Variable-length codes assigned to input characters are prefix codes. That is, codes (bit strings) are assigned such that the code assigned to one character is not a prefix of the code assigned to another character.
Steps to build a Huffman tree
- The input is an array of unique characters and their frequencies and the output is a Huffman tree.
- Create a leaf node for each unique character and create a min-heap of all leaf nodes (min-heap is used as priority queue. The value of the frequency field is used to compare two nodes within the min heap. First, the least common characters are at the root)
- Extract two nodes from the minimum heap with minimum frequency.
- Creates a new internal node with a frequency equal to the sum of the frequencies of the two nodes. Make the first extracted node the left child and the other extracted nodes the right child. Add this node to the minimum heap. Repeat steps 2 and 3 until only one node remains in the heap. The rest of the nodes are root nodes and complete the tree.
Step by step
Solved in 2 steps
