Shannon-Fano Coding

Predecessor to Huffman coding, a compression algorithm.

• Calculate how often a symbol will appear in a given message.
• Construct a tree such that the left and right branches have as close to equal liklihood as possible (ex. if a single symbol is 45% and the rest of all symbols sum to 55%, the tree is split between the popular symbol and the set.)
• Encode bits as a walk left or right on the trees.