Introduction to Algorithms. (2nd edition) Thomas Cormen_ Charles Leiserson_ Ronad Rivest (811417), страница 74
Текст из файла (страница 74)
Give an efficient algorithmto find an optimal solution to this variant of the knapsack problem, and argue that youralgorithm is correct.Exercises 16.2-4Professor Midas drives an automobile from Newark to Reno along Interstate 80. His car's gastank, when full, holds enough gas to travel n miles, and his map gives the distances betweengas stations on his route. The professor wishes to make as few gas stops as possible along theway. Give an efficient method by which Professor Midas can determine at which gas stationshe should stop, and prove that your strategy yields an optimal solution.Exercises 16.2-5Describe an efficient algorithm that, given a set {x1, x2, ...,xn} of points on the real line,determines the smallest set of unit-length closed intervals that contains all of the given points.Argue that your algorithm is correct.Exercises 16.2-6:Show how to solve the fractional knapsack problem in O(n) time. Assume that you have asolution to Problem 9-2.Exercises 16.2-7Suppose you are given two sets A and B, each containing n positive integers.
You can chooseto reorder each set however you like. After reordering, let ai be the ith element of set A, and. Give an algorithm thatlet bi be the ith element of set B. You then receive a payoff ofwill maximize your payoff. Prove that your algorithm maximizes the payoff, and state itsrunning time.16.3 Huffman codesHuffman codes are a widely used and very effective technique for compressing data; savingsof 20% to 90% are typical, depending on the characteristics of the data being compressed. Weconsider the data to be a sequence of characters. Huffman's greedy algorithm uses a table ofthe frequencies of occurrence of the characters to build up an optimal way of representingeach character as a binary string.Suppose we have a 100,000-character data file that we wish to store compactly.
We observethat the characters in the file occur with the frequencies given by Figure 16.3. That is, only sixdifferent characters appear, and the character a occurs 45,000 times.abcdefFrequency (in thousands) 45 13 12 16 95Fixed-length codeword 000 001 010 011 100 101Variable-length codeword 0 101 100 111 1101 1100Figure 16.3: A character-coding problem. A data file of 100,000 characters contains only thecharacters a–f, with the frequencies indicated. If each character is assigned a 3-bit codeword,the file can be encoded in 300,000 bits.
Using the variable-length code shown, the file can beencoded in 224,000 bits.There are many ways to represent such a file of information. We consider the problem ofdesigning a binary character code (or code for short) wherein each character is representedby a unique binary string. If we use a fixed-length code, we need 3 bits to represent sixcharacters: a = 000, b = 001, ..., f = 101. This method requires 300,000 bits to code the entirefile. Can we do better?A variable-length code can do considerably better than a fixed-length code, by givingfrequent characters short codewords and infrequent characters long codewords. Figure 16.3shows such a code; here the 1-bit string 0 represents a, and the 4-bit string 1100 represents f.This code requires(45 · 1 + 13 · 3 + 12 · 3 + 16 · 3 + 9 · 4 + 5 · 4) · 1,000 = 224,000 bitsto represent the file, a savings of approximately 25%. In fact, this is an optimal character codefor this file, as we shall see.Prefix codesWe consider here only codes in which no codeword is also a prefix of some other codeword.Such codes are called prefix codes.[2] It is possible to show (although we won't do so here)that the optimal data compression achievable by a character code can always be achieved witha prefix code, so there is no loss of generality in restricting attention to prefix codes.Encoding is always simple for any binary character code; we just concatenate the codewordsrepresenting each character of the file.
For example, with the variable-length prefix code ofFigure 16.3, we code the 3-character file abc as 0·101·100 = 0101100, where we use "·" todenote concatenation.Prefix codes are desirable because they simplify decoding. Since no codeword is a prefix ofany other, the codeword that begins an encoded file is unambiguous.
We can simply identifythe initial codeword, translate it back to the original character, and repeat the decodingprocess on the remainder of the encoded file. In our example, the string 001011101 parsesuniquely as 0 · 0 · 101 · 1101, which decodes to aabe.The decoding process needs a convenient representation for the prefix code so that the initialcodeword can be easily picked off.
A binary tree whose leaves are the given charactersprovides one such representation. We interpret the binary codeword for a character as the pathfrom the root to that character, where 0 means "go to the left child" and 1 means "go to theright child." Figure 16.4 shows the trees for the two codes of our example. Note that these arenot binary search trees, since the leaves need not appear in sorted order and internal nodes donot contain character keys.Figure 16.4: Trees corresponding to the coding schemes in Figure 16.3. Each leaf is labeledwith a character and its frequency of occurrence.
Each internal node is labeled with the sum ofthe frequencies of the leaves in its subtree. (a) The tree corresponding to the fixed-length codea = 000, ..., f = 101. (b) The tree corresponding to the optimal prefix code a = 0, b = 101, ..., f= 1100.An optimal code for a file is always represented by a full binary tree, in which every nonleafnode has two children (see Exercise 16.3-1). The fixed-length code in our example is notoptimal since its tree, shown in Figure 16.4(a), is not a full binary tree: there are codewordsbeginning 10..., but none beginning 11....
Since we can now restrict our attention to full binarytrees, we can say that if C is the alphabet from which the characters are drawn and allcharacter frequencies are positive, then the tree for an optimal prefix code has exactly |C|leaves, one for each letter of the alphabet, and exactly |C| - 1 internal nodes (see Exercise B.53).Given a tree T corresponding to a prefix code, it is a simple matter to compute the number ofbits required to encode a file. For each character c in the alphabet C, let f (c) denote thefrequency of c in the file and let dT(c) denote the depth of c's leaf in the tree. Note that dT(c) isalso the length of the codeword for character c. The number of bits required to encode a file isthus(16.5)which we define as the cost of the tree T.Constructing a Huffman codeHuffman invented a greedy algorithm that constructs an optimal prefix code called aHuffman code.
Keeping in line with our observations in Section 16.2, its proof of correctnessrelies on the greedy-choice property and optimal substructure. Rather than demonstrating thatthese properties hold and then developing pseudocode, we present the pseudocode first. Doingso will help clarify how the algorithm makes greedy choices.In the pseudocode that follows, we assume that C is a set of n characters and that eachcharacter c C is an object with a defined frequency f [c]. The algorithm builds the tree Tcorresponding to the optimal code in a bottom-up manner. It begins with a set of |C| leavesand performs a sequence of |C| - 1 "merging" operations to create the final tree. A min-priorityqueue Q, keyed on f , is used to identify the two least-frequent objects to merge together.
Theresult of the merger of two objects is a new object whose frequency is the sum of thefrequencies of the two objects that were merged.HUFFMAN(C)1 n ← |C|2 Q ← C3 for i 14do56789to n - 1allocate a new node zleft[z] ← x ← EXTRACT-MIN (Q)right[z] ← y ← EXTRACT-MIN (Q)f [z] ← f [x] + f [y]INSERT(Q, z)return EXTRACT-MIN(Q)▹Return the root of the tree.For our example, Huffman's algorithm proceeds as shown in Figure 16.5. Since there are 6letters in the alphabet, the initial queue size is n = 6, and 5 merge steps are required to buildthe tree. The final tree represents the optimal prefix code. The codeword for a letter is thesequence of edge labels on the path from the root to the letter.Figure 16.5: The steps of Huffman's algorithm for the frequencies given in Figure 16.3.
Eachpart shows the contents of the queue sorted into increasing order by frequency. At each step,the two trees with lowest frequencies are merged. Leaves are shown as rectangles containing acharacter and its frequency. Internal nodes are shown as circles containing the sum of thefrequencies of its children. An edge connecting an internal node with its children is labeled 0if it is an edge to a left child and 1 if it is an edge to a right child. The codeword for a letter isthe sequence of labels on the edges connecting the root to the leaf for that letter. (a) The initialset of n = 6 nodes, one for each letter. (b)–(e) Intermediate stages. (f) The final tree.Line 2 initializes the min-priority queue Q with the characters in C.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
