🚀 go-pugleaf

In <JT.92Sep30184832@fizyk1.fuw.edu.pl> jt@fuw.edu.pl (Jerzy Tarasiuk) writes:

>Hello,
>Most efficient algorithm to store information necessary to re-build
>Huffman decoding tree is put 256 bytes each specifying code size
>used to encode byte value which is index to the table, for exmple
>if use for 'a', 'b' and 'c' codes of lengths 4, 7 and 6, respectively
>then bytes at positions 97,98 and 99 should be 4,7,6; if '@' is not
>used in text which is compressed, then at position 64 can be 0.
>This information is not sufficient to rebuild original tree but is
>sufficient to build tree giving max compression (as original gives)
>so can put same algorithm for rebuilding in both comp and decomp.
>If there are no many long codes can think about using less then 8-bit
>bytes for this information (but is possible worst case when code
>sizes have range from 1 to 255 and such a packing is not possible...).
>Jerzy Tarasiuk

The idea to use code lengths for compact storage is quite common,
and of course quite good. Soem more idea's right "stolen" from
PKZIP 1.93a on this subject (and the PKZIP scheme is derived
from the AR002 scheme):
   - limit the code size to e.g. 15 (almost no harm to compression!)
   - use Huffman compression to compress the value's, there will be
     more long than short codes after all!
   - It even pays off to use an optimal tree for these Huffman
     codes and store this tree as well (wan't real fun? do this
     recursive multiple times :-).
   - run length encode the values, especially usefull for blocks
     of unused values
Some more tricks to improve the compression of the tree:
   - use some predictive model to make the tree rep even smaller
   - use a static dictionary of specific file's (general ones)
     helping the predictor
   - try to analyze tree's with familiar characteristics (e.g.
     if a single file is cut into pieces the tree's for those
     pieces will have properties in common)
Even using a neural network to do the predicting pays off.

Nico E. de Vries
 _ _
 O O  USENET nevries@cc.ruu.nl This text reflects MY opinions, nothing else.
  o   This text is supplied 'AS IS', no waranties of any kind apply.
 \_/  Don't waste your time on complaining about my hopeless typostyle.

"I own so many clocks that I need 1 hour to set them all one hour back
 for Winter time. Nevertheless it does not cost me any time."