Path: sparky!uunet!munnari.oz.au!metro!cluster!...@gnu.ai.mit.edu
From: r...@gnu.ai.mit.edu (Richard Stallman)
Newsgroups: comp.patents
Subject: [SPAT] Compression Patent
Message-ID: <4928@cluster.cs.su.oz.au>
Date: 15 May 92 11:11:00 GMT
Sender: n...@cluster.cs.su.oz.au
Lines: 166
Approved: pate...@cs.su.oz.au
X-Article-Number: uklpf Msg # 28
X-Software: List-Server V 7.0
Comments: List problems/queries to <uklpf-requ...@uk.ac.daresbury>


[mod- from uk lpf mailing list]

    Wrapping an algorithm in a program can't be patented.

This is less helpful than you might think.
Here's a piece I am writing about the US situation, which is based on
the same principle.


		Patenting Algorithms and Mathematics

When the Patent and Trademark Office says, "We do not issue patents on
algorithms", they are playing a word game, like the original Lay's
Potato Chip commercial which said, "Bet you can't eat one!"

(Newer versions of this commercial have changed the wording to say,
"Bet you can't eat just one," but the first version used the ambiguous
wording quoted above.)

The natural meaning, what you think of if you don't know the trick, is
that a certain quantity (the number of chips you can eat, or the
number of algorithms covered by any patent) is less than one.  The
joke is that the real meaning of the statement is that the quantity is
much greater than one.

Software patents are not, strictly, "patents on algorithms" because no
patent covers just a single algorithm.  A claim in a patent describes
a combination of certain steps or elements.  If an algorithm involves
using all of those steps or elements, then use of the algorithm is
prohibited by the patent.

As a result, a single patent can easily make many related algorithms
off-limits to programmers.  This is why those patents impede software
development; this is the real issue that programmers mean when they
speak of "patented algorithms".  The Patent Office should face this
issue squarely rather than denying it.

Sometimes a patent covers so many related algorithms that for
practical purposes it covers all possible ways of producing a given
result.  The well-known case of LZW data compression (used in the
`compress' program and in all modems that do data compression) is an
example of this.  Experts on data compression, the discoverers of
other compression techniques, have been unable to find any method of
computing the same output as the LZW algorithm without infringing the
patents that cover it.  This particular case is important in practice
because a new modem must be able to talk with existing modems; one
could conceivably use a different algorithm to produce the output, but
it must be the same output.

Another reason software patents are not, strictly, "patents on
algorithms" is because they generally include a statement about what
the algorithm is used for.  (This may be narrow or broad.)  Thus, you
could be permitted to use the LZW algorithm for something other than
data compression.  This is of little help to programmers who need to
implement data compression--or, more generally, to use known
algorithms straightforwardly.

Scientific American (September 1991, p. 58) says the following
about Dave Huffman and Huffman coding.

   If Huffman were just starting his career, patent attorneys would
   surely be knocking on his door.  Patenting of algorithms is still
   subject to endless judicial debate.  But a lawyer today would tell
   Huffmann to ``clothe'' his code in silicon, that is, produce a
   patentable microchip that contains his code programmed into memory.
   ``I bet I could write an application that would be considered
   patentable,'' says Richard H. Stern, a patent attorney who was chief
   of the intellectual property section of the U. S. Department of
   Justice from 1970 to 1978.

The patenting of mathematical techniques is not limited to the new
fields of mathematics most closely related to computers.  In 1991,
patent number 5,031,134 was issued on a technique for numerical
integration, and integral calculus is as classical an area of
mathematics as any that exists.  Even Newton's method (used for
finding roots of a polynomial) could be patented today if it were new.

Here is a description of the LZE data compression algorithm, followed
by quotations from two different patents each of which covers the use
of this algorithm.  (Yes, this technique has been patented twice by
different people.  This is not supposed to happen, but it does.)


The LZW algorithm, as described by Daniel Bernstein in the style that
would be used in a mathematics textbook.

Notation: x~A means x is an element of A, * is the empty set.
Let functions equal their graphs. Let A be a set of size n, g
map A onto (1,...,n). As usual let A^i be the set of functions
>from (0,1,...,i-1) to A. As usual, given s~A^m, t~A^n,
u~A^{m+n}: if i<m implies u(i)=s(i), and i>=m implies
u(i)=t(i-m), then we write s+t=u, u-s=t, t<=u, s=u_m. Here x is
cross product, \union is set union, ^ is power, max is maximum,
|S| is the size of set S, >= is greater-than-or-equal-to, PS is
the power set of S.

Algorithm W: Fix I~\union_{n>=0}A^n. Consider pairs
(k,D)~N_0xP(\union_{n>=0}A^n x N_0). Put f(k,D)=(k',D') if
k'=max{j:I_j-I_k~Dom D}, D'=D\union{(I_{k'+1}-I_k,|D|+1)}. Now
iterate f^i(0,g)=(k_i,D_i) and form the sequence D_i(S_{i+1}) as
long as S_{i+1} is in D_i, where S_{i+1}=I_k_{i+1}-I_k_i.


Claim 1 from United States Patent 4,558,302, Dec. 10, 1985, "High speed
data compression and decompression apparatus and method":

1. In a data compression and data decompression system,
compression apparatus for compressing a stream of data character
signals into a compressed stream of code signals, said
compression apparatus comprising

storage means for storing strings of data character signals
encountered in said stream of data character signals, said
stored strings having code signals associated therewith,
respectively,

means for searching said stream of data character signals by
comparing said stream to said stored strings to determine the
longest match therewith,

means for inserting into said storage means, for storage
therein, an extended string comprising said longest match with
said stream of data character signals extended by the next data
character signal following said longest match,

means for assigning a code signal corresponding to said stored
extended string, and

means for providing the code signal associated with said longest
match so as to provide said compressed stream of code signals.


Claim 1 from United States Patent 4,814,746, Mar 21, 1989, "Data Compression
Method".


1. A method for data compression of individual sequences or strings of
symbols arranged in a data stream, comprising the steps of:

initializing a dictionary consisting of a set of strings with an index
for each of said strings and including all possible strings of length 1;

setting a current input position at the beginning of said data stream
and repeating the following steps until the data stream to be compressed
is exhausted;

determining a longest string S in said dictionary which matches a current
string in the data stream starting from the current input position;

generating an identifier I for S consisting of an encoding of the index
associated with said longest matching string S;

advancing the current input position to immediately after said current
string in the data stream;

modifying said dictionary based on the preceding longest matched string S,
the immediately succeeding symbols in the next string in the data stream,
and the sequence of previously matched strings;

transmitting I to a utilization device; and

decoding I at said utilization device to recover said string S.