Introduction to Algorithms. (2nd edition) Thomas Cormen_ Charles Leiserson_ Ronad Rivest (811417), страница 75
Текст из файла (страница 75)
The for loop in lines 3–8repeatedly extracts the two nodes x and y of lowest frequency from the queue, and replacesthem in the queue with a new node z representing their merger. The frequency of z iscomputed as the sum of the frequencies of x and y in line 7. The node z has x as its left childand y as its right child.
(This order is arbitrary; switching the left and right child of any nodeyields a different code of the same cost.) After n - 1 mergers, the one node left in the queue—the root of the code tree—is returned in line 9.The analysis of the running time of Huffman's algorithm assumes that Q is implemented as abinary min-heap (see Chapter 6). For a set C of n characters, the initialization of Q in line 2can be performed in O (n) time using the BUILD-MIN-HEAP procedure in Section 6.3.
Thefor loop in lines 3–8 is executed exactly n - 1 times, and since each heap operation requirestime O (lg n), the loop contributes O (n lg n) to the running time. Thus, the total running timeof HUFFMAN on a set of n characters is O (n lg n).Correctness of Huffman's algorithmTo prove that the greedy algorithm HUFFMAN is correct, we show that the problem ofdetermining an optimal prefix code exhibits the greedy-choice and optimal-substructureproperties. The next lemma shows that the greedy-choice property holds.Lemma 16.2Let C be an alphabet in which each character c C has frequency f [c]. Let x and y be twocharacters in C having the lowest frequencies.
Then there exists an optimal prefix code for Cin which the codewords for x and y have the same length and differ only in the last bit.Proof The idea of the proof is to take the tree T representing an arbitrary optimal prefix codeand modify it to make a tree representing another optimal prefix code such that the charactersx and y appear as sibling leaves of maximum depth in the new tree. If we can do this, thentheir codewords will have the same length and differ only in the last bit.Let a and b be two characters that are sibling leaves of maximum depth in T. Without loss ofgenerality, we assume that f[a] ≤ f[b] and f[x] ≤ f[y].
Since f[x] and f[y] are the two lowest leaffrequencies, in order, and f[a] and f[b] are two arbitrary frequencies, in order, we have f [x] ≤f[a] and f[y] ≤ f[b]. As shown in Figure 16.6, we exchange the positions in T of a and x toproduce a tree T′, and then we exchange the positions in T′ of b and y to produce a tree T″. Byequation (16.5), the difference in cost between T and T′ isFigure 16.6: An illustration of the key step in the proof of Lemma 16.2. In the optimal tree T,leaves a and b are two of the deepest leaves and are siblings. Leaves x and y are the twoleaves that Huffman's algorithm merges together first; they appear in arbitrary positions in T .Leaves a and x are swapped to obtain tree T′. Then, leaves b and y are swapped to obtain treeT″. Since each swap does not increase the cost, the resulting tree T″ is also an optimal tree.because both f[a] - f[x] and dT (a) - dT (x) are nonnegative.
More specifically, f[a] - f[x] isnonnegative because x is a minimum-frequency leaf, and dT (a) - dT (x) is nonnegativebecause a is a leaf of maximum depth in T. Similarly, exchanging y and b does not increasethe cost, and so B(T′) - B(T″) is nonnegative. Therefore, B(T″) ≤ B(T), and since T is optimal,B(T) ≤ B(T″), which implies B(T″) = B(T). Thus, T″ is an optimal tree in which x and y appearas sibling leaves of maximum depth, from which the lemma follows.Lemma 16.2 implies that the process of building up an optimal tree by mergers can, withoutloss of generality, begin with the greedy choice of merging together those two characters oflowest frequency.
Why is this a greedy choice? We can view the cost of a single merger asbeing the sum of the frequencies of the two items being merged. Exercise 16.3-3 shows thatthe total cost of the tree constructed is the sum of the costs of its mergers. Of all possiblemergers at each step, HUFFMAN chooses the one that incurs the least cost.The next lemma shows that the problem of constructing optimal prefix codes has the optimalsubstructure property.Lemma 16.3Let C be a given alphabet with frequency f[c] defined for each character c C. Let x and y betwo characters in C with minimum frequency.
Let C′ be the alphabet C with characters x, yremoved and (new) character z added, so that C′ = C - {x, y} {z}; define f for C′ as for C,except that f[z] = f[x] + f[y]. Let T′ be any tree representing an optimal prefix code for thealphabet C′. Then the tree T, obtained from T′ by replacing the leaf node for z with an internalnode having x and y as children, represents an optimal prefix code for the alphabet C.Proof We first show that the cost B(T) of tree T can be expressed in terms of the cost B(T′) oftree T′ by considering the component costs in equation (16.5). For each c C - {x, y}, wehave dT (c) = dT′ (c), and hence f[c]dT(c) = f[c]d′(c).
Since dT (x) = dT (y) = d′(z) + 1, we havef[x]dT (x) + f[y]dT (y) = (f[x] + f[y])(d′ (z) + 1)= f[z]d′(z) + (f[x] + f[y]),from which we conclude thatB(T) = B(T′) + f[x] + f[y]or, equivalently,B(T′) = B(T) - f[x] - f[y].We now prove the lemma by contradiction. Suppose that T does not represent an optimalprefix code for C. Then there exists a tree T″ such that B(T″) < B(T). Without loss ofgenerality (by Lemma 16.2), T″ has x and y as siblings.
Let T′′′ be the tree T″ with thecommon parent of x and y replaced by a leaf z with frequency f[z] = f[x] + f[y]. ThenB(T‴) = B(T″) - f[x] - f[y]< B(T) - f[x] - f[y]= B(T′),yielding a contradiction to the assumption that T′ represents an optimal prefix code for C′.Thus, T must represent an optimal prefix code for the alphabet C.Theorem 16.4Procedure HUFFMAN produces an optimal prefix code.Proof Immediate from Lemmas 16.2 and 16.3.Exercises 16.3-1Prove that a binary tree that is not full cannot correspond to an optimal prefix code.Exercises 16.3-2What is an optimal Huffman code for the following set of frequencies, based on the first 8Fibonacci numbers?a:1 b:1 c:2 d:3 e:5 f:8 g:13 h:21Can you generalize your answer to find the optimal code when the frequencies are the first nFibonacci numbers?Exercises 16.3-3Prove that the total cost of a tree for a code can also be computed as the sum, over all internalnodes, of the combined frequencies of the two children of the node.Exercises 16.3-4Prove that if we order the characters in an alphabet so that their frequencies are monotonicallydecreasing, then there exists an optimal code whose codeword lengths are monotonicallyincreasing.Exercises 16.3-5Suppose we have an optimal prefix code on a set C = {0, 1, ..., n - 1} of characters and wewish to transmit this code using as few bits as possible.
Show how to represent any optimalprefix code on C using only 2n - 1 + n ⌈lg n⌉ bits. (Hint: Use 2n - 1 bits to specify thestructure of the tree, as discovered by a walk of the tree.)Exercises 16.3-6Generalize Huffman's algorithm to ternary codewords (i.e., codewords using the symbols 0, 1,and 2), and prove that it yields optimal ternary codes.Exercises 16.3-7Suppose a data file contains a sequence of 8-bit characters such that all 256 characters areabout as common: the maximum character frequency is less than twice the minimumcharacter frequency. Prove that Huffman coding in this case is no more efficient than using anordinary 8-bit fixed-length code.Exercises 16.3-8Show that no compression scheme can expect to compress a file of randomly chosen 8-bitcharacters by even a single bit.
(Hint: Compare the number of files with the number ofpossible encoded files.)[2]Perhaps "prefix-free codes" would be a better name, but the term "prefix codes" is standardin the literature.16.4Theoretical foundations for greedy methodsThere is a beautiful theory about greedy algorithms, which we sketch in this section. Thistheory is useful in determining when the greedy method yields optimal solutions.
It involvescombinatorial structures known as "matroids." Although this theory does not cover all casesfor which a greedy method applies (for example, it does not cover the activity-selectionproblem of Section 16.1 or the Huffman coding problem of Section 16.3), it does cover manycases of practical interest. Furthermore, this theory is being rapidly developed and extended tocover many more applications; see the notes at the end of this chapter for references.MatroidsA matroid is an ordered pair M = (S,ℓ) satisfying the following conditions.1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
