Algorithms For Dummies

Encoding using Huffman compression

Redefining an encoding, such as when mapping nucleotides in DNA, is a smart 

move that works only when you use a part of the alphabet that the encoding rep-

resents. When you use all the symbols in the encoding, you can’t use this solution. 

David A. Huffman discovered another way to encode letters, numbers, and sym-

bols efficiently  even when  using all of them. He achieved this  accomplishment 

when  he was a student  at MIT in  1952 as part of a term paper required  by his 

professor,  Prof.  Robert  M.  Fano.  His  professor  and  another  famous  scientist, 

Claude Shannon (the father of information theory), had struggled with the same 

problem.

In his paper, “A Method for the Construction of Minimum-Redundancy Codes,” 

Huffman  describes  in  just  three  pages  his  mind-blowing  encoding  method. 

---

274

 

   

  PART 4