# Implement the Huffman code in Python or Numpy?

The Huffman code is a way of compressing data streams by encoding the more frequent items with shorter words.

Here is a distribution on the letters A thru J and the code I obtained:

0.00066872  0.01864353  0.0474964   0.18568327  0.11587298
0.13329128  0.08580358  0.0881718   0.1847246   0.13964385


Notice that A is least frequent ant gets a word of length six, while I occurs more often and has length 2.

'B': '100011'
'A': '000011'
'D': '111'
'C': '10011'
'F': '001'
'E': '110'
'H': '010'
'G': '1011'
'J': '101'
'I': '00'


The Huffman algorithm builds a tree out of the different keys. From Pseudcode

• Begin with the set of leaf nodes, containing symbols and their frequencies, as determined by the initial data from which the code is to be constructed.

• Now find two leaves with the lowest weights and merge them to produce a node that has these two nodes as its left and right branches. The weight of the new node is the sum of the two weights. Remove the two leaves from the original set and replace them by this new node.

• Now continue this process. At each step, merge two nodes with the smallest weights, removing them from the set and replacing them with a node that has these two as its left and right branches.

### Pseudocode

Algorithm: HUFFMAN-TREE(C)

1. n ← |C|
2. Q ← C a min–priority queue keyed by frequency
3. for i ← 1 to n-1 do
4. Allocate new node z
5. z.left ← x ← EXTRACT-MIN(Q)
6. z.right ← y ← EXTRACT-MIN(Q)
7. z.freq ← x.freq ← y.freq
8. Q.INSERT(z)
9. B Return the root of the tree
10. return EXTRACT-MIN(Q)

Here's my implmentation in Python. It uses a lot of sorting and does not use any of the data types above. Is there a way to do it using numPy and/or priority queues?

f  = lambda a,b: int(100*(a-b))

p = np.random.random(10)*np.arange(10)+0.01
p = p/sum(p)
q = p
p = sorted([(str(x), x) for x in enumerate(p)], f)

code = { x: '' for x in p}

for k in range(10-1):
for x in p:
code[x] += '0'
for x in p:
code[x] += '1'

p = sorted(p[2:] + [(p+p, p+p)],f)

print q
print code


## 2 Answers

you can use http://docs.python.org/2/library/heapq.html as a priority queue

Are you looking for a fast implementation, or are you doing this to learn about Python/numPy/priority queues/Huffman codes?

There are a number of different implementations out there already: