[mrkeen]

There exists an array-based, in-place algorithm for this, reducing the need to allocate trees and chase pointers.

I mention this only because, when I learned the tree-based approach at uni, I simply wasn't aware that there was another way to do it, and I'm wondering how many of you that's true for as well.

While the tree approach is intuitive and illuminating, it probably makes more sense to work with in-place arrays, since the situations when you care most about compression are probably the situations when you have a lot of data and want to run fast.

  In-Place Calculation of Minimum-Redundancy Codes
  Moffat, Katajainen.  1995.
  http://hjemmesider.diku.dk/~jyrki/Paper/WADS95.pdf

[lifthrasiir]

> In-Place Calculation of Minimum-Redundancy Codes

Or in general, refer to "On the Implementation of Minimum Redundancy Prefix Codes" by Moffat and Turpin (1997), as strongly recommended and later explained by Charles Bloom [1].

[1] https://cbloomrants.blogspot.com/2010/08/08-12-10-lost-huffm...

[lazamar]

Thanks for the link. I was motivated to write the post after reading Moffat’s book ‘Managing Gigabytes’. A pearl from the 90’s.

The authors mention this technique in the second edition.

[userbinator]

The JPEG standard ITU T.81 (1992) has a description of the algorithm in flowcharts, so the knowledge of array-based Huffman was probably already somewhat common in the 80s.

[agentultra]

It’s mentioned at the end and left as an exercise to the reader.

[mjan22640]

> and I'm wondering how many of you that's true for as well

the phrasing sounds like a list comprehension

[agumonkey]

true, tickles my brain in all kinds of funny ways