The LZW Patent

AUG 20 1985 · 12:00

Handcuffs and paperclips. Unisys patents LZW compression and quietly arms the lawsuit clock. Place: Sperry Corporation (later Unisys), patent USPTO 4,558,302 Figures: Terry Welch, author of the 1984 Communications of the ACM paper on LZ-Welch compression Terry Welch publishes A Technique for High-Performance Data Compression in IEEE Computer in June 1984. The paper describes a variant of Lempel-Ziv that uses a dictionary built on the fly during compression, so the decompressor can reconstruct the dictionary without it being sent. The compression ratios are excellent on the kind of repetitive bitmap data computer graphics produce. Sperry Corporation files for a patent. USPTO 4,558,302 issues on 10 December 1985 to Sperry. By the time CompuServe ships the GIF format two years later (see [[compuserve-ships-gif87a-1987]]), LZW is the only commercially-viable compression algorithm for the image data the format needs to carry. The format and the patent travel together for the next fifteen years. Video: Professor Brailsford explains the Lempel and Ziv dictionary lineage that Terry Welch's 1984 paper extended into LZW.