Algorithm 673

Algorithm 673: Dynamic Huffman coding. We present a Pascal implementation of the one-pass algorithm for constructing dynamic Huffman codes that is described and analyzed in a companion paper [J. Assoc. Comput. Mach. 34, 825-845 (1987; Zbl 0637.94002)]. 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.

This software is also peer reviewed by journal TOMS.