Huffman Encoding

• Algorithm

• Arrange symbols in order of decreasing probability
• Combine two symbols with lowest probability
• Assign a new name, add their probabilities
• Rebuild the list
• Combine the next two lowest symbols
• Repeat until there is one symbol, with probability of one
• Build a binary tree
• Form codewords by tracing down the tree to the symbol