18.310 Lecture Notes: Huffman Codes

18.310 lecture notes Huffman Codes Shannon’s noiseless coding theorem tells us how compactly we can compress messages in which all letters are drawn independently from an alphabet A and we are given the probability pa of each letter a ∈ A appearing in the message. Shannon’s theorem says that, for random messages with n  letters, the expected number of bits we need to transmit is at least nH(p) = −n a∈A pa log2 pa bits, and there exist codes which transmit an expected number of bits of just o(n) beyond this lower bound of nH(p) (recall that o(n) means that this function satisfies that o(n) n tends to 0 as n tends to infinity). We will see now a very efficient way to construct a code that almost achieves this Shannon lower bound. The idea is very simple. To every letter in A, we assign a string of bits. For example, we may assign 01001 to a, 100 to d and so on. ’dad’ would then be encoded as 10001001100. But to make sure that it is easy to decode a message, we make sure this gives a prefix code. In a prefix code, for any two letters x in y of our alphabet the string corresponding to x cannot be a prefix of the string corresponding to y and vice versa. For example, we would not be allowed to assign 1001 to c and 10010 to s. There is a very convenient way to describe a prefix code as a binary tree. The leaves of the tree contain the letters of our alphabet, and we can read off the string corresponding to each letter by looking at the path from the root to the leaf corresponding to this letter. Every time we go to the left child, we have 0 as the next bit, and every time we go to the right child, we get a 1. For example, the following tree for the alphabet A = {a, b, c, d, e, f }: a d b e c f corresponds to the prefix code: a b c d e f 10 000 110 01 001 111 The main advantage of a prefix code is that it is very to decode a string of bits by just repeatedly marching down this tree from the root until one reaches a leaf. For example, to decode 1111001001, we march down the tree and see that the first 3 bits correspond to f , then get a for the next 2 bits, then d and then e, and thus our string decodes to ’fade’. Our goal now is to design a prefix code which minimizes the expected number of bits we transmit. If we encode letter a with a bit string of length la , the expected length for encoding one letter is  L= pa l a , a∈A and our goal is to minimize this quantity L over all possible prefix codes. By linearity of expectations, encoding a message n letters then results in a bit strength of expected length n a∈A pa la . We’ll show now an optimal prefix code and this is known as the Huffman code, based on the name of the MIT graduate student who invented it in 1952. As we derive it in its full generality, we will also consider an example to illustrate it. Suppose our alphabet is {a, b, c, d, e, f } and the probabilities for each letter are: a 0.40 b 0.05 c 0.18 d 0.07 e 0.20 f 0.10 Let us assume we know an optimum prefix code; letter a is encoded with string sa of length la for any letter a of our alphabet. First, we can assume that, in this optimum prefix code, the letter with smallest probability, say b as in our example (with probability 0.05) corresponds to one of the longest strings. Indeed, if that is not the case, we can keep the same strings but just interchange the string sb with the longest string, and decrease the expected length of an encoded letter. If we now look at the parent of b in the tree representation of this optimum prefix code, this parent must have another child. If not, the last bit of sb was unnecessary and could be removed (thereby decreasing the expected length). But, since b corresponds to one of the longest strings, that sibling of b in the tree representation must also be a leaf and thus correspond to another letter of our alphabet. By the same interchange argument as before, we can assume that this other letter has the second smallest probability, in our case it is d with probability 0.07. Being siblings mean that the strings sb and sd differ only in the last bit. Thus, our optimum prefix code can be assumed to have the following subtree: b d Now suppose we replace b and d (the two letters with smallest probabilities) by one new letter, say α with probability pα = pb + pd (in our case pα = 0.12). Our new alphabet is thus A = A \ {b, d} ∪ {α}. In our example, we have: a c e f α 0.40 0.18 0.20 0.10 0.12 = pb + pd and given our prefix code for A, we can easily get one for A by simply encoding this new letter α with the lb − 1 = ld − 1 common bits of sb and sd . This corresponds to replacing in the tree, the subtree b d by α In this prefix code for A , we have lα = lb − 1 = ld − 1. Thus, if we denote by L and L , the expected length for our prefix codes for A and A , observe that L = L − pα . On the other hand, if one considers any prefix code for A , it is easy to get a prefix code for A such that L = L + pα by simply doing the reverse transformation. This shows that the prefix code for A must be optimal as well. But, now, we can repeat the process. For A , the two letters with smallest probabilities are in our example f (pf = 0.1) and α (pα = 0.12), and thus they must correspond to the subtree: α f Expanding the tree for α, we get that one can assume that the following subtree is part of an optimum prefix code for A: f b d We can now aggregate f and α (i.e. f , b and d), into a single letter β with pβ = pf + pα = 0.22. Our new alphabet and corresponding probabilities are therefore: a c e β 0.40 0.18 0.20 0.22 = pf + pα = pf + pb + pd This process can be repeated and leads to the Huffman code. At every stage, we take the two letters, say x and y, with smallest probabilities of our new alphabet and replace them by a new letter with probability px + py . At the end, we can unravel our tree representation to get an optimal prefix code. Continuing the process with our example, we get the sequence of alphabets: a 0.40 β 0.22 = pf + pα = pf + pb + pd γ 0.38 = pc + pe then a 0.40 δ 0.60 = pβ + pγ = pf + pb + pd + pc + pe and then  1 = pa + pδ = pa + pb + pc + pd + pd + pe + pf . We can do the reverse process to get an optimum prefix code for A. First, we have:  then a δ then a β γ β γ then a then a β c e f α c e f c e then a and finally: a b This corresponds to the prefix code: a b c d e f 0 1010 110 1011 111 100 d The expected number of bits per letter is thus  pa la = 0.40 · 1 + 0.05 · 4 + 0.18 · 3 + 0.07 · 4 + 0.2 · 3 + 0.1 · 3 = 2.32. a∈A This is to be compared to Shannon’s lower bound of  − pa log2 (pa ) = 2.25, · · · a∈A and the trivial upper bound of log2 (|A|) = 2.58 · · · . We will now show that Huffman coding is always close to the Shannon bound, no matter how large our alphabet A is and our choice of probabilities. Our first lemma (known as Kraft’s inequality) gives an inequality for the depths of the leaves of a binary tree. Lemma 1 (Kraft’s inequality). Let l1 , l2 , · · · , lk ∈ N. Then there exists a binary tree with k leaves at distance (depth) li for i = 1, · · · k from the root if and only if k  2−li ≤ 1. i=1 Prove this lemma (for example by induction) as an exercise. With this lemma, we have now the required tools to show that Huffman coding is always within 1 bit per letter of the Shannon bound. Theorem 1. Let A be an alphabet, and let pa for a ∈ A denote the probability of occurrence of letter a ∈ A. Then, Huffman coding gives an expected length L per letter satisfying: H(p) ≤ L ≤ H(p) + 1. Proof. The first inequality follows from Shannon’s noiseless coding theorem. To prove the second inequality, define la = − log2 (pa ), for a ∈ A. Notice that la is an integer for every a. Furthermore, we have that     2−− log2 (pa ) ≤ 2log2 pa = pa = 1. 2−la = a∈A a∈A a∈A a∈A Thus, by Kraft’s inequality, there exists a binary tree with |A| leaves and the corresponding prefix tree has a string of length la for a ∈ A. As we have argued that the Huffman code gives the smallest possible expected length, we get that  L ≤ p a la a∈A =  pa − log2 (pa ) a∈A ≤  pa (1 − log2 pa ) a∈A = H(p) + 1. This proves the theorem.