Smatchcube's website 🌍


Exercise 2.70

Let’s start by defining the lyrics and the associated tree.

As we can see the frequency matches the lyrics so the tree is “perfect” for this message.
We can verify if the encoding is working by checking if encoding and decoding the message return the original message:

Now let’s see the length of the encoded message to see how many bits are required for the lyrics.

If we use a fixed-length, we would need to encode each symbol of the height-symbol alphabet with \(\log_2(8)=3\) bits.

As there are \(36\) symbols in the lyrics we would need \(36 \times 3 = 108\) bits to encode the lyrics. We see that using variable-length code saves more than 20% in space in comparison with the fixed-length code.