Design and analysis of dynamic Huffman codes

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.

REFERENCES

• 1: Jon Louis Bentley , Daniel D. Sleator , Robert E. Tarjan , Victor K. Wei, A locally adaptive data compression scheme, Communications of the ACM, v.29 n.4, p.320-330, April 1986 [doi>10.1145/5684.5688]
• 2: Peter Elias, Interval and recency rank source coding: two on-line adaptive variable-length schemes, IEEE Transactions on Information Theory, v.33 n.1, p.3-10, January 2, 1987 [doi>10.1109/TIT.1987.1057251]
• 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.
• 4: GALLAGER, R.G. Variations on a theme by Huffman. IEEE Trans. Inf. Theory 17"-24, 6 (Nov. 1978), 668-674.
• 5: HUFFMAN, D.A. A method for the construction of minimum redundancy codes. In Proc. IRE 40 (1951), 1098-1101.
• 6: Donald E. Knuth, Dynamic Huffman coding, Journal of Algorithms, v.6 n.2, p.163-180, June 1985 [doi>10.1016/0196-6774(85)90036-7]
• 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.
• 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.
• 9: VlYrER, J.S. Dynamic Huffman Coding. ACM Trans. Math. Sofiw. Submitted 1986.
• 10: Jeffrey S. Vitter , Wen-Chin Chen, The design and analysis of coalesced hashing, Oxford University Press, Inc., New York, NY, 1987

INDEX TERMS

Primary Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY
      Subjects: Data compaction and compression

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Data communications

General Terms:
Algorithms, Design, Measurement, Performance, Theory, Verification