mercredi 10 février 2016

Playing with limited-length Huffman trees

A small portion of a Huffman tree
Proper counting is crucial

On the second image you can recognize "DIZAINES" and "UNITÉS". The letters are hardly visible after some 90 years of use... It's a pool table in the mythic Schlauch Restaurant in Zurich.

Back to Huffman trees: just came across a beautiful algorithm [1] for building a Huffman tree with, as a constraint, a limited code length. With the original Huffman algorithm, parts of the tree may become arbitrarily long - well, obviously not longer that the alphabet to be encoded. This algorithm is optimal (given the constraint), fast and very economical in terms of used memory.

There is an equally beautiful implementation [2], translated for the purpose of the Zip-Ada project - a proper dynamic Deflate for compression is still missing, and a limited-length Huffman tree building algorithm is needed for that.
Translation is there: specification, body, test procedure, and abstract enough to build with an Ada 83 compiler (at least GNAT in -gnat83 mode)!
___
[1] Search: "A Fast and Space-Economical Algorithm for Length-Limited Coding"
[2] Search: "katajainen.c" (this part of the "Zopfli" project)

Aucun commentaire:

Enregistrer un commentaire

Silly Abbreviation Generator (SAG)

An overdue feature (better said: a low-hanging fruit) of the Corporate Bullshit Generator is the Silly Abbreviation Generator (SAG). Now, fi...