  Efficient optimal prefix coding has long been accomplished via the Huffman
algorithm. However, there is still room for improvement and exploration
regarding variants of the Huffman problem. Length-limited Huffman coding,
useful for many practical applications, is one such variant, in which codes are
restricted to the set of codes in which none of the $n$ codewords is longer
than a given length, $l_{\max}$. Binary length-limited coding can be done in
$O(n l_{\max})$ time and O(n) space via the widely used Package-Merge
algorithm. In this paper the Package-Merge approach is generalized without
increasing complexity in order to introduce a minimum codeword length,
$l_{\min}$, to allow for objective functions other than the minimization of
expected codeword length, and to be applicable to both binary and nonbinary
codes; nonbinary codes were previously addressed using a slower dynamic
programming approach. These extensions have various applications -- including
faster decompression -- and can be used to solve the problem of finding an
optimal code with limited fringe, that is, finding the best code among codes
with a maximum difference between the longest and shortest codewords. The
previously proposed method for solving this problem was nonpolynomial time,
whereas solving this using the novel algorithm requires only $O(n (l_{\max}-
l_{\min})^2)$ time and O(n) space.
