Huffman code optimal substructure property

Question

I am learning about Greedy Algorithms and we did an example on Huffman codes. To prove the correctness of our algorithm, we had to have the greedy choice property and the optimal substructure property.

Here is what my professor said about the optimal substructure property:

Let C be an alphabet and x and y characters with the lowest frequency.

Let C' = C-{x,y}U{z} where z.frequency = x.frequency + y.frequency

Let T' (a binary tree) be an optimal prefix code for C' She then drew these pictures

Let T be constructed from T' by replacing z with an internal node with children x and y. Then T is an optimal prefix code for C

And I don't really understand what/how this proves anything. All I see that she is doing is like..working backwards. First she replaced x and y with z, and now she is replacing z with x and y. What exactly is this showing? I'm really bad with proofs sometimes so I am just completely lost as to how this showed me anything about anything

Answer 1

Your teacher are proving:

Lemma: If $T'$ is optimal for $C' = C \setminus \{ x, y \} + \{ z \}$, then $T$ is optimal for $C$.

Once you have this lemma, you can prove the correctness of Huffman algorithm by mathematical induction on the cardinality of the alphabet $|C|$.

• Base Case: The base case of $|C| = 2$ is trivial.
• Inductive Hypothesis: Suppose Huffman algorithm is correct for any $|C| < n$.
• Inductive Step: Consider the case of $|C| = n$. According to Huffman algorithm, you reduce the problem to constructing $T'$ on $C'$ where $|C'| = n -1$. By inductive hypothesis, $T'$ is optimal for $C'$. By the lemma above, $T$ is then optimal for $C$.