Incremental Calculation of Minimum-Redundancy Length-Restricted Codes

The length-restricted code-construction problem arises when using prefix codes for large messages and also for search-tree depth minimization. A problem instance comprises an ordered set of input probabilities which in this paper are assumed, without loss of generality, to be a set of unnormalized integer frequencies {f₁ , f₂,..., f_n}, and a maximum codeword length L bits. The package-merge algorithm of Larmore and Hirschberg constructs a minimum-redundancy length-restricted code in O(nL) time. Here we present an algorithm which computes a minimum-redundancy length-restricted code in O((H L + 1)n) time, by starting with a minimum-redundancy (Huffman) code with a maximum codeword length of H, and then refining it to meet the length limit L. The new algorithm is suited to problems where H - L is small; and when H - L > L - [log n], the new algorithm outperforms all previous methods. Experimental results confirm the behavior of the new algorithm