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.

Note: We will construct the code by pairing the lowest frequency nodes at each step. The lower frequency node will be assigned the $0$ value encoding. In the case of a tie, the first letter alphabetically will be assigned the value $0.$

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$ provide the code according to these instructions within main.cpp