Huffman Coding

Huffman Coding

This is an important and widely-used example of a statistical compression algorithm. As with all such algorithms the basic idea is to identify those data items (symbols) that appear most frequently and give them the shortest codes.
This is achieved by first creating a binary tree as follows...
1. Rank the symbols by their frequency (which should sum
to 1) and create a node for each symbol.
2. Create a new node by joining the two lowest ranked
nodes and summing their rankings together.
3. Continue until all nodes on the tree are joined to create
a single node of rank 1.

Binary tree example:

Having obtained the binary tree it is now possible to
calculate the Huffman code for each symbol...
1. Starting at the root assign 0 to the branch with the
higher value and 1 to the branch with the lower value.
2. Once the tree is traversed the code for each symbol
may be obtained by following the path from the root to
that symbol.
This ensures that that the highest frequency symbols have
the shortest codes and that a continuous stream of
encoded bits may be uniquely decoded.

To illustrate how codes are assigned: