Animation: Huffman Encoding

Animation Systems Collection -- Animations Collection

Description

Huffman codes represent a very useful way to compress data by ascertaining the frequency of occurrence for each character. The basic idea of the procedure is to assign bit codes of varying length to characters – where common characters receive a short code and uncommon characters receive a longer one.

To generate the code the two most uncommon elements are combined to a new node with the sum of the probability of it two daughters. This process is repeated until only one unprocessed node is left - the root of the tree.

In the end the elements of the tree (which leaves represent the input characters) get assigned their code. The code is generated by traversing the path from the root of the tree to the leave and adding a 0 for each branching to a left child and a 1 for each branching to a right child.

In the animation the generating of the code is first represented in text form before showing the generation of the code tree. The current coding step is highlighted in a different colour.

Finally the code for each input element is shown and a message is coded.

Screen Shot(s):

Pseudo code for the algorithm

After merging the two nodes with lowest probability

Code tree with codes and encoded message

Classification

• Algorithms
• Compression
• Tree Structures

Animation Rating

You can provide a rating for this animation. The rating is performed on a scale of 1 to 10, where 10 is the highest possible grade.

1(very bad) 2 3 4 5 6 7 8 9 10(very good)

File information

Title	Huffman Encoding
Animation URL	http://www.animal.ahrgr.de/Anims/en/huffman.aml
Animation Applet	Animal Applet
Animation System	Animal
Animation Type	dynamic full VCR
Supported OS(s)	Linux,MacOS,Windows 95,Windows 98,Windows ME,Windows NT,Windows 2000,Unix
Author(s)	Guido Rößling
Date	1999-05-10
File Size size	4835 Byte
Number of Accesses:	12902
Added to DB by	Guido Rößling
Average Rating	5.6981(53 submitted ratings)
Language:	en
Number of Accesses:	12902

BibTeX bibliographic entry for citations:

@Misc{Rößling:1999,
   author = {Guido Rößling},
   title = {Huffman Encoding},
   howpublished = {WWW: \url{http://www.animal.ahrgr.de/Anims/en/huffman.aml}},
 }