🚀 go-pugleaf

In article <CARLTON.91Jan26141644@husc8.harvard.edu> carlton@husc8.harvard.edu (david carlton) writes:
> does anybody know what
> happened with that?

Well, yes. The question is who wants to spend the hours telling you. :-)

The best non-Huffman variant of LZ/LZW/MW is Storer's AP coding, which I
independently discovered and implemented last year. After I found out
that Storer had discovered the method first (and patented it), I tried
to negotiate with him, but he doesn't seem interested in helping people
if he doesn't make some money off the deal.

I now have a compression program that produces typically 10-20% better
results than compress, can be compiled to use under half as much memory
as compress for decompression and the same amount for compression, runs
at basically the same speed, is easier to configure, compiles and runs
on 16- and 32-bit machines under practically any sane C implementation,
and can prep its output for encryption.

If James Storer agrees to let everyone use the program without
restriction, I will place it into the public domain and distribute it
through USENET; since RMS was interested in my squeeze program and since
the new program is better in almost all respects, I imagine he'll pick
it up for GNU. Send a polite note to storer@cs.brandeis.edu if you would
like to see this happen.

In the meantime, I'm not sure that even a few hundred messages would
convince Storer, so here's a method that appears to be unpatented. For
the record, I found Y coding December 26. It gives slightly better
results than LZW and codes somewhat faster than AP. On the other hand,
decompression is about as slow as compression and uses more memory.

Y coding: Start with a dictionary of all single characters. At each
input position, add a new string to the dictionary. The new string is
the longest match between the current position and the dictionary, plus
one further character in the current position.

Constructing the dictionary and printing output are entirely
independent. To do the latter, simply output a code for the longest
match against the dictionary constructed so far, advance past that
match, and repeat. (``So far'' means taking into account only strings
constructed without having to look at the start of the current match.)

For example, take the input string yabbadabbadabbadoo!!!!. These strings
are added to the dictionary, one starting at each input position: ya,
ab, bb, ba, ad, da, abb, bba, bad, ada, dab, abba, bbad, bado, ado, do,
oo, o!, !!, !!!. One way to look at this generation is that bbad is
added to the dictionary as soon as bb.*bba.*bbad appears in the input.

Now you read off the coding as follows: Read y. y matches the dictionary
constructed up to the previous character, so keep going. Read a. ya
doesn't match the dictionary constructed up to the previous character,
so output the code for y. Read b. Output a. etc. The final outputs are
y, a, b, b, a, d, ab, ba, da, bba, d, o, o, !, !, !!.

Another example: pickypickypickypickypicky! codes as p, i, c, k, y, pi,
ck, yp, ick, ypi, ckyp, icky, !. You can see that strings of any length
can be added to the dictionary rather quickly, so although this has a
similar flavor to LZJ it is certainly not equivalent.

Anyway, I place Y coding into the public domain; unless somebody else
has snuck a patent in somewhere, you're free to use the method in any
program. I'm working on rewriting my AP program for Y coding, though I
think AP is somewhat better, and I don't particularly want to optimize
yet another compressor if Storer's willing to allow use of the current
one.

---Dan