3 ms·
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 t
by mrkeen 2y ago
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
- agentultra 2y agoIt’s mentioned at the end and left as an exercise to the reader.
- lifthrasiir 2y ago> 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-huffman-paper.html https://cbloomrants.blogspot.com/2010/08/08-12-10-lost-huffm...
- lazamar 2y agoThanks 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.
- mjan22640 2y ago> and I'm wondering how many of you that's true for as well the phrasing sounds like a list comprehension
- agumonkey 2y agotrue, tickles my brain in all kinds of funny ways
- userbinator 2y agoThe 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.