🚀 go-pugleaf

The compression method used by PkZIP is identical to that used by LHARC
(that is, Lempel-Ziv/Storer-Syzmanski plus Huffman; sorry no refs), except
that instead of the frequency-fixed Huffman used by Yoshi, PK uses two
or three Shannon-Fano trees to compress separately the length, offset, and
literal (if necessary) components of the data stream.

The exact LZSS method is to keep a 4096 (or 8192) byte sliding dictionary;
you then read in data and search for as long a match as possible in the
dictionary.  You then emit a code giving the offset into the buffer and the
length of the match found, and continue; if no match is found, then emit a
literal character and try again.

Yoshi's hand-tuned Huffman and Katz's Shannon-Fano arrangements run at
about the same compression rate, all things considered, with a slight
edge to PK.  I haven't tried it yet, but there is a program out there which
uses an adaptive arithmetic second stage, which may or may not perform
better.

-GAWollman

--
"Sorry, my .signature's in Baltimore."
   - me