Huffman

Document last modified:

To represent a 44 character message consisting of the 8-bit character frequencies below is 8*44=352 bits.

c m n o p q r s t

f(c) 3 5 9 4 2 7 6 8
Construct the optimal encoding for the character frequencies.
What is the savings of the optimal encoding over the 8-bit?

Huffman (C)
-- pre:  C is the characters that comprise the alphabet
-- post: return the root of the optimal encoding tree

   n ← |C|
   Q ← C    -- insert all the elements of C into Q, using the frequency as the priority
   for i ← 1 to n-1 do
		z ←  a new tree node
		x ←  Extract-Minimum (Q) 
		y ←  Extract-Minimum (Q)
		left[ z ] ←  x
		right[ z ] ← y
		f[z] ←  f[x] + f[y]
		Insert (Q, z)
   return Extract-Minimum (Q)        -- the root of the encoding tree

c	m	n	o	p	q	r	s	t
f(c)	3	5	9	4	2	7	6	8