09-01-2014, 03:15 PM
Huffman Coding: An Application of Binary Trees and Priority Queues
An Application of Binary .ppt (Size: 334 KB / Downloads: 164)
Encoding and Compression of Data
Fax Machines
ASCII
Variations on ASCII
min number of bits needed
cost of savings
patterns
modifications
The Basic Algorithm
Huffman coding is a form of statistical coding
Not all characters occur with the same frequency!
Yet all characters are allocated the same amount of space
1 char = 1 byte, be it e or x
The (Real) Basic Algorithm
1. Scan text to be compressed and tally occurrence of all characters.
2. Sort or prioritize characters based on number of occurrences in text.
3. Build Huffman code tree based on prioritized list.
4. Perform a traversal of tree to determine all code words.
5. Scan text again and create new file using the Huffman codes.
Building a Tree
While priority queue contains two or more nodes
Create new node
Dequeue node and make it left subtree
Dequeue next node and make it right subtree
Frequency of new node equals sum of frequency of left and right children
Enqueue new node back into queue
Summary
Huffman coding is a technique used to compress files for transmission
Uses statistical coding
more frequently used symbols have shorter code words
Works well for text and fax transmissions
An application that uses several data structures