Huffman Coding
Huffman coding, published by David Huffman in 1952, is a prefix-code construction algorithm that assigns short codes to frequent symbols and long codes to rare ones, reaching the entropy lower bound.
Purpose
It builds optimal prefix codes for lossless compression when symbol frequencies are known, and is the back end of DEFLATE, JPEG, and MP3.
Mechanism
Count symbol frequencies and build a Huffman tree: repeatedly merge the two lowest-frequency nodes into a new parent until only the root remains; the root-to-leaf path (left 0, right 1) gives each symbol's code. Frequent symbols get short paths.
Use cases
- Entropy coding stage in DEFLATE
- Entropy coding stage in JPEG/MP3
- Back end of text compression