Huffman Code
Notes
- Huffman code is constructed by
- Making all symbols unique trees
- Selecting the two symbols with the lowest frequency and combining those into a new tree, with the symbols as children.
- Continue this process until only a single tree remains.
- Since traversing a tree from the root to a leaf indicates the encoding for a symbol
- The lowest frequency symbols will have the longest path
- And hence the longest encoding
- And the opposite for the most frequently used symbols.
- The greedy choice is to select the lest frequently used trees and unite them,
- This is prefix-free as the symbols will always be leaves.
- The algorithm
HUFFMAN(Σ) Input: Σ An alphabet with associated symbols and frequency Output: A prefix-free tree with minimal encoding costs.- n ← |Σ|
- Q ← Σ // note Q is a min-heap
- for i ← 1 to n-1 do
- allocate a new node z
- z.left = x = Q.ExtractMin()
- z.right = y = Q.ExtractMin()
- z.frequency = x.frequency + y.frequency
- Q.Insert(z)
- return Q.ExtractMin()
- This is from CLRS
- What is the performance?
- Line 2 is O(n) where n = |Σ|
- The loop in 3 is also O(n) but is the body O(1)?
- Remember, with a heap, ExtractMin, and Insert are both O(log2n)
- So the loop in 3-8 is O(n log2 n)
- Try this with : e 12.7%, t 9.1%, a 8.2% o 7.5%, i 7.0%
- Q: i-7, o-7.5, a-8.2, t-9.1, e-12.7
- Q: a-8.2, t-9.1, e-12.7, A-14.5:i-7:o-7.5
- Q: e-12.7, A-14.5:i-7:o-7.5, B-17.3:a-8.2:t-9.1
- Q: B-17.3:a-8.2:t-9.1, C-27.2:e-12.7:A-14.5:i-7:o-7.5
- Q D-44.5: B-17.3:a-8.2:t-9.1:C-27.2:e-12.7:A-14.5:i-7:o-7.5