22.2.1. Merging Frequencies

Try these first

1. 1.

   What happens when two characters with the least frequency are merged?

   Hint

   Think about the process of combining numbers together.

2. 2.

   What character encoding is assigned to the last two remaining letters?

   Hint

   What binary code would you use for two choices?

3. 3.

   What is the first step in Huffman coding?

   • Merge the highest frequencies
   • Merge the lowest frequencies
   • Assign binary codes directly

   Hint

   Remember the strategy is to minimize representation.

4. 4.

   True or False: Huffman coding guarantees optimal encoding for any dataset.

   • True
   • False

   Hint

   Think about the fundamental principle of this coding method.

5. 5.

   Given the following frequencies, construct a Huffman tree and determine the codes: X(0.05), Y(0.15), Z(0.25), W(0.55).

   Hint

   Start with the two lowest frequencies.

6. 6.

   Explain why alternative merging strategies lead to sub-optimal trees compared to Huffman’s method.

   Hint

   Consider trade-offs of choosing higher frequencies early.