21.7. Expected Length of the Encoding

Try these first

1. 1.

   What is Huffman coding?

   Hint

   It involves using shorter codes for more frequent characters.

2. 2.

   What does a prefix code ensure?

   Hint

   Think about how codes might overlap.

3. 3.

   What is the purpose of Huffman coding?

   • To assign fixed-length codes to all characters
   • To encode letters based on their frequency for better efficiency
   • To create ambiguous codes for different letters

   Hint

   Think about how efficiency can be enhanced using frequency.

4. 4.

   True or False: In a prefix code, one code can be a prefix of another.

   • True
   • False

   Hint

   Consider what happens during decoding.

5. 5.

   Assume we need to encode the letters 'A', 'B', 'C', 'D', 'E' with frequencies 0.4, 0.3, 0.2, 0.1. Create the Huffman tree, and derive the encoding for each character.

   Hint

   Start by pairing the lowest frequencies and build upwards.

6. 6.

   What would happen if we allow one of the codes in a Huffman tree to be the prefix of another? Discuss the implications for encoding and decoding.

   Hint

   Think about how this overlaps during the decoding process.