Python programming Huffman tree

ELEC-621 Information Theory and Coding, Spring 2018 Lab 2 – Huffman Coding Huffman Tree:

• Finish the Python code for determining the Huffman Tree for the English alphabet. Your code needs to work for any probability distribution. For example, your code should work for the alphabet of another language too. The algorithm you need to implement is the same algorithm in the tutorial of Lab 1. Letters have to be sorted in ascending order of probabilities. The two least probable letters are combined into one tree where the two letters are the only leaf nodes, and the parent node is a new symbol whose probability is the addition of the probabilities of the two letters. The two letters are removed from the list of letters, and the new symbol is added to the list making sure that the list is still sorted in ascending order of probabilities. This process is repeated until there is only one symbol left in the list. This symbol is the root of the Huffman tree.

• Update the list of letters with the space character. For example, the text “hello world” has one space between letters “o” and “w”. You can find the frequency of the space character online. The space character is more frequent than the letter of higher frequency, “e”.