Algorithms For Dummies

  Compressing Data 

     275

The square nodes represent branch nodes, where the algorithm places the number 

of the remaining letters it distributes to the child nodes (those that are below the 

branch nodes in the hierarchy). The round nodes represent leaf nodes, where you 

find the successfully encoded letters. The tree starts at the root with 300 letters 

left to distribute (the length of the text). It distributes the letters by branching the 

0 and 1 bits, respectively, on the left and on the right branches until it reaches all 

the  leaves  necessary  for  encoding.  By  reading  from  the  top  of  the  sequence  of 

branches to a specific letter, you determine the binary sequence representing that 

letter. Less frequent letters (D and E) get the longest binary sequences.

Following the Huffman tree from bottom to top lets you compress a symbol into a 

binary sequence. By following the tree from top to bottom, you can decompress 

a  binary  sequence  into  a  symbol  (as  represented  by  the  first  leaf  node  you 

encounter).

For decompression, you need to store both the compressed binary sequence and 

the  Huffman  tree  that  made  the  compression  possible.  When  your  text  or  data 

is  too  short,  the  Huffman  tree  could  require  more  space  than  the  compressed 

data, thus making compression ineffective. Huffman code works best on larger 

data files.