Algorithms For Dummies

 

   

  PART 5 

 Challenging Difficult Problems

lowest left priority score, you obtain a best schedule that assures that you both 

minimize times and respect priorities: (30,4), (40,8), (10,3), (20,12).

Revisiting Huffman coding

As seen in the previous chapter, Huffman coding can represent data content in a 

more  compact  form  by  exploiting  the  fact  that  some  data  (for  instance  certain 

characters  of  the  alphabet)  appear  more  frequently  in  a  data  stream.  By  using 

encodings of different length (shorter for the most frequent characters, longer for 

the  least  frequent  ones),  the  data  consumes  less  space.  Prof.  Robert  M.  Fano 

(Huffman’s professor) and Claude Shannon already envisioned such a compres-

sion strategy but couldn’t find an efficient way to determine an encoding arrange-

ment that would make it impossible to mistake one character for another.

Prefix-free codes are necessary in order to avoid errors when decoding the mes-

sage. It means that no previously used bit encoding should be used as the starting 

point of another bit encoding. Huffman found a simple and workable solution for 

implementing  prefix-free  codes  using  a  greedy  algorithm.  The  solution  to  the 

prefix-free problem found by Huffman is to transform the originally balanced tree 

(a data structure discussed in Chapter 6) containing the fixed-length encoding 

into an unbalanced tree, as shown in Figure 15-1.

An unbalanced tree has a special characteristic that each node has only one branch 

that keeps on developing in other nodes and branches, whereas the other branch 

terminates with an encoded character. This characteristic assures that no previ-

ously  used  encoding  sequence  can  start  a  new  sequence  (graphically,  a  branch 

terminating with an encoded character is a dead end).

FIGURE 15-1: 

From a balanced 

tree (left) to an 

unbalanced tree 

(right).

---

CHAPTER 15