Huffman Coding

This page we will be looking at Huffman Coding and how to encode and decode a huffman tree

Overview

Huffman encoding is a method used to reduce the number of bits used to store a message. Huffman coding is built uppon the frequency of occuring characters or data items (pixels in an image). The goal Huffman coding intends to achieve is to use a lower amount of bits than origianlly used.

Method

Example: he ties the tether

First we make a list of the character frequency and order in ascending frequancy order - as below:

 I1
R1
S1
SPACE3
H3
T3
E5

Then we repeat the following process process until we only have one node left.

1. Take the two lowest frequency nodes from the list and join them together to make a new node. The label for this new node is the combined frequency of the two previous nodes that were taken out. Ignore the 0 and 1 in the diagram below.

2. Place this new node back in the list ensuring you position it at the correct frequency position, in this example it would be positioned just after the S1 node.

3. Repeat steps one and two until there is only one node left.

The tree is now complete. To read the Huffman coding for a character you start at the top and follow the route to the character’s node reading off the 1 or 0 on the arrows as you go along. Eventually you should end up with a diagram looking like this.

The complete Huffman Coding is:

i11010

S11011

R1100

SPACE111

E10

T01

H00

So the entire encoding for he ties the tether is: 00101110111010101101111101100100101100. The amount of bits used to encode this sentence is clearly longer than the original amount of charaters used. Huffman Coding works best with images and film as there are several colours and shades that would be the same, for example with an image of the sky there would be many shades of the same colour across the entire picture

Decoding a Huffman encoded string

To decode the Huffman string: 00101110111010101101111101100100101100 use the following steps starting at the top of the Huffman Tree.

1. Take a character (call it C ) from the left most position in our string (this will be a zero or a 1), make a note of the index position you are at in the string, lets call this X, (so this will start at one and increment by 1 each time we take a character)

2. Navigate down the Huffman tree. Left is 0, right is 1. If C from step 1 was a zero we navigate left, else right

3. Have you reached a letter?

4. If not then go back to step 1 and continue from the position X that you were at. 

5.If you reached a letter then make a note of it (this is part of your decoded string, store it to one side) 

6. Now starting again from the top of the huffman tree Go back to step 1 and continue from  position X.