Incremental calculation of minimum-redundancy length-restricted codes

The prefix-free code construction problem is to take a message containing n unique symbols and produce a set of n codewords which can be used to create a reversible encoding of the message. The minimum-redundancy code construction problem adds the requirement that the code produced must minimise the cost of transmission (or storage) of the message. Adding another constraint, the minimum-redundancy length-restricted code construction problem is to create a minimum-redundancy code in which no codeword has a length greater than L bits. The solution to the minimum-redundancy code construction problem is due to Huffman (1952). The package-merge strategy of Larmore and Hirschberg (1990) is a two-stage mechanism for creating minimum-redundancy length-restricted codes. Their implementation, here called ORIGINAL-PM, requires O(nL) time and space. ORIGINAL-PM follows the underlying strategy closely and the following is a description of both the principle and that first implementation. Different implementation methods are discussed.