A file contains only colons spaces newlines commas and digit

A file contains only colons, spaces, newlines, commas, and digits in the following frequency: colon (100), space (605), newline (100), comma (705), 0 (431), 1 (242), 2 (176), 3 (59), 4 (185), 5 (250), 6 (174), 7 (199), 8 (205), 9 (217). Construct the Huffman code.

Solution

The huffman coding algorithm begins with a forest of trees consisting of one vertex each. At each step we combine two trees having the least total weight into a single tree by introducing a new root and placing the larger weight at its left subtree and the tree with smaller weight at its right subtree.

For the given problem, we have:

Continuing this way we get the following tree:

For example the code for the value 1 would be: 1011 and for space it would be:110.