Any good example of Package-Merge algorithm limiting Huffman codes?

[inlove...@gmail.com]

I've been searching the net for any good example or explanation on how to use the Package-Merge algorithm to create huffman codes limiting their maximum length.

I understand the Package-Merge algorithm when it's explained with coins of denominational value and "collector's" value. That much is simple and makes sense to me.

I don't quite yet see the jump from coins to huffman codes. Explanations suggest creating X coins for each symbol, where each coin has 2^(-x) denominational value and F (frequency) "collector's" value. OK, but when I start going through the process in my head, I end up with packages that contain coins that reference the same symbol, which doesn't make sense to me.

I looked at the bzip2 source code and how they handle huffman codes that are too long. They just re-adjust the weights (basically divide all by 2) and regenerate the huffman tree until the maximum length is short enough. It's ridiculously simple.

Anyway, is there any explanations, examples, code samples, that actually use the Package-Merge algorithm to generate huffman codes? I'd love to learn more but it seems the net is lacking on good explanations.

Thanks!
Jeremiah

[Mark Adler]

On 2012-07-11 10:03:48 -0700, inlove...@gmail.com said:
> I've been searching the net for any good example or explanation on how
> to use the Package-Merge algorithm to create huffman codes limiting
> their maximum length.

You'll need to read Moffat's papers on the subject. Look for
"length-restricted" and "length-limited" on this page:

http://ww2.cs.mu.oz.au/~alistair/abstracts/

Mark