Algorithm 673: Dynamic Huffman coding

ABSTRACT

We present a Pascal implementation of the one-pass algorithm for constructing dynamic Huffman codes that is described and analyzed in a companion paper. The program runs in real time; that is, the processing time for each letter of the message is proportional to the length of its codeword. The number of bits used to encode a message of t letters is less than t bits more than that used by the well-known two-pass algorithm. This is best possible for any one-pass Huffman scheme. In practice, it uses fewer bits than all other Huffman schemes. The algorithm has applications in file compression and network transmission.

REFERENCES

• 1: HUFFMAN, D.A. A method for the construction of minimum redundancy codes. In the Proceedings o{ the Institute of Radio Engineers 40 (1951), pp. 1098-1101.
• 2: 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]
• 3: Jeffrey Scott Vitter, Design and analysis of dynamic Huffman codes, Journal of the ACM (JACM), v.34 n.4, p.825-845, Oct. 1987 [doi>10.1145/31846.42227]

INDEX TERMS

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

  E. Data
  E.1 DATA STRUCTURES
      Subjects: Trees
  E.4 CODING AND INFORMATION THEORY
      Subjects: Data compaction and compression; Nonsecret encoding schemes**

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

  H. Information Systems
  H.1 MODELS AND PRINCIPLES
      H.1.1 Systems and Information Theory
          Subjects: Value of information

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
Huffman codes