🚀 go-pugleaf

I now have version 0.95 of a compression package implementing AP and Y
coding, two non-Huffman LZ78-style dictionary coders. Both compressors
produce somewhat smaller output than compress. AP runs at basically the
same speed as compress. Y is quite a bit slower but appears to be new
(and hence unpatented). Enclosed are BLURB and PATENTS from the package.

I plan to send the entire package to comp.sources.misc by the end of the
month. In the meantime, I'm looking for gamma testers. Gamma test means
the package has survived beta test and I think it's reasonably complete,
but it still needs more portability testing, and it's not too late to
add features if I've missed any. If you're interested in the package and
you're willing to put in some time testing it and telling me what you
think, send a note to brnstnd@nyu.edu.

---Dan

This package includes yabba and unyabba, portable implementations of Y
coding. Y coding is unpatented---unlike the LZW coding used by compress
and the LZ78 variants used by most other dictionary compressors. Y also
gives somewhat better compression than LZW.

As an extra bonus, this package also includes whap and unwhap, portable
implementations of AP coding. AP coding is patented, but like Y it is
more effective than LZW. whap runs about as fast as compress and, in its
default configuration, uses less memory; unwhap runs as fast as
uncompress and uses less than half as much memory.

The entire package is public-domain. You can copy my Y code into any
application without fear of copyrights or patents. Be aware, however,
that the current implementation is probably not too close to optimal,
and I am actively searching for a better method. If AP were not patented
I would recommend that you use it instead. For more information see
PATENTS in the package.

PATENTS:

After someone patents a product or method that he invented, he can sue
anyone who makes, uses, or sells the invention. You've probably heard
that Welch at Unisys patented LZW compression some years back, and so
Unisys can sue anyone who uses UNIX compress or any similar program.
You may not have heard that Miller and Wegman at IBM independently
discovered several compression methods, including LZW---and sent their
patent application to the Patent & Trademark Office before Welch did.
So it appears that IBM controls LZW.

How can Unisys patent something that IBM already patented? And how can
either of them patent what are obviously mathematical algorithms, when
mathematical algorithms aren't supposed to be patentable? The answer is
that the Patent & Trademark Office doesn't let mathematicians and
computer scientists become patent examiners. So none of their examiners
can recognize mathematics without a court order, and even then they have
trouble. They also can't tell that two patents cover exactly the same
algorithm when the wording is slightly different.

Practically every good compression method in the last ten years has been
patented. Modem and disk manufacturers can't ignore the possibility of
government-approved monopolies on compressors: there's too much money at
stake. So they apply for one patent after another, twisting the wording
as much as possible so that the patent examiners don't realize they're
patenting mathematics. By and large, they succeed.

On December 26, 1990, I discovered an apparently new compression method,
Y coding. I haven't found a way to make Y run as fast as compress (yet),
but it's not too slow for general use, and it produces better results
overall than any other non-Huffman dictionary compressor I've seen. I am
sick and tired of having to tiptoe through this minefield of patents; I
want a method that produces good results and can be used freely by
anyone. Well, now I have it. Everything in Y coding is public domain. No
copyrights, no patents, no protection at all, on the code or on the
algorithms or on the file format or on anything else. I can't be totally
sure, of course, that I'm the first to discover Y, but everyone I've
talked to thinks it's new. Use it as you will.

Several months before I found Y coding, I found what I now know to be
Storer's AP coding. At first I thought it was new, and I started putting
together an implementation. It's quite a bit faster than my Y
implementation---even faster than compress on some machines---and uses
less memory. But it has turned out to be patented. I've included the
code in my Y package because I don't want my work to go to waste, but it
can't be used freely. You can use AP for what's sometimes called
``experimental use''; the precise wording in most court cases is ``for
the sole purpose of satisfying philosophical taste or curiosity, or for
instruction and amusement.'' Patents never apply to that sort of use.

If you like AP's efficiency and want to start using it for more than
satisfying your philosophical curiosity, you might be tempted to ask
Storer for a license. Don't give in! First, his patent---any compression
patent---is on very shaky ground, and as it hasn't been acknowledged in
the industry, it's even weaker. Second, you can challenge the patent by
sending the Patent & Trademark Office about $2000 and an explanation of
why AP is a mathematical algorithm. Now you may not have the money or
lawyers or time or energy to do this successfully, but there are a lot
of people who feel just as restricted. You should check up on the League
for Programming Freedom; if you don't subscribe to their political goals
but still want to get rid of compression patents, send me a note. In any
case this will be cheaper on everyone than paying Storer for something
he shouldn't even control. Third, Y isn't that much slower than AP, and
it compresses just as effectively. Chances are good that I or someone
else will find a faster implementation soon. Finally, we may be able to
convince Storer to donate his patent to the public good. If you want to
appeal to his morals, send a note to storer@cs.brandeis.edu, copy to
brnstnd@nyu.edu.

Disclaimer: I'm not a lawyer. I'm just an outraged citizen.

---Dan Bernstein, brnstnd@nyu.edu