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...
The 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.
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...