Jeffrey Scott Vitter
Abstract
A new one-pass algorithm for constructing dynamic Huffman codes is introduced and analyzed. We also analyze the one-pass algorithm due to Faller, Gallager, and Knuth. In each algorithm, both the sender and the receiver maintain equivalent dynamically varying Huffman trees, and the coding is done in real time. We show that the number of bits used by the new algorithm to encode a message containing t letters is < t bits more than that used by the conventional two-pass Huffman scheme, independent of the alphabet size. This is best possible in the worst case, for any one-pass Huffman method. Tight upper and lower bounds are derived. Empirical tests show that the encodings produced by the new algorithm are shorter than those of the other one-pass algorithm and, except for long messages, are shorter than those of the two-pass method. The new algorithm is well suited for on-line encoding/decoding in data networks and for tile compression.
- 1 BENTLEY, Jf L., SLEATOR, D. D., TARJAN, R. E., AND WEI, V. K. A locally adaptive data compression scheme. Commun.4CM 29, 4 (Apr. 1986), 320-330. Google Scholar
- 2 ELIAS, P. Interval and recency-rank source coding: Two online adaptive variable-length schemes. IEEE Trans. Inf. Theory. To be published. Google Scholar
- 3 FALLER, N. An adaptive system for data compression. In Record of the 7th .4silomar Conference on Circuits, Systems, and Computers. 1973, pp. 593-597.Google Scholar
- 4 GALLAGER, R.G. Variations on a theme by Huffman. IEEE Trans. Inf. Theory 17"-24, 6 (Nov. 1978), 668-674.Google Scholar
- 5 HUFFMAN, D.A. A method for the construction of minimum redundancy codes. In Proc. IRE 40 (1951), 1098-1101.Google Scholar
- 6 KNUTH, D.E. Dynamic Huffman coding. J. Algorithms 6 (1985), 163-180. Google Scholar
- 7 MCMASTER, C. L. Documentation of the compact command. In UNIX User's Manual, 4.2 Berkeley Software Distribution, Virtual VAX-11 Version, Univ. of California, Berkeley, Berkeley, Calif., Mar. 1984.Google Scholar
- 8 SCHWARTZ, E.S. An Optimum Encoding with Minimum Longest Code and Total Number of Dip~ts. Inf. Control 7, 1 (Mar. 1964), 37-44.Google Scholar
- 9 VlYrER, J.S. Dynamic Huffman Coding. ACM Trans. Math. Sofiw. Submitted 1986.Google Scholar
- 10 VITTER, J. S., AND CHEN, W.C. Design and Analysis of Coalesced Hashing. Oxford University Press, New York, 1987. Google Scholar
Index Terms
- Design and analysis of dynamic Huffman codes
Recommendations
Design and analysis of dynamic Huffman coding
SFCS '85: Proceedings of the 26th Annual Symposium on Foundations of Computer ScienceWe introduce an efficient new algorithm for dynamic Huffman coding, called Algorithm V. It performs one-pass coding and transmission in real-time, and uses at most one more bit per letter than does the standard two-pass Huffman algorithm; this is ...
H.264 Video Compression Using Novel Refined Huffman Codes for Omnipresent Applications
AbstractThe technologies like cloud computing, big data, data mining applications deal with large volumes of data in the form of videos, images, audio and multi-media data. To efficiently store and transmit huge volumes of data is a challenge. The data ...
Forward Looking Huffman Coding
Computer Science – Theory and ApplicationsAbstractHuffman coding is known to be optimal, yet its dynamic version may yield smaller compressed files. The best known bound is that the number of bits used by dynamic Huffman coding in order to encode a message of n characters is at most larger by n ...
Comments