CompuServe Messages

This is a section of the "Data Compression FAQ" available on the Internet which deals with patents for algorithms such as the one for LZW held by UniSys that is just now being exploited for the so-called "Gif Tax". If there's enough interest I can upload the entire FAQ somewhere – it's a bit over 5000 lines / 86k zipfile. —————————————————————————– What about patents on data compression algorithms? All patents mentioned here are US patents, and thus probably not applicable outside the US. (a) Run length encoding – Tsukiyama has two patents on run length encoding: 4,586,027 and 4,872,009 granted in 1986 and 1989 respectively. The first one covers run length encoding in its most primitive form: a length byte followed by the repeated byte. The second patent covers the 'invention' of limiting the run length to 16 bytes and thus the encoding of the length on 4 bits. Here is the start of claim 1 of patent 4,872,009, just for pleasure: 1. A method of transforming an input data string comprising a plurality of data bytes, said plurality including portions of a plurality of consecutive data bytes identical to one another, wherein said data bytes may be of a plurality of types, each type representing different information, said method comprising the steps of: […] – O'Brien has patented (4,988,998) run length encoding followed by LZ77. (b) LZ77 – Waterworth patented (4,701,745) the algorithm now known as LZRW1, because Ross Williams reinvented it later and posted it on comp.compression on April 22, 1991. (See item 5 for the ftp site with all LZRW derivatives.) The *same* algorithm has later been patented by Gibson & Graybill (see below). The patent office failed to recognize that the same algorithm was patented twice, even though the wording used in the two patents is very similar. The Waterworth patent is now owned by Stac Inc, which won a lawsuit against Microsoft, concerning the compression feature of MSDOS 6.0. Damages awarded were $120 million. – Fiala and Greene obtained in 1990 a patent (4,906,991) on all implementations of LZ77 using a tree data structure. Claim 1 of the patent is much broader than the algorithms published by Fiala and Greene in Comm.ACM, April 89. The patent covers the algorithm published by Rodeh and Pratt in 1981 (J. of the ACM, vol 28, no 1, pp 16-24). It also covers the algorithm previously patented by Eastman-Lempel-Ziv (4,464,650), and the algorithms used in lharc, lha and zoo. – Notenboom (from Microsoft) 4,955,066 uses three levels of compression, starting with run length encoding. – The Gibson & Graybill patent 5,049,881 covers the LZRW1 algorithm previously patented by Waterworth and reinvented by Ross Williams. Claims 4 and 12 are very general and could be interpreted as applying to any LZ algorithm using hashing (including all variants of LZ78): 4. A compression method for compressing a stream of input data into a compressed stream of output data based on a minimum number of characters in each input data string to be compressed, said compression method comprising the creation of a hash table, hashing each occurrence of a string of input data and subsequently searching for identical strings of input data and if such an identical string of input data is located whose string size is at least equal to the minimum compression size selected, compressing the second and all subsequent occurrences of such identical string of data, if a string of data is located which does not match to a previously compressed string of data, storing such data as uncompressed data, and for each input strings after each hash is used to find a possible previous match location of the string, the location of the string is stored in the hash table, thereby using the previously processed data to act as a compression dictionary. Claim 12 is identical, with 'method' replaced with 'apparatus'. Since the 'minimal compression size' can be as small as 2, the claim could cover any dictionary technique of the LZ family. However the text of the patent and the other claims make clear that the patent should cover the LZRW1 algorithm only. (In any case the Gibson & Graybill patent is likely to be invalid because of the prior art in the Waterworth patent.) – Phil Katz, author of pkzip, also has a patent on LZ77 (5,051,745) but the claims only apply to sorted hash tables, and when the hash table is substantially smaller than the window size. – IBM patented (5,001,478) the idea of combining a history buffer (the LZ77 technique) and a lexicon (as in LZ78). – Stac Inc patented (5,016,009 and 5,126,739) yet another variation of LZ77 with hashing. The '009 patent was used in the lawsuit against Microsoft (see above). Stac also has patents on LZ77 with parallel lookup in hardware (4,841,092 and 5,003,307). – Robert Jung, author of 'arj', has been granted patent 5,140,321 for one variation of LZ77 with hashing. This patent covers the LZRW3-A algorithm, also previously discovered by Ross Williams. LZRW3-A was posted on comp.compression on July 15, 1991. The patent was filed two months later on Sept 4, 1991. (The US patent system allows this because of the 'invention date' rule.) – Chambers 5,155,484 is yet another variation of LZ77 with hashing. The hash function is just the juxtaposition of two input bytes, this is the 'invention' being patented. The hash table is named 'direct lookup table'. –continued next message– [More] –continued from previous message– (c) LZ78 – One form of the original LZ78 algorithm was patented (4,464,650) by its authors Lempel, Ziv, Cohn and Eastman. – The LZW algorithm used in 'compress' is patented by IBM (4,814,746) and Unisys (4,558,302). It is also used in the V.42bis compression standard (see question 11 on V.42bis below) and in Postscript Level 2. (Unisys sells the license to modem manufacturers for a onetime $25,000 fee.) The IBM patent application was filed three weeks before that of Unisys, but the US patent office failed to recognize that they covered the same algorithm. (The IBM patent is more general, but its claim 7 is exactly LZW.) – AP coding is patented by Storer (4,876,541). (Get the yabba package for source code, see question 2 above, file type .Y) (d) arithmetic coding – IBM holds many patents on arithmetic coding (4,286,256 4,295,125 4,463,342 4,467,317 4,633,490 4,652,856 4,891,643 4,905,297 4,935,882). It has patented in particular the Q-coder implementation of arithmetic coding. The arithmetic coding option of the JPEG standard requires use of the patented algorithm. No JPEG-compatible method is possible without infringing the patent, because what IBM actually claims rights to is the underlying probability model (the heart of an arithmetic coder). (See the JPEG FAQ for details.) AT&T has 3 patents on arithmetic coding (4,973,961, 5,023,611, 5,025,258). (e) predictor – The 'predictor' algorithm was first described in the paper Raita, T. and Teuhola, J. (1987), "Predictive text compression by hashing", ACM Conference on Information Retrieval This algorithm has been patented (5,229,768) by K. Thomas in 1993. It is used in the Internet Draft "PPP Predictor Compression Protocol" (see venera.isi.edu:/internet-drafts/draft-ietf-pppext-predictor-00.txt). As can be seen from the above list, some of the most popular compression programs (compress, pkzip, zoo, lha, arj) are now covered by patents. (This says nothing about the validity of these patents.)