Feedback Author Log in

Hightech Dreams

Huffman Coding

This page was developed to explain the Huffman coding scheme by tracing the creation of a Huffman tree.

You can enter any symbol set and see how the Huffman tree is constructed at each tree joining step. Click the Encoding Schemes tab to view corresponding encodings for each symbol.

Manipulate the symbols and their frequencies by adding space-separated list of symbols in the form below. Repeated symbols increase their frequency.

The Algorithm

  1. If starting with a set of symbols, find the unique ones and count their frequency.
  2. Now that you have a set of symbols paired with their frequencies, let's really start.
  3. Turn the symbols into trees of height 1.
  4. If there is less than 2 trees, that is your Huffman tree and you are done.
  5. Sort the trees by frequency.
  6. Join the 2 minimum frequency trees as direct children of another tree. This new tree will have a root symbol with name empty and frequency equal to the sum of frequencies for its children.
  7. Go back to step 4.

If the algorithm seems confusing, clear the tracer above and try with different inputs. Try to predict the changes from step to step.

Related Resources

Add New Comment