6.046J Lecture 19: Compression and Huffman Coding

Lecture 19 Compression and Huffman Coding Supplemental reading in CLRS: Section 16.3 19.1 Compression As you probably know at this point in your career, compression is a tool used to facilitate storing large data sets. There are two different sorts of goals one might hope to achieve with compression: • Maximize ease of access, manipulation and processing • Minimize size—especially important when storage or transmission is expensive. Naturally, these two objectives are often at odds with each other. In this lecture we will focus on the second objective. In general, data cannot be compressed. For example, we cannot losslessly represent all m-bit strings using (m − 1)-bit strings, since there are 2m possible m-bit strings and only 2m−1 possible (m − 1)-bit strings. So when is compression possible? • If only a relatively small number of the possible m-bit strings appear, compression is possible. • If the same “long” substring appears repeatedly, we could represent it by a “short” string. • If we relax the requirement that every string have a unique representation, then compression might work but make “similar” strings identical. 19.1.1 Lossless and lossy Initial Compressed Reconstituted Compress Decompress Document −−−−−−−−−−−→ Document −−−−−−−−−−−−→ Document D C D0 In lossless compression, we require that D = D 0 . This means that the original document can always be recovered exactly from the compressed document. Examples include: • Huffman coding • Lempel–Ziv (used in gif images) In lossy compression, D 0 is close enough but not necessarily identical to D. Examples include: • mp3 (audio) • jpg (images) • mpg (videos) 19.1.2 Adaptive and non-adaptive Compression algorithms can be either adaptive or non-adaptive. • Non-adaptive – assumes prior knowledge of the data (e.g., character frequncies). • Adaptive – assumes no knowledge of the data, but builds such knowledge. 19.1.3 Framework For the remainder of this lecture, we consider the following problem: Input: Known alphabet (e.g., English letters a,b,c,. . . ) Sequence of characters from the known alphabet (e.g., “helloworld”) We are looking for a binary code—a way to represent each character as a binary string (each such binary string is called a codeword). Output: Concatenated string of codewords representing the given string of characters. 19.1.4 Fixed-length code In a fixed-length code, all codewords have the same length. For example, if our alphabet is © ª a, b, c, d, e, f, g, h , then we can represent each of the 8 characters as a 3-bit string, such as   b c d e f g h   a ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ .   000 001 010 011 100 101 110 111 Such a code is easy to encode and decode: ¯ ¯ ¯ baba = 001¯000¯001¯000 Just as in DNA encoding and decoding, it is important to keep track of register: the deletion or insertion of a single bit into the binary sequence will cause a frame shift, corrupting all later characters in the reconstituted document. 19.1.5 Run-length encoding Imagine you are given the string of bits 111 |{z} 000 |{z} 11 00000 000000 | {z } . | {z } |{z} 6 3 3 2 5 Rather than create codewords, we could simply store this string of bits as the sequence 〈6, 3, 3, 2, 5〉. This strategy is used in fax-machine transmission, and also in jpeg. Lec 19 – pg. 2 of 7 19.1.6 Variable-length code If we allow our codewords to have different lengths, then there is an obvious strategy: Use shorter codewords for more frequent characters; use longer codewords for rarer characters. For example, consider a six-letter alphabet with the following character frequencies: Character Frequency Codeword a 45% 0 (1 bit) b 13% 101 c d 12% 16% 100 111 (3 bits) e f 9% 5% 1101 1100 (4 bits) Using this code, the average number of bits used to encode 100 characters is (45)1 + (13)3 + (12)3 + (16)3 + (9)4 + (5)4 = 224. Compare this to a 3-bit fixed-length code, in which it would take 300 bits to encode 100 characters. Notice that I didn’t use 1, 01, or 10 as codewords, even though they would have made the encoding shorter. The reason for this is that we want our code to be uniquely readable: it should never be ambiguous as to how to decode a compressed document.1 One standard way to make uniquely readable codes is to use prefix coding: no codeword occurs as a prefix (initial substring) of another codeword. This allows unambiguous, linear-time decoding: 101 111 1100 0 100 1101 d b a f c e Prefix coding means that we can draw our code as a binary tree, with the leaves representing codewords (see Figure 19.1). 19.2 The Huffman Algorithm The problem of §19.1.3 amounts to the following. We are given an alphabet {a i } with frequencies © ª © ª f (a i ) . We wish to find a set of binary codewords C = c(a 1 ), . . . , c(a n ) such that the average number of bits used to represent the data is minimized: B(C) = n X ¯ ¯ f (a i ) ¯ c(a i )¯ . i =1 Equivalently, if we represent our code as a tree T with leaf nodes a 1 , . . . , a n , then we want to minimize B(T) = n X f (a i ) d(a i ), i =1 where d(a i ) is the depth of a i , which is also equal to the number of bits in the codeword for a i . The following algorithm, due to Huffman, creates an optimal prefix tree for a given set of characters C = {a i }. Actually, the Huffman code is optimal among all uniquely readable codes, though we don’t show it here. 1 For an example of non-unique readibility, suppose we had assigned to “d” the codeword 01 rather than 111. Then the string 0101 could be decoded as either “ab” or “dd.” Lec 19 – pg. 3 of 7 100% 0 1 45% 55% a=0 0 1 25% 0 30% 1 12% 0 13% c = 100 1 14% 16% b = 101 d = 111 0 1 5% 9% f = 1100 e = 1101 Figure 19.1. Representation of a binary code as a binary tree. Algorithm: H UFFMAN -T REE(C) 1 2 3 4 5 6 7 8 9 10 19.2.1 n ← |C | Q ← C B a min–priority queue keyed by frequency for i ← 1 to n − 1 do Allocate new node z z.left ← x ← E XTRACT-M IN(Q) z.right ← y ← E XTRACT-M IN(Q) z.freq ← x.freq + y.freq Q.I NSERT(z) B Return the root of the tree return E XTRACT-M IN(Q) Running time Initially, we build a minqueue Q with n elements. Next, the main loop runs n − 1 times, with each iteration consisting of two E XTRACT-M IN operations and one I NSERT operation. Finally, we call E XTRACT-M IN one last time; at this point Q has only one element left. Thus, the running time for Q a binary minheap would be Θ (n) | {z } B UILD -Q UEUE + Θ (n lg n) + | {z } Loop O(1) | {z } = Θ (n lg n) . E XTRACT-M IN If instead we use a van Emde Boas structure for Q, we achieve the running time Θ (n lg lg n) . Lec 19 – pg. 4 of 7 f: 5% e: 9% c: 12% b: 13% c: 12% b: 13% 14% c: 12% 25% c: 12% d: 16% a: 45% a: 45% 25% d: 16% e: 9% f: 5% a: 45% e: 9% f: 5% 14% d: 16% b: 13% 30% a: 45% 14% b: 13% f: 5% d: 16% e: 9% a: 45% 55% 25% 30% c: 12% 14% b: 13% f: 5% d: 16% e: 9% 100% a: 45% 55% 25% c: 12% 30% 14% b: 13% f: 5% d: 16% e: 9% Figure 19.2. Example run of the Huffman algorithm. The six rows represent the state of the graph each of the six times line 3 is executed. Lec 19 – pg. 5 of 7 x y a y a b T a b x b T0 y x T 00 Figure 19.3. Illustration of the proof of Lemma 19.1. 19.2.2 Correctness The Huffman algorithm is a greedy algorithm: at each stage, we merge together the two nodes of lowest frequency. Lemma 19.1 (CLRS Lemma 16.2). Suppose x, y are the two most infrequent characters of C (with ties broken arbitrarily). Then there exists an optimal prefix code for C with codewords for x and y of the same length and differing only in the last bit. (In other words, there exists an optimal tree in which x and y are siblings.) Proof. Let T be an optimal tree. Let a be a leaf of maximal depth. If a has no sibling, then deleting a from the tree (and using a’s parent to represent the character formerly represented by a) produces a better code, contradicting optimality. So a has a sibling b, and since a has maximum depth, b is a leaf. So a and b are nodes of maximal depth, and without loss of generality we can say a.freq ≤ b.freq. Also without loss of generality, say x.freq ≤ y.freq. Switch the leaves a and x; call the resulting tree T 0 (see Figure 19.3). Then B(T 0 ) ≤ B(T), seeing as x.freq ≤ a.freq. So it must be the case that x.freq = a.freq and T 0 is optimal as well. Similarly, switch the leaves b and y in T 0 ; call the resulting tree T 00 . It must be the case that y.freq = b.freq and T 00 is optimal. In T 00 , the leaves x and y are siblings. Lemma 19.2 (CLRS Lemma 16.3). Given an alphabet C, let: • • • • x, y be the two most infrequent characters in C (with ties broken arbitrarily) z be a new symbol, with z.freq ← x.freq + y.freq ¡ ¢ C 0 = C \ { x, y} ∪ { z} T 0 be an optimal tree for C 0 . Then T is an optimal tree for C, where T is a copy of T 0 in which the leaf for z has been replaced by an internal node having x and y as children. Proof. Suppose T is not optimal. By Lemma 19.1, let T be an optimal tree for C in which x and y are siblings. Delete x and y from T , and label their parent (now a leaf) with the symbol z. Call the Lec 19 – pg. 6 of 7 resulting tree T 0 . Notice that T 0 is a tree for C 0 , and furthermore, B(T 0 ) = B(T ) − x.freq − y.freq < B(T) − x.freq − y.freq = B(T 0 ). This contradicts the optimality of T 0 . We conclude that T must have been optimal in the first place. Corollary 19.3. The Huffman algorithm is correct. Proof sketch. Let T be the tree produced by the Huffman algorithm. Construct a new tree U as follows. Initially, let U consist of just one vertex. Then, perform a series of transformations on U. In each transformation, append two children to what was previously a leaf node. In this way, we can eventually transform U into T. Moreover, Lemma 19.2 guarantees that, at each stage, U is an optimal tree for the alphabet formed by its leaves. Lec 19 – pg. 7 of 7