2 ms·
The most clever part of deflate is actually how they store the huffman trees without storing the frequencies but rather the length in bits of each symbol. Combi
by shenberg 10y ago
The most clever part of deflate is actually how they store the huffman trees without storing the frequencies but rather the length in bits of each symbol. Combining the length of each symbol with its lexicographical ordering is enough to uniquely specify the actual tree.
Ok, some research showed me that the idea can probably be traced back to Schwartz & Kallick 1964 (can't find the text), popularized by TAOCP vol. 1...
- userbinator 10y agoThe technique is known as "Canonical Huffman" and is quite elegant indeed. It is best understood by considering the codes as binary numbers, then the tree structure naturally appears. There's a very short algorithm to generate the appropriate encoding and decoding tables in the JPEG standard and it involves not much more than shifts and adds.