On the implementation of minimum-redundancy prefix codes

Abstract

Minimum-redundancy coding is one of the enduring techniques of data compression. This work examines how best minimum-redundancy coding can be implemented, with particular emphasis on the situation when n is large. Techniques for devising minimum-redundancy codes are reviewed. It is also shown in detail how encoding and decoding should be accomplished. In particular, a modified decoding method is described that allows improved decoding throughput, requiring just a few machine operations per output symbol, and uses just a few hundred bytes of memory above and beyond the space required to store an enumeration of the source alphabet.