Huffman Trees

Huffman Trees

• Each node has 0 or 2 children
• Only leaf nodes contain data
• Data in each leaf node is unique

Huffman Coding

• Basic compression
• Performs compression on characters (not entire words)
• Represent most frequent characters using shortest bit-length

Building a Huffman Tree

1. Create a table of values mapping characters to their frequencies
2. Create a priority queue where the key is the frequency and the data is the character (minimum values have higher priority)
3. Insert all of the values from the table into the priority queue
4. If the priority queue has a single element, you're done, this is the root of the tree
5. Poll the priority queue twice and create a binary tree with those nodes
6. Add the frequencies of the newly created tree and offer back to the priority queue
7. Return to step 4

Example / In Lab Discussion

• Create a Huffman tree for the data humuhumunukunukuapuaa

Character	Frequency
u	9
p	1
a	3
n	2
m	2
k	2
h	2

Huffman Coding with Tree

• Find the leaf with data for current character
• Starting from the root, traverse to the leaf node with data for current character
• If you take a left subtree, record a 0 bit
• If you take a right subtree, record a 1 bit

Example / In Lab Discussion

• Find the encoding for the previous tree

Character	Encoding
u	0
h	100
a	101
p	1100
n	1101
m	1110
k	1111

Example / In Lab Discussion

• Now that we know how to code each character, we can encode the entire message
• Using the previous coding, encode humuhumunukunukuapuaa

h   u m    u h   u m    u n    u k    u n    u k    u a   p    u a   a
100 0 1110 0 100 0 1110 0 1101 0 1111 0 1101 0 1111 0 101 1100 0 101 101

• But really, there are no spaces

h  um   uh  um   un   uk   un   uk   ua  p   ua  a
1000111001000111001101011110110101111010111000101101

Compression: How much space did we save?

• Depends on how strings are encoded
• If using ASCII each character can be represented using two hex digits
• Each hex digit is represented by a nibble (4 bits)
• So two hex digits give us a byte (8 bits)
• Therefore, in ASCII, it takes 8 bits to store a single character
• humuhumunukunukuapuaa => 21 characters => 21 * 8 bits => 168 bits => 21 bytes
• Our Huffman encoded string is only 52 bits (7 bytes)
• However, this does not account for storing the Huffman tree
• Larger strings produce better compression

Decoding Huffman Coded Message

• Given a Huffman tree, it's easy to decode a message
• Starting at the root node, go left on a 0 bit and right on a 1 bit
• If you hit a leaf node, record the data and start back over at the root for the next bit

Another Example for Building a Huffman Tree

• Easy to follow example on how to apply method to create Huffman Tree @ (http://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=17&ved=0CDsQFjAGOAo&url=http%3A%2F%2Fwww.cs.nyu.edu%2F~melamed%2Fcourses%2F102%2Flectures%2Fhuffman.ppt&ei=tAqsUtGWL8XcoATa7IKADA&usg=AFQjCNGyVG_6cVLhPE1W8ICZaDhLbT6Lyw)

Example / In Lab Discussion

• Decode the following coded message using the following tree
• 1001110010111000111

Example / Do It Yourself

• Encode the the string firefighting fireflies (show final Huffman tree)
• Decode the following encoded string using the following tree
• 1110100110110011100010