Incremental calculation of minimum-redundancy length-restricted codes

Abstract

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 {f1, f2,...,fn}, 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,..