🚀 go-pugleaf

In article <PCG.91Feb25215626@odin.cs.aber.ac.uk> pcg@cs.aber.ac.uk (Piercarlo Grandi) writes:
> Suppose that you do not patent your algorithm; somebody else later can
> rediscover and patent it, and then *you* have to sue the somebody and
> prove that you had prior art.

No, there's no point. The courts have said [riffle riffle riffle]
``A patent could not be infringed by the practice of any prior art.''
(Peerless Equipment Co. [now there's a name!] v. W.H. Miner, Inc.,
C.C.A. Ill.1938, 93 F.2d 98, certiorari denied 58 S.Ct. 611, 303 U.S. 
641, 82 L.Ed. 1113.)

Even better: ``It is neither wrong nor immoral for a manufacturer
deliberately to create an article on basis of prior art in order to
avoid infringement.'' (Reiner v. I. Leon Co., C.A.N.Y. 1963, 324 F.2d
648.) All you have to do is find a previous publication of the invention
and you're home free.

An interesting twist is that the courts usually won't even consider
whether the patent in question is valid. They'll just watch a dozen
experts testify that you're working within the prior art, and boom, the
case is over. Normally they would first consider the validity of the
patent, and only then consider whether you've infringed it. (This is
still backwards in some circuits.)

I am told, by the way, that electronic publication does constitute
publication for the purposes of patent law (though not necessarily
copyright law). However, evidence from a computer generally isn't
admissible in court, so anyone who saved a copy of my first announcement
of Y coding should print out a copy, sign and date it, and preferably
notarize it. Here's another copy just in case. (Can never be too
careful... [grin])

---Dan

Path: kramden.acf.nyu.edu!brnstnd
From: brnstnd@kramden.acf.nyu.edu (Dan Bernstein)
Newsgroups: gnu.misc.discuss
Subject: Re: compress algorithm patent
Message-ID: <6617:Jan2723:16:0991@kramden.acf.nyu.edu>
Date: Sun Jan 27 23:16:09 GMT 1991
References: <CARLTON.91Jan26141644@husc8.harvard.edu>
Organization: IR
Lines: 68

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