2
$\begingroup$

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[1]-b[1]))

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

code = { x[0]: '' for x in p}


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

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

print q
print code
$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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:

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.