20.4 Huffman Coding and Compression of Data 907 *ilong=j-1; free_lvector(nprob,1,(long)(2*hcode->nch-1)); free_lvector((unsigned long *)up,1,(long)(2*hcode->nch-1)); free_lvector(index,1,(long)(2*hcode->nch-1)); void hufapp(unsigned long index],unsigned long nprob[,unsigned long n, unsigned long i) Used by hufmak to maintain a heap structure in the array index [1..1]. 83g unsigned long j,k; granted for 19881992 k=index[i]; h11e(1<=(n>>1)){ 1.800 9 if ((j i<<1)<n&&nprob[index[j]]nprob[index[j+1]])j++; if (nprob[k]<nprob[index[j]])break; index [i]=index[j]; from NUMERICAL RECIPESI 1=j: index[i]=k; (Nort 2 America server computer, Note that the structure hcode must be defined and allocated in your main ART program with statements like this: Progra #include "nrutil.h" #define MC 512 Maximum anticipated value of nchin in hufmak. #define MQ (2*MC-1) typedef struct unsigned long *icod,*ncod,*left,*right,nch,nodemax; to dir huffcode; 188 huffcode hcode; OF SCIENTIFIC COMPUTING(ISBN 1920 hcode.icod=(unsigned long *)lvector(1,MQ); Allocate space within hcode. hcode.ncod=(unsigned long *)1vector(1,MQ); hcode.left=(unsigned long *)lvector(1,MQ); 0621 hcode.right=(unsigned long *)1vector(1,MQ); for (j=1;j<=MQ;j++)hcode.icod[j]=hcode.ncod[j]=0; Numerical Recipes -43108 Once the code is constructed,one encodes a string of characters by repeated calls to hufenc,which simply does a table lookup of the code and appends it to the (outside 膜 output message. oftware. #include <stdio.h> Ame #include <stdlib.h> typedef struct unsigned long *icod,*ncod,*left,*right,nch,nodemax; huffcode; void hufenc(unsigned long ich,unsigned char **codep,unsigned long *lcode, unsigned long *nb,huffcode *hcode) Huffman encode the single character ich (in the range 0..nch-1)using the code in the structure hcode,write the result to the character array *codep[1..Icode]starting at bit nb (whose smallest valid value is zero).and increment nb appropriately.This routine is called20.4 Huffman Coding and Compression of Data 907 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). *ilong=j-1; } } free_lvector(nprob,1,(long)(2*hcode->nch-1)); free_lvector((unsigned long *)up,1,(long)(2*hcode->nch-1)); free_lvector(index,1,(long)(2*hcode->nch-1)); } void hufapp(unsigned long index[], unsigned long nprob[], unsigned long n, unsigned long i) Used by hufmak to maintain a heap structure in the array index[1..l]. { unsigned long j,k; k=index[i]; while (i <= (n>>1)) { if ((j = i << 1) < n && nprob[index[j]] > nprob[index[j+1]]) j++; if (nprob[k] <= nprob[index[j]]) break; index[i]=index[j]; i=j; } index[i]=k; } Note that the structure hcode must be defined and allocated in your main program with statements like this: #include "nrutil.h" #define MC 512 Maximum anticipated value of nchin in hufmak. #define MQ (2*MC-1) typedef struct { unsigned long *icod,*ncod,*left,*right,nch,nodemax; } huffcode; ... huffcode hcode; ... hcode.icod=(unsigned long *)lvector(1,MQ); Allocate space within hcode. hcode.ncod=(unsigned long *)lvector(1,MQ); hcode.left=(unsigned long *)lvector(1,MQ); hcode.right=(unsigned long *)lvector(1,MQ); for (j=1;j<=MQ;j++) hcode.icod[j]=hcode.ncod[j]=0; Once the code is constructed, one encodes a string of characters by repeated calls to hufenc, which simply does a table lookup of the code and appends it to the output message. #include <stdio.h> #include <stdlib.h> typedef struct { unsigned long *icod,*ncod,*left,*right,nch,nodemax; } huffcode; void hufenc(unsigned long ich, unsigned char **codep, unsigned long *lcode, unsigned long *nb, huffcode *hcode) Huffman encode the single character ich (in the range 0..nch-1) using the code in the structure hcode, write the result to the character array *codep[1..lcode] starting at bit nb (whose smallest valid value is zero), and increment nb appropriately. This routine is called