How to Use this Site

  • Type a string of probabilities delimited by a space in the text box.
    • (The numbers entered are whole numbers, decimals or fractions, such that they must add up to one.)

  • The 'Go' button will jump to the resulting tree.
  • The 'Play' button will start from level one and take one step through the construction of the tree every one second.
  • The 'Forward' button will take one step through the construction of the tree.
  • The 'Back' button will go back one step.
  • The 'Reset' button will clear the page and bring up these instructions.

What is Huffman code?

Developed by David Huffman while he was a Ph.D. student at MIT, and published in the 1952 paper "A Method for the Construction of Minimum-Redundancy Codes"

It takes alphabet and gives them the shortest code length of bits possible (optimal), based off given probabilities for a particular set of in the alphabet. The produced code is a 'prefix code', which is to say that no code will be a prefix of another code. All code strings are uniquely and instantaneously decodable.

To top

Who:

Brandon Martella • Shawn Robbins • Christian Smeltzer • Charles Bocage

What:

A website that allows a user to input probabilities and creates a tree using Huffman's algorithm.

Where:

California State University Stanislaus
One University Circle
Turlock, CA 95382

When:

Spring Semester 2012

Why:

Final project for CS 4450- Coding and Information Theory

How:

The site uses JavaScript for everything including drawing the tree, which uses the new <canvas> tag. Because javascript does not have infinite precision all calculations are done in fraction in order to make each set of percentages add up to 1. For example 0.3 0.3 0.3 will be converted to 1/3 1/3 1/3. 0.3 * 3 will be close to 1 approximately .99999999 but 1/3 * 3 equals 1. In addition each tree is labeled with a number in which it was created so the draw function can draw the tree in the correct order.

What we learned:

  • JavaScript does not support infinite precision
  • How to sort binary strings in ascending order
  • How to draw with the html5 canvas API
  • How to add and reduce fractions with code
  • Gained an in depth knowledge of how the Huffman code works
  • How to build a tree that does not necessarily build in order