🚀 go-pugleaf

[I tried to post this to comp.patents without success. I apologize
if you get it twice.]

In article <1111@spam.ua.oz>, ross@spam.ua.oz.au (Ross Williams) writes:

| Rumour has it that a new data compression patent has just appeared.
| 
|    Names: ?.Graybill and Dean K. Gibson
|    Patent: #5,049,881
| 
| Does anyone know anything about this?

I don't know about 5,049,881, but I have just been informed of another one,
which happens to patent an algorithm that many people have independently
"discovered". I even hesitate to use this word, because the algorithm is just
an application of a fundamental algorithm, string searching by hashing.  The
LZ78 data compression algorithm (used in 'compress') was patended by two
companies (IBM then Unisys), and LZ77 seemed to be free of patents. It
appears that Phil Katz managed to get a patent on LZ77, used in his well
known PKZIP program:

    5,051,745                     Sep. 24, 1991
		   String searcher, and compressor using same

    INVENTOR:      Phillip W. Katz, Glendale, WI
    DATE FILED:    Aug. 21, 1990

    ABSTRACT:
    Methods and apparatus for string searching and data compression.

    In the string search method and apparatus pointers to the string to be
    searched are indexed via a hashing function and organized according to
    the hashing values of the string elements pointed to. The hashing
    function is also run on the string desired to be found, and the resulting
    hashing value is used to access the index. If the resulting hashing value
    is not in the index, it is known that the target string does not appear
    in the string being searched. Otherwise the index is used to determine
    the pointers which correspond to the target hashing value, these pointers
    pointing to likely candidates for matching the target string. The
    pointers are then used to sequentially compare each of the locations in
    the string being searched to the target string, to determine whether each
    location contains a match to the target string.

    In the method and apparatus for compressing a stream of data symbols, a
    fixed length search window, comprising a predetermined contiguous portion
    of the symbol stream, is selected as the string to be searched by the
    string searcher. If a string to be compressed is found in the symbol
    stream, a code is output designating the location within the search
    window of the matching string and the length of the matching string.

    End of abstract

The idea of string searching with hashing is certainly not new (see for
example the Rabin & Karp algorithm). Note that the patent seems to apply to
string searching in general (first part of the abstract), not only to its
application to data compression. It is not clear if the second part of the
abstract covers the LZ77 algorithm in general or only when it is implemented
using hashing. (There are other ways of implementing LZ77, such as the
patented Fiala and Greene algorithm.)

The LZ77 algorithm patented by PK (or variants of it) is already used in
several data compression programs, including those by Robert Jung (ARJ),
Yooichi Tagawa (lharc), Brad Templeton (ISP?), Leonid Broukhis (freeze),
myself (portable zip) and probably many others (Ross Williams?). [zoo and lha
also use LZ77 but with a trie instead of a hash table.] It might be difficult
to prove that these programs consistute prior art, but at least they prove
that the Phil Katz "invention" is obvious to a practioner skilled in the
field. A hashing algorithm applied to data compression was also published
by Brent in 1987.

I won't even try to enumerate the programs using string searching by
hashing outside the data compression field...

Jean-loup Gailly
jloup@chorus.fr

references:

- LZ77 refers to
  Ziv,J. and Lempel,A. 1977. A universal algorithm for sequential data
  compression. IEEE Trans. Inf. Theory IT-23, 3(May), 337-343.

- Brent,R.P. 1987. A linear algorithm for data compression.
  Aust.Comput.J. 19, 2, 64-68.