Huffman coding

the history of Huffman coding

David A. Huffman had a great idea of an algorithm deal with the optimal code of given probability.

The Huffman coding is an entropy encoding algorithm used for lossless data compression, this method developed in 1952 paper " A method for the Construction of Minimum-Redundancy Codes".

procedure of Binary Huffman coding procedure

1. Sort the probability of all source symbols in a descending order.

2. Merge the last two into a new symbol, add their probabilities.

3. Repeat the above steps until only one root left.

4. Code assignment: Traverse the tree from the root to each leaf node, assign 0 to the top branch and 1 to the bottom branch.


(The Huffman algorithm works from leaves to the root of the code tree)

Limitations of Huffman Codes:

- Fixed source probability is required.

- For online computation, one needs extra bits to encode the table.

Application of Huffman codes:

Applications: Huffman Codes are often used

as a “back-end” to other compression 

methods. For example, MP3, JPEG and MPEG

have a “front-end” model (lossy compression) 

and quantisation followed by Huffman coding.

*D.A. Huffman, "A Method for the Construction of Minimum-
Redundancy Codes", Proceedings of the I.R.E., September 1952,

pp 1098–1102. Huffman's original article.