Danger Ahead—Patents

The fact that most work on dictionary-based compression has been done over the last ten or fifteen years has a potentially dangerous side effect. Until the early 1980s, it was generally not possible to patent software. But during the past ten years, increasingly large numbers of patents were awarded for what are clearly algorithms.

One of the first data-compression patents was granted to Sperry Corp. (now Unisys) for the improvements to LZ78 developed by Terry Welch at the Sperry Research Center. In fact, this patent became a point of contention during the standardization process for the V.42bis data-communications standard. Since V.42bis is based on the LZW algorithm, Unisys claimed the right to collect royalties on implementations which use V.42bis. There was some concern in the CCITT about the effect of basing a standard on a patented technique. Unisys dampened concern while protecting its patent rights by publicly offering to license the algorithm to any modem manufacturer for a onetime $25,000 fee.

After a hiatus of several years, Unisys recently woke from slumber and began patent-related legal maneuvers, seeking to get licensing fees from CompuServe and other users of the popular GIF format. Some in the industry viewed this request as unreasonable, given the lengthy delay between the introduction of the GIF format, and the unexpected demands for licensing fees once the format had gained wide acceptance. The response to Unisys’ effort was creative rather than contentious. Developers came together and in short order produced the PNG effort, a license-free format that contains many improvements over the existing GIF format.

As research in dictionary-based compression continues, patents are being filed at a relatively rapid pace. Since patent filings are not a matter of public record, it is not possible to know if and when certain techniques will be freely available. At present, the most prudent course for potential data-compression users would be to conduct a patent search and to contact the inventors of any techniques they intend to use.

Fortunately, manufacturers can generally come to terms on patent royalties for relatively modest terms. The danger comes when the owner of the patent is competing for the same market as a potential licensee. Unisys was only too happy to license the LZW algorithm to modem manufacturers, but it may have adopted an entirely different strategy in the online market—that of benign neglect followed by hasty demands.

In recent years, the US Patent Office has come under severe criticism from some sectors in the industry by granting patents that some consider inappropriate or undeserved. The most visible instance was the patent granted to Compton’s for simple and widely-used techniques found in its multimedia encyclopedia product. This patent was later invalidated by the Patent Office, after much debate and criticism. Another well-publicized case was the lawsuit between Microsoft and Stac Electronics, which revolved around a number of issues, including certain patents on data compression.

Regarding the general subject of software patents, the computer industry has been split along at least two points of view. One view holds that patents are inappropriate in a dynamic and innovative field such as software, in which a computer program is built using dozens if not hundreds of techniques, algorithms, and data structures (as opposed to a physical/mechanical device or product, whose design centers around a much smaller array of techniques). In the case of software, patents can stifle innovation and economic growth that benefits us all. Large, well-established companies in the industry that generally adhere to this view include Adobe and Oracle, in addition to smaller non-profit organizations such as the League for Programming Freedom (see “Afterword” at the end of this book).

Another point of view is that the patent process, while in some instances flawed and in need of overhaul, is basically well-conceived and should be preserved. Companies like IBM and Apple seem to adhere to this view. Regardless of their view, today most companies have stepped up their patent-related efforts, either as an aggressive business strategy or a precautionary self-defensive maneuver. Microsoft, for example, historically indifferent to the patent process, has bulked up for future skirmishes by hiring a phalanx of intellectual-property lawyers.

After a series of public hearings on the matter of software patents, the US Patent Office, under Commissioner Bruce Lehman, has made improvements, added resources, and modified its instructions to patent examiners so that software patents are more easily granted. Whether these changes will have a positive effect on the computer industry remains to be seen. The only certainty is that patents will continue to play a central role in the field of data compression.

Conclusion

Dictionary-based compression techniques are presently the most popular forms of compression in the lossless arena. Almost without exception, these techniques can trace their origins back to the original work published by Ziv and Lempel in 1977 and 1978. Refinements on these algorithms yield better performance at lower cost, but both types of improvements are evolutionary, not revolutionary.