20.4 Huffman Coding and Compression of Data 905 9 EAUIO 1.00 0 2@0.42 8AU100.58 0 1 read able files 7AUI0.28 4⊙0.30 0 1 1@0.126U☐0.16 .com or call 1-800-872- (including this one) internet 0 7 -7423 (North America to any server computer. 1988-1992 by Cambridge University Press. tusers to make one paper from NUMERICAL RECIPES IN C: 5①0.07 3①0.09 Figure 20.4.1.Huffman code for the fictitious language Vowellish,in tree form.A letter (A,E,I, THE O,or U)is encoded or decoded by traversing the tree from the top down;the code is the sequence of 0's and I's on the branches.The value to the right of each node is its probability;to the left,its node ART number in the accompanying table. ictly pror Programs smallest nodes are always an original node and a composite one;this need not be true in general:The two smallest probabilities might be both original nodes,or both composites,or one of each.At the last stage,all nodes will have been collected into one grand composite of total probability 1. 可 Now,to see the code,you redraw the data in the above table as a tree (Figure 20.4.1).As shown,each node of the tree corresponds to a node (row)in the table, OF SCIENTIFIC COMPUTING (ISBN indicated by the integer to its left and probability value to its right.Terminal nodes. 1988-18920 so called,are shown as circles:these are single alphabetic characters.The branches of the tree are labeled 0 and 1.The code for a character is the sequence of zeros and uurggoglrion Numerical Recipes 10-621 ones that lead to it,from the top down.For example,E is simply 0,while U is 1010. Any string of zeros and ones can now be decoded into an alphabetic sequence. Consider,for example,the string 1011111010.Starting at the top of the tree we 431985 descend through 1011 to I,the first character.Since we have reached a terminal node,we reset to the top of the tree,next descending through 11 to O.Finally 1010 (outside gives U.The string thus decodes to IOU. North Software. These ideas are embodied in the following routines.Input to the first routine hufmak is an integer vector of the frequency of occurrence of the nchin =Nch alphabetic characters,i.e.,a set of integers proportional to the pi's.hufmak,along with hufapp,which it calls,performs the construction of the above table,and also the tree of Figure 20.4.1.The routine utilizes a heap structure(see 88.3)for efficiency; for a detailed description,see Sedgewick [71.20.4 Huffman Coding and Compression of Data 905 Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copyin Copyright (C) 1988-1992 by Cambridge University Press. Programs Copyright (C) 1988-1992 by Numerical Recipes Software. Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5) g of machine￾readable files (including this one) to any server computer, is strictly prohibited. To order Numerical Recipes books or CDROMs, visit website http://www.nr.com or call 1-800-872-7423 (North America only), or send email to directcustserv@cambridge.org (outside North America). E EAUIO A U AUI AUIO UI I O 1.00 0.58 0.28 0.30 5 0.07 3 0.09 0.12 6 0.16 2 0.42 9 8 7 4 1 0 1 0 1 0 1 0 1 Figure 20.4.1. Huffman code for the fictitious language Vowellish, in tree form. A letter (A, E, I, O, or U) is encoded or decoded by traversing the tree from the top down; the code is the sequence of 0’s and 1’s on the branches. The value to the right of each node is its probability; to the left, its node number in the accompanying table. smallest nodes are always an original node and a composite one; this need not be true in general: The two smallest probabilities might be both original nodes, or both composites, or one of each. At the last stage, all nodes will have been collected into one grand composite of total probability 1. Now, to see the code, you redraw the data in the above table as a tree (Figure 20.4.1). As shown, each node of the tree corresponds to a node (row) in the table, indicated by the integer to its left and probability value to its right. Terminal nodes, so called, are shown as circles; these are single alphabetic characters. The branches of the tree are labeled 0 and 1. The code for a character is the sequence of zeros and ones that lead to it, from the top down. For example, E is simply 0, while U is 1010. Any string of zeros and ones can now be decoded into an alphabetic sequence. Consider, for example, the string 1011111010. Starting at the top of the tree we descend through 1011 to I, the first character. Since we have reached a terminal node, we reset to the top of the tree, next descending through 11 to O. Finally 1010 gives U. The string thus decodes to IOU. These ideas are embodied in the following routines. Input to the first routine hufmak is an integer vector of the frequency of occurrence of the nchin ≡ N ch alphabetic characters, i.e., a set of integers proportional to the p i’s. hufmak, along with hufapp, which it calls, performs the construction of the above table, and also the tree of Figure 20.4.1. The routine utilizes a heap structure (see §8.3) for efficiency; for a detailed description, see Sedgewick [7]