Code 52 : Huffman Code

Huffman Code

Background

The Huffman code was developed in 1952 by David Albert Huffman (* 9. April 1925; † 7. October 1999 in Santa Cruz, California). It is an algorithm that creates a binary tree based on the input data, which results in a lossless data compression.

Principle

Let’s assume the message "ERDBEERE" should be encoded. A leaf is created for each character. Then, the most infrequent characters are translated into a new tree until only one tree remains.¹

Fig. 1: Binary tree Huffman code¹

This results in the following code-table:

Character	Code
E	0
R	10
B	110
D	111

To get the original message "ERDBEERE" back: The following sequence of bits is read out according to the binary tree: "0 10 111 110 0 0 10 0". The original ASCII-message was significantly longer:  "01100101 01110010 01100100 01100010 01100101 01100101 01110010 01100101"

Details

The Huffman code is a so called "entropy encoding".