From: Jon Smirl Date: Tue, 15 Aug 2006 13:29:28 GMT Subject: Re: Compression and dictionaries Message-ID: <9e4733910608150629t1826717cqc4bde9f1ab5cc725@mail.gmail.com> In-Reply-To: <20060815083303.13253.qmail@science.horizon.com> On 15 Aug 2006 04:33:03 -0400, linux@horizon.com wrote: > Just to inform this discussion, a brief description of the zlib > "deflate" algorithm. A full description is in RFC1951. > > This is LZ77 compression, meaning that what is actually encoded is > a series of instruction to either > - Insert a specified byte, or > - Copy a run of n bytes, starting m bytes ago. Shawn and I did some testing overnight. A simple 4KB preload table yielded a 4% size reduction in my 850MB pack. I'm still hoping for 10% using an optimal 32K table. Paper on computing the optimal preload table: http://www.eecs.harvard.edu/~michaelm/postscripts/dcc2001a.pdf If anyone is interested in doing some research, it would be interesting to build a pack engine based on full-text search technology. For example cLucene, http://clucene.sourceforge.net/index.php/Main_Page The full-text search app contains the code for extracting the dictionary and then encoding all of the blobs using it. My prediction is that a large global dictionary based scheme will compress significantly better than zlib is capable of. -- Jon Smirl jonsmirl@gmail.com