How to Compress Data Using Huffman Encoding

Article provided by wikihow the wikihow manual.

Huffman's algorithm is used construct a tree that is used for data compression as well as encryption. We'll discuss how to construct the tree here.

We'll assume that each character has an associated weight equal to the number of times the character occurs in a file, for example. In the "go go gophers" example, the characters 'g' and 'o' have weight 3, the space has weight 2, and the other characters have weight 1. When compressing a file we'll need to calculate these weights, we'll ignore this step for now and assume that all character weights have been calculated. Huffman's algorithm assumes that we're building a single tree from a group (or forest) of trees. Initially, all the trees have a single node with a character and the character's weight. Trees are combined by picking two trees, and making a new tree from the two trees. This decreases the number of trees by one at each step since two trees are combined into one tree. The algorithm is as follows:

Steps

1. 1
   Begin with a forest of trees. All trees are one node, with the weight of the tree equal to the weight of the character in the node. Characters that occur most frequently have the highest weights. Characters that occur least frequently have the smallest weights.

   
   
2. 2
   Repeat this step until there is only one tree:
3. 3
   Choose two trees with the smallest weights, call these trees T1 and T2. Create a new tree whose root has a weight equal to the sum of the weights T1 + T2 and whose left subtree is T1 and whose right subtree is T2.
4. 4
   The single tree left after the previous step is an optimal encoding tree.

5. Article provided by wikihow the wikihow manual. Please edit this article and find author credits at the original wikiHow article on How to Compress Data Using Huffman Encoding. All content on wikiHow can be shared under a Creative Commons license.