  Given a probability distribution over a set of n words to be transmitted, the
Huffman Coding problem is to find a minimal-cost prefix free code for
transmitting those words. The basic Huffman coding problem can be solved in O(n
log n) time but variations are more difficult. One of the standard techniques
for solving these variations utilizes a top-down dynamic programming approach.
In this paper we show that this approach is amenable to dynamic programming
speedup techniques, permitting a speedup of an order of magnitude for many
algorithms in the literature for such variations as mixed radix, reserved
length and one-ended coding. These speedups are immediate implications of a
general structural property that permits batching together the calculation of
many DP entries.
