20.4 Huffman Coding and Compression of Data 909 *ich=node-1; return; For simplicity,hufdec quits when it runs out of code bytes;if your coded message is not an integral number of bytes,and if Nch is less than 256,hufdec can return a spurious final character or two,decoded from the spurious trailing bits in your last code byte.If you have independent knowledge of the number of characters sent,you can readily discard these.Otherwise,you can fix this behavior by providing a bit,not byte,count,and modifying the routine accordingly.(When Nch is 256 or larger,hufdec will normally run out of code in the middle of a spurious character, and it will be discarded. Run-Length Encoding For the compression of highly correlated bit-streams(for example the black or white values along a facsimile scan line),Huffman compression is often combined 9 with run-length encoding:Instead of sendingeach bit,the input stream is converted to a series of integers indicating how many consecutive bits have the same value.These Press. integers are then Huffman-compressed.The Group 3 CCITT facsimile standard functions in this manner,with a fixed,immutable,Huffman code,optimized for a set of eight standard documents [8,9]. %≥N OF SCIENTIFIC CITED REFERENCES AND FURTHER READING: Gallager,R.G.1968.Information Theory and Reliable Communication (New York:Wiley). Hamming,R.W.1980,Coding and Information Theory(Englewood Cliffs,NJ:Prentice-Hall). Storer,J.A.1988,Data Compression:Methods and Theory(Rockville,MD:Computer Science Press). Nelson,M.1991,The Data Compression Book(Redwood City,CA:M&T Books). 10.621 Huffman,D.A.1952,Proceedings of the Institute of Radio Engineers,vol.40,pp.1098-1101.[1] Ziv,J.,and Lempel,A.1978,IEEE Transactions on Information Theory,vol.IT-24,pp.530-536. 么 Numerical Recipes 43106 2] Cleary.J.G.,and Witten,I.H.1984,IEEE Transactions on Communications,vol.COM-32, Pp.396-402.[3] (outside Welch,T.A.1984,Computer,vol.17,no.6,pp.8-19.[4] Bentley.J.L.,Sleator,D.D.,Tarjan,R.E..and Wei,V.K.1986,Communications of the ACM, North Software. vol.29,pp.320-330.[5 Jones,D.W.1988,Communications of the ACM,vol.31,pp.996-1007.[6] Sedgewick,R.1988.A/gorithms,2nd ed.(Reading,MA:Addison-Wesley).Chapter 22.[7] Hunter,R.,and Robinson,A.H.1980,Proceedings of the /EEE,vol.68,pp.854-867.[8] Marking,M.P.1990,The C Users'Journal,vol.8,no.6,pp.45-54.[9]20.4 Huffman Coding and Compression of Data 909 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). *ich=node-1; return; } } } For simplicity, hufdec quits when it runs out of code bytes; if your coded message is not an integral number of bytes, and if Nch is less than 256, hufdec can return a spurious final character or two, decoded from the spurious trailing bits in your last code byte. If you have independent knowledge of the number of characters sent, you can readily discard these. Otherwise, you can fix this behavior by providing a bit, not byte, count, and modifying the routine accordingly. (When N ch is 256 or larger, hufdec will normally run out of code in the middle of a spurious character, and it will be discarded.) Run-Length Encoding For the compression of highly correlated bit-streams (for example the black or white values along a facsimile scan line), Huffman compression is often combined with run-length encoding: Instead of sending each bit, the input stream is converted to a series of integers indicating how many consecutive bits have the same value. These integers are then Huffman-compressed. The Group 3 CCITT facsimile standard functions in this manner, with a fixed, immutable, Huffman code, optimized for a set of eight standard documents [8,9]. CITED REFERENCES AND FURTHER READING: Gallager, R.G. 1968, Information Theory and Reliable Communication (New York: Wiley). Hamming, R.W. 1980, Coding and Information Theory (Englewood Cliffs, NJ: Prentice-Hall). Storer, J.A. 1988, Data Compression: Methods and Theory (Rockville, MD: Computer Science Press). Nelson, M. 1991, The Data Compression Book (Redwood City, CA: M&T Books). Huffman, D.A. 1952, Proceedings of the Institute of Radio Engineers, vol. 40, pp. 1098–1101. [1] Ziv, J., and Lempel, A. 1978, IEEE Transactions on Information Theory, vol. IT-24, pp. 530–536. [2] Cleary, J.G., and Witten, I.H. 1984, IEEE Transactions on Communications, vol. COM-32, pp. 396–402. [3] Welch, T.A. 1984, Computer, vol. 17, no. 6, pp. 8–19. [4] Bentley, J.L., Sleator, D.D., Tarjan, R.E., and Wei, V.K. 1986, Communications of the ACM, vol. 29, pp. 320–330. [5] Jones, D.W. 1988, Communications of the ACM, vol. 31, pp. 996–1007. [6] Sedgewick, R. 1988, Algorithms, 2nd ed. (Reading, MA: Addison-Wesley), Chapter 22. [7] Hunter, R., and Robinson, A.H. 1980, Proceedings of the IEEE, vol. 68, pp. 854–867. [8] Marking, M.P. 1990, The C Users’ Journal, vol. 8, no. 6, pp. 45–54. [9]