Compression:
Introduction to The Huffman algorithm

By Bluefish@11a.nu.

Abstract

The Huffman algorithms are based around the idea that a datastream which is to be compressed contains a high frequence of certain character, while others are not so common. A character which is common is assigned a short path in a tree, while an uncommon character is assigned a longer path.

Similarities with Morse-codes and Huffman

An interresting fact is that the wildly known and used Morse-codes are based upon very similar ideas as the Huffman algorithms. (this paragraph given to aid understanding Huffman if you allready are familiar with Morse, if you aren't simply skip to the next paragraph)

• Both systems are binary: Huffman uses "left" and "right" (where "left" means "0", right means "1"). Morse uses two beeps, commonly written as "." and "-".
• Huffman gives the most common characters the shortest path. Morse has definied the shortest codes for the most commonly used english words.
• Huffman trees has values in leaves only. Morse has values in nodes and leaves also. Example: The morse code "." and ".-" exists. This is possible since each code is seperated by a short period of silence. This is not possible with Huffman, as the concept of silence is not known. Alas, if "0" is a path, "01" is the path "0" followed by the path "1".

Example of compression using a Huffman tree

Consider the message "ABBACCAAAAA". We find that we have seven "A", two "B" and two "C". As this message is so simple, we can design a suitable tree easily:

  +
 / \
A   +
   / \
  B   C

Why do we need the Huffman algorithm?

As seen the example, how to use the trees to compress a known data is quite simple. And, when creating small trees, you can find a good tree by simply guessing. However, what happens if you are i.e working on compressing a chineese book, and there are thousands of different characters used? Obviously, an algorithmic solution to find a good tree is needed. David A Huffman developed a algorithm which is rather simple for this purpose.

The Huffman Algorithm

In the algorithm, Huffman defines the concept of weight. A leaf has the same weight as the number of such characters to be compressed (thus, if there are 7 "A", "A" has the weight of 7. For a tree, the 'weight' is sum of all the leaves' weight. The Huffman algorithm can then be described in the following way:

  while not all trees are connected {
    take the tree with the least weight, 
    and combine it the tree with second least weight.
  }

Example #1 of Huffman algorithm for tree-generation

3A  4B  11C  23D  37E

  7     11C  23D  37E
 / \
A   B

    18       23D  37E
   /  \
  7    C
 / \
A   B

       41         37E
      /  \
    18    D
   /  \
  7    C
 / \
A   B

        78
       /  \
      41   E
     /  \
    18   D
   /  \
  7    C
 / \
A   B

Example #2 of Huffman algorithm for tree-generation

3A  4B  11C  16D  17E

  7     11C  16D  17E
 / \
A   B

    18       16D  17E
   /  \
  7    C
 / \
A   B

    18      33
   /  \    /  \
  7    C  D    E
 / \
A   B

        51 
      /    \
    18      33
   /  \    /  \
  7    C  D    E
 / \
A   B