Re: Compression and dictionaries

From: Johannes Schindelin <johannes.schindelin@gmx.de>
Date: Aug 14, 2006, 14:45 UTC
Message-ID: <Pine.LNX.4.63.0608141641330.28360@wbgn013.biozentrum.uni-wuerzburg.de>
In-Reply-To: <9e4733910608140708i45e3d6day6b87676783fd6511@mail.gmail.com>

Hi,

On Mon, 14 Aug 2006, Jon Smirl wrote:

> Does a zlib dictionary just changes the probabilities in the histogram 
> or does it turn the dictionary into a pre-loaded encoding tree?

I have to admit that I do not know zlib well enough to tell off the top of my head, but I guess it would make more sense to have it as a preloaded encoding tree.

Show 9 quoted lines

> The other compression schemes I looked at let you load in a
> precomputed huffman/arithmetic encoding tree. By preloading an
> encoding tree you avoid storing the encoding of "void => 010101' in
> every  item. Removing 1M encoding maps and using one common one should
> be a win. Items not in the map would still be stored using internal
> additions to the map.
> 
> Changing the probabilities probably won't help much, but there may be
> good gains from partially eliminating 1M encoding maps.

I _think_ that it would not matter much. The deltas have a more important impact.

> > Further, if the pack-file becomes corrupt, you usually still have the 
> > pack index, or the start of the pack-file, and can reconstruct most of 
> > the objects. If you use a dictionary, and just one bit flips in it, 
> > you're screwed.

I still think that this is important to think through: Is it worth a couple of kilobytes (I doubt that it would be as much as 1MB in _total_), and be on the unsafe side?

Ciao, Dscho