Summary

The adaptive Huffman algorithm as described by Vitter had three constraints that were compelling to relax.

The first is the size of the table.  The size of the table was constrained based on initial knowledge of the set being compressed—typically constrained to 256 for a single byte alphabet size.

The NotYetTransmitted sequence never adjusted its weight based on its own frequency so clusters of new characters would not benefit from reduced sizes of this sequence.

Once new characters become rare, it makes sense to reduce the NotYetTransmitted weight and therefore demote it farther down the Huffman tree.

Source

The source for these changes can be found on GitHub. The implementation is C#. C/C++ implementations will be added in the future.
Continue reading →