3 ms·
The Lost Huffman Paper (2010)
- userbinator 9y agoMost people in the implementation community also missed this paper (eg. zlib, JPEG, etc. people who make important use of huffman decodes have missed these techniques). Actually, ITU T.81 (the JPEG standard), published in 1992, contains a flowchart that appears to implement the same algorithm, so I think Moffat and Turpin were a few years "late to the party". However, that's still not the fastest way to decode Huffman, since it involves a loop --- the fastest is a single table lookup, which is practical for smaller maximum code lengths (such a commonly encountered in JPEG.)
- timb07 9y agoAnd presumably Turpin's PhD examiners weren't aware of the flowchart in the JPEG standard either.
- timb07 9y agoAndrew Turpin's implementation of a minimum-redundancy code (a.k.a. "Huffman code") is here: https://github.com/turpinandrew/shuff https://github.com/turpinandrew/shuff