Data Compression Lec#8 PowerPoint

2- Huffman Coding
Huffman coding is a popular method for data compression. Its development, in 1952, by D. Huffman, this method has been the subject of intensive research into data compression.
The algorithm starts by building a list of all the alphabet symbols in descending order of their probabilities. It then constructs a tree, with a symbol at every leaf, from the bottom up. This is done in steps, where at each step the two symbols with smallest probabilities are selected, added to the top of the partial tree, deleted from the list, and replaced with an auxiliary symbol representing the two original symbols. When the list is reduced to just one auxiliary symbol (representing the entire alphabet), the tree is complete. The tree is then traversed to determine the codes of the symbols.
Example 1: Given five symbols {a1, a2, a3, a4, a5}with probabilities { 0.4, 0.2, 0.2, 0.1, 0.1} construct a set of Huffman codes.







0.4 0.2 0.2 0.1 0.1

Example 2: Derive a Huffman code for string "AAABEDBBTGGG".










3 3 3 1 1 1
G B A T D E



Exercise 1: Compress ‘BILL BEATS BEN.’ (15 characters in total) using the Huffman approach.






Exercise 2: Given seven symbols {a, b, c, d, e, f, g} with probabilities { 0.3, 0.2, 0.1, 0.1, 0.1, 0.1, 0.1} , construct a set of Huffman codes.