Algorithms For Dummies

  Working with Greedy Algorithms 

     297

        pair[1] = '1' 

+ pair[1]

    heappush(heap, [lo[0] 

+ hi[0]] + lo[1:] + hi[1:])

Step 1 1st:[145, ['G', '']] 2nd:[158, ['T', '']]

Step 2 1st:[292, ['C', '']] 2nd:[303, ['G', '0'],

 ['T', '1']]

Step 3 1st:[405, ['A', '']] 2nd:[595, ['C', '0'],

 ['G', '10'], ['T', '11']]

As the aggregations put the nucleotides together, which constitutes different lev-

els  of  the  unbalanced  tree,  their  Huffman  encoding  is  systematically  modified; 

adding a zero in front of the encoding of the lowest frequent aggregate and adding 

one to the second-lowest frequent one. In this way, the algorithm efficiently rep-

licates the unbalanced tree structure previously illustrated.

tree = sorted(heappop(heap)[1:], key=lambda p: (len(p[-

            1]), p))

print ("Symbol\tWeight\tCode")

for e in tree:

    print ("%s\t%s\t%s" % (e[0], frequencies[e[0]], e[1]))

Symbol   Weight   Code

A        405      0

C        292      10

G        145      110

T        158      111

The final step is to print the result, sorting it by the bit encoding and showing the 

final symbol table generated.

---

---

CHAPTER 16