Data Compression Lec#6-2018

Statistical compression algorithms

2- Huffman Coding
Huffman coding is a popular method for data compression. It serves as the basis for several popular programs run on various platforms. Some programs use just the Huffman method, while others use it as one step in a multistep compression process. The Huffman method is somewhat similar to the Shannon-Fano method. It generally produces better codes, and like the Shannon-Fano method, it produces the best code when the probabilities of the symbols are negative powers of 2. The main difference between the two methods is that Shannon-Fano constructs its codes top to bottom (from the leftmost to the rightmost bits), while Huffman constructs a code tree from the bottom up (builds the codes from right to left). Since 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.
This process is best illustrated by an example. Given five symbols with probabilities as shown in Figure below, they are paired in the following order:
1. a4 is combined with a5 and both are replaced by the combined symbol a45, whose probability is 0.2.
2. There are now four symbols left, a1, with probability 0.4, and a2, a3, and a45, with probabilities 0.2 each. We arbitrarily select a3 and a45, combine them, and replace them with the auxiliary symbol a345, whose probability is 0.4.
3. Three symbols are now left, a1, a2, and a345, with probabilities 0.4, 0.2, and 0.4, respectively. We arbitrarily select a2 and a345, combine them, and replace them with the auxiliary symbol a2345, whose probability is 0.6.
4. Finally, we combine the two remaining symbols, a1 and a2345, and replace them with a12345 with probability 1.