Priority Queues Applications

Data Compression: Huffman Code

Task: encoding strings ("messages") of symbols (digits)

Suppose we want to obtain an optimal set of codes for messages. Each code is a binary string that will be used for transmission of the corresponding message.

At the receiving end the code will be decoded using a decode tree.

A decode tree is a binary tree in which the external nodes represent messages. The binary bits in the code word for a message determine the branching needed at each level of the decode tree to reach the external node.

This represents a decoded tree with

• M1 000
• M2 001
• M3 01
• M4 1

Therefore what we want to minimize is P(i) L(i)

Intuitively, the most common message should be the shortest

Notice how no message begins with a 1 except M4

This is the "trick"

What would message M4M4 be?

Suppose we had messages of yes, no, maybe and repeat and consider the following codes:

Message	P(i)	code	P(i)L(i)
yes	.50	00	1.00
no	.40	01	.80
maybe	.09	10	.18
repeat	.01	11	.02

The P(i) L(i) = 2.00 this is not very low, but the messages are easy to parse

YNYYMRN would be ?

Messages are delimited in a fixed manner.

Now consider:

Message	P(i)	code	P(i)L(i)
yes	.50	0	1.00
no	.40	10	.80
maybe	.09	110	.27
repeat	.01	111	.03

The P(i) L(i) = 1.60 smaller and still easy to parse.

Consider the same message: YNYYMRN

What is it? Pictorially:

The idea here is to have instantaneous codes. Messages are delimited in a variable manner however no good digit sequence can be the prefix of a longer good one.

For example

Y 0
N 01
M 011
R 010

is not good. Why?

Technique to determine code: (binary version so d = 0,1)

Notice: the two least probable codes will be the longest and they will differ in their final digit

Conclude: the least probable will be of the form ddd...d1 and the second least will be of form ddd...d0

The probability of either of the last two is the probability of their sum, i.e., P(n-1 U n) equals P(n) + P(n-1)

Now for the important part:
If we combine these last two and repeat this process we can build the code.

Specifically, at this time we have

yes	P =.50
no	P = .40
maybe/repeat	P = .10 (.09 +.01)

Do it again (i.e., repeat until one message keeping track of P)

yes	.50		yes	.50		yes   .50		y/n/m/r    1.0
no	.40		no	.40 		n/m/r .50
maybe	.09		m/r 	.10
repeat	.01		

So

yes	.50			yes			yes	0	
no	.40			no	--0 		n/m/r 	1
maybe	.09 ---0		m/r 	--1
repeat	.01 ---1		

Probabilities with the same value can go either way - they will result in codes with the same average length.

The most compression (obviously) occurs when probabilities are lopsided.

Consider a file with predominately numeric data and some variables:

_  .30 	        _  .30		_  .30		_   .30		_       .30	023    .40
0  .20		0  .20		0  .20		0   .20		1abc  	.30	 -     .30	
1  .15		1  .15		1  .15		23  .20	    	0 	.20	1abc   .30
2  .10		2  .10		abc.15		1   .15		23 	.20		
3  .10		3  .10		2  .10		abc .15 				
a  .08		a  .08		3  .10
b  .04		bc .07
c  .03

The text notes are on page 534 and discuss the diagram Figure 13.11 for Constructing a Huffman tree.