🚀 go-pugleaf

While I'm working on recreating the source to LZES1,5 and 6, I
thought that (actually was hounded into :-) I should describe
the basic outline of the algorithm.  LZES1 was the fastest of the
algorithms, averaging about 100K/sec on a 7 Mhz 68000.  LZES5 
was the fastest at it's compression level, which produced an
archive about 10-20% smaller (relative) than compress -b 16.
LZES6 was a compromise between the two, usually beating
compress -b 16.

As an overview, the LZES algorithms are an LZ77 derivative, with
a few twists.  All versions use a dictionary with 4K entries,
though only LZES5 will usually use all of them.  They all produce
a compressed file with the same format, and the same decompressor
is used for all variants. LZES5 and 6 outcompress LZRW algorithms
1,2 and 3, as well as 3a in most cases, though they are not faster
than 1, 2, or 3.

The basic file format is similar to the LZRW file format, in that
everything is composed of WORDs, with literals packed two to a word,
and buffered.  The basic stream consists of one WORD of flags
indicating whether the next 16 tokens are literals or copy-tokens, then
the tokens themselves.  I'm not good at explaining, so you may want to
see the LZRW documentation for a better description.

The major differences between the LZES and LZRW algorithms are simple:

	1) the copy offset is by dictionary entry, not by buffer-position
	or hash value.

	2) the copy lengths are 3-17, with one for (read in next literal,
	add 18 to it, and use that as the copy length).

The dictionary entries (there are 4096 of them) are used in a
rotating manner, with the least recently recycled entry recycled to
create space for the new entry.  You create entries only where
you send tokens (literals or copy commands), so if you were compressing
"abc123", you didn't match "abc", but you did match "bc12", and sent 3 as
a literal, you would have added 3 dictionary entries.

The cost of this is the need for a larger buffer (4K entries on
byte boundries is 4K, but 4K on token boundarys can be huge (though past
32K, the compression ratio doesn't seem to improve much).  

The benefit is that you only need to add one dictionary entry per
token, even if you match 10 or more literals.

Now, that will improve the speed, but not by an incredible amount.
The real trick is my binary-tree search method.  I start off with an array 
of pointers, 2 dimensional, with X and Y size of the max unsigned char
value+1, or 256 on a machine with 8-bit chars.  This array's base type
is a pointer to a dictionary entry.  Then, under that is a binary tree.
Since you have 4096 dictionary entries spread out between 65356 nodes,
I find you will seldom have to traverse more than 3 or 4 nodes in the
binary tree before reaching the bottom, so your time for that is
small too.  Of course, that table is 256K contiguous.

Each Dictionary entry is a structure like this:

	struct entry {
		char *buffer;
		struct entry *r-child;
		struct entry *l-child;
	}
/* actually, I padded it to 16 bytes so I could just subtract the start,
or the copy length, and output that value */

So when you get the pointer to the first entry from the array (which can be cut
down to a single dimension, saving tons of memory), you then have a 
node to compare to.  Note that you don't need to compare the first two
chars, since they are automatically identical.  you match as long as you can,
then when you don't match, you compare the first non-matching character
to determine whether to look at the right child or the left child.  You follow
the binary tree until you find a NULL pointer, then insert the new entry at that
location, so you only traverse the tree a single time.

Actually, the binary tree isn't what speeds up this algorithm over a regular
search it's the charXchar array front end, with the binary tree only taking
effect if there are a lot of collisions.

Future Ideas:  These are things I haven't implemented yet, but have thought
about.

Rather than recycling the least recently recycled dictionary entry,
recycle the least recently used entry.  This will complicate the programming,
since the entries are no longer in order, and your buffer can be stretched out
for the entire length of the document.  It will also slow down decompression
(currently faster than anything I have found except for LZRW1/2).

Add a static-huffman layer (static as same table for entire file, not
same table for all files).  This should put the algorithm close to LHA or ZIP
compression levels, though costing a little more speed.

Add something like Info-Zip's lazy matching, but on the tail end.  IE if
we use a match length of 10, then match 3 characters somewhere else, check
to see if we only match 9, can we match 4 or more right after that.

Since my current encoder never sends the current index (the one it will
create this time), let that index represent (continue copying where the
last one left off.  That way if you get a long match, and send the first
copy command, but the remainder no longer matches since we can only use
whatever is at the start of the dictionary entry, you can still continue
to refer to the old dictionary entry.  Of course, I don't expect this to
make a fantastic difference, but it might help a little.

Here's an early message I mailed a friend concerning the speed and
compression ratios of the preliminary version of the LZES algorithms.

-----
Here's how I'm doing so far.  The 4 test files are

        twm.man, an 84433 byte man page.
        lz01, a sparc executable of 47266 bytes.
        xbm, a HUGE (230223 bytes) bitmap file for X.
        lha, the executable lha for a NeXT (213019 bytes)

FILE    lzes1   lzes2   lzes3   compress
TWM     37928   26554   32240   28481           bytes
        101.7   16.0    42.6                    K/Sec
LZ01    25520   22660   24092   25633           bytes
        82.7    16.6    32.3                    K/Sec
XBM     18499   9644    18404   12309           bytes
        274.1!! 37.0    120.1                   K/Sec
lha     93824   80619   87975   102865          bytes
        102.8   15.2    39.9                    K/Sec

Note that ALL lzes algorithms beat compress on the executables, and
the lzes2 algorithm beats compress on everything.  I'm working on a
faster version of the lzes2, but it still won't match the speed of even
lzes3.  Also, just for trivia, all three lzes algorithms use the exact same
decoder.
---
I later refined lzes2 into LZES5 and lzes3 into LZES6 so that
LZES5 ran about twice as fast as LZES2, and LZES6 ran 50% faster
than LZES3.

LZES5 is the algorithm described above, LZES6 is the same algorithm,
but only retaining the most recent entry with a given three-literal
starting sequence, and LZES1 was the same compression algorithm, but
with no tree, retaining only the most recent entry with a given
two-literal starting sequence.

-- 
Eric J. Schwertfeger, maniac@cs.unlv.edu