Short Answer 
The optimal Huffman code is constructed by first sorting characters by their probabilities, then iteratively combining the lowest probability characters into a “super-character,” and finally calculating the average code length using their probabilities and code lengths, yielding an average of 1.99 bits per character.
Step 1: Sort Character Probabilities
Begin the process of constructing the optimal Huffman code by organizing the characters based on their probabilities in descending order. For this example, the sorted characters and their probabilities are as follows:
- f: 0.27
- e: 0.23
- d: 0.22
- c: 0.12
- b: 0.09
- a: 0.07
Step 2: Combine Lowest Probability Characters
Next, identify the two characters with the smallest probabilities and combine them into a new “super-character,” with a probability equal to their sum. Continue this process iteratively:
- Select two characters with the lowest probabilities.
- Combine them into a new character, updating the list accordingly.
- Repeat until only one “super-character” remains.
Step 3: Calculate Average Code Length
Once the optimal Huffman tree is created, compute the average code length using the weighted average formula. Each character’s contribution to the average is based on its probability and the length of its assigned code:
The formula used is:
- average code length = (0.27 ‚à öo 1 + 0.23 ‚à öo 2 + 0.22 ‚à öo 2 + 0.12 ‚à öo 3 + 0.09 ‚à öo 3 + 0.07 ‚à öo 3) bits per character
The result of this calculation yields an average code length of 1.99 bits per character.