Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uunet!mcsun!hp4nl!charon!sander
From: sander@cwi.nl (Sander Plomp)
Newsgroups: comp.binaries.ibm.pc.d
Subject: Re: Dictionary-based archiver
Keywords: archiver
Message-ID: <2862@charon.cwi.nl>
Date: 29 Jan 91 13:08:31 GMT
References: <16055@sdcc6.ucsd.edu> <1991Jan28.155038.56@csc.canterbury.ac.nz> <5741@idunno.Princeton.EDU> <1991Jan28.161216.28110@en.ecn.purdue.edu>
Sender: news@cwi.nl
Distribution: comp
Lines: 31

carlsona@en.ecn.purdue.edu (The Lossel) writes:

> It's been a long time since I read the information on PKZIP's compression
>methods, but doesn't the 'Imploding' compression use a 'sliding dictionary'
>as part of the compression scheme?  Anyone really familliar with the PKZIP
>compression care to comment?

Yes, Imploding uses a 'sliding dictionary' method. You should really consult
the information provided with PKZIP, as it contains not only more detailed
information but also some literature references. The information provided in
that file (APPNOTE.ZIP) is sufficient to built yourself an unzipper, but the
details of the compression process are left out, making it harder to construct
your own zipper.

As far as I recall, the sliding dictionary is either 4k or 8k long, and its
output is a mixture of litteral characters and (distance, length) pairs.
Litterals are 8 bits, distances either 12 or 13 bits and lengths 6 bit.
The distance/length pairs indicate a string of length bytes which has already
occurred in the input distance bytes back. Literal bytes are used when no long
enough match could be found in the buffer.

The output of the sliding dictionary is then compressed using Shannon-Fano
trees. These are just like Huffman trees, only the algorithm to construct them
is different (Top-down instead of bottom-up). Separate trees are used for the
upper six bits of the distances, the lenghts, and the literals. (The
compression of litterals can be switched off however)

[The above information may be (wildly) inaccurate as it has been a long time
since I read APPNOTE.ZIP]

 -- Sander Plomp                                  sander@cwi.nl