Source code online books for professionals by professionals

Figure 7-2.  A Huffman tree for a–i, with frequencies/weights 4, 5, 6, 9, 11, 12, 15, 16, and 20, and the path represented 
by the code 101 (right, left, right) highlighted

---

Chapter 7 
■
 Greed Is Good? prove It! 
146
Here’s an example of how you might use the code:
 
>>> seq = "abcdefghi"
>>> frq = [4, 5, 6, 9, 11, 12, 15, 16, 20]
>>> huffman(seq, frq)
[['i', [['a', 'b'], 'e']], [['f', 'g'], [['c', 'd'], 'h']]]
A few details are worth noting in the implementation. One of its main features is the use of a heap (from 
heapq). Repeatedly selecting and combining the two smallest elements of an unsorted list would give us a quadratic 
running time (linear selection time, linear number of iterations), while using a heap reduces that to loglinear 
(logarithmic selection and re-addition). We can’t just add the trees directly to the heap, though; we need to make 
sure they’re sorted by their frequencies. We could simply add a tuple, (freq, tree), and that would work as long as 
all frequencies (that is, weights) were different. However, as soon as two trees in the forest have the same frequency, 
the heap code would have to compare the trees to see which one is smaller—and then we’d quickly run into 
undefined comparisons.
Note
 
■
  In python 3, comparing incompatible objects like 
["a", ["b", "c"]]
 and 
"d"
 is not allowed and will raise 
a 
TypeError
. In earlier versions, this was allowed, but the ordering was generally not very meaningful; enforcing more 
predictable keys is probably a good thing either way.
A solution is to add a field between the two, one that is guaranteed to differ for all objects. In this case, I simply 
use a counter, resulting in (freq, num, tree), where frequency ties are broken using the arbitrary num, avoiding direct 
comparison of the (possibly incomparable) trees.
6
 
As you can see, the resulting tree structure is equivalent to the one shown in Figure 
7-2
.
To compress and decompress a text using this technique, you need some pre- and post-processing, of course. 
First, you need to count characters to get the frequencies (for example, using the Counter class from the collections 
module). Then, once you have your Huffman tree, you must find the codes for all the characters. You could do this 
with a simple recursive traversal, as shown in Listing 7-2.