Deutsch (DE-CH-AT)English (United Kingdom)
 
 
 
 
 
   


 

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.1

huffman_tree2

Fig. 1: Binary tree Huffman code1


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".

 

Weblinks

http://en.wikipedia.org/wiki/Huffman_code

 

References

1 Kryptographiespielplatz


   
     
 
 
Copyright © 1998 - 2016 CrypTool Project / Contributors