Shannon-Fano Coding

Created: 2024-09-28T18:02:18-05:00

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.