  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, for 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
and with even smaller asymptotic complexity using a lesser-known algorithm. In
this paper these algorithms are generalized without increasing complexity in
order to introduce a minimum codeword length constraint $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 fast decompression and
a modified version of the game ``Twenty Questions'' -- 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 linear-space algorithm
requires only $O(n (l_{\max}- l_{\min})^2)$ time, or even less if $l_{\max}-
l_{\min}$ is not $O(\log n)$.
