$12\mathrm{.}5$ Lab: Huffman Code

Huffman codes is a compression scheme for assigning variable$-$length bit codes to symbols$($letters$)$ to allow for a minimum cost storage and transmission of messages. The idea is to assign variable$-$length codes to input characters, with the lengths of the assigned codes are based on the frequencies of corresponding characters.

The variable$-$length codes assigned to input characters must be Prefix Codes. That means the codes $($bit sequences$)$ are assigned in such a way that the code assigned to one character is not the prefix of code assigned to any other character. In this way we ensure that there is no ambiguity when decoding the resulting bitstream.

We would like to implement the encoding and decoding process to allow for the compression of a given text. In addition, we would like to be able to decode a given bitstream with a provided encoding.

Write a program that takes a string as input. It should compute the frequencies and then construct a Huffman Code. For simplicity, use only the upper$-$case versions of all characters. We would like to have some consistency in selecting symbols to pair.

Select the smaller value first $($on the left, implicitly the $0$ value$).$ In the case of a tie, select alphabetically with the first letter on the left.

For example, for an input of:

This is his message

The resulting Huffman Code should be:

Huffman Code: $\text{'}\text{'}110\text{'}$A$\text{'}0000\text{'}$E$\text{'}001\text{'}$G$\text{'}0001\text{'}$H$\text{'}010\text{'}$I$\text{'}111\text{'}$M$\text{'}0110\text{'}$S$\text{'}10\text{'}$T$\text{'}0111$

And the encoding of the message should be:

Encoded string is: $01110101111011011110110010111101100110001101000000001001$

c$++$ please