Hi folks,

This week we are going to tell you a short story about LZW compression and how it influenced three widespread graphics file formats: TIFF, GIF, and PNG.

How it started

The story began in 1977 and 1978 when Israeli computer scientists Abraham Lempel and Jacob Ziv published descriptions of lossless data compression algorithms named LZ-77 and LZ-78, respectively.
Terry Welch, an MIT trained computer scientist, further developed the LZ algorithms and, in 1984, he published the Lempel-Ziv-Welch (LZW) algorithm.

LZW compression became the first widely used universal data compression method on computers.
Being so influential, the “LZ-” based various algorithms became, of course, subject to patent protection in many countries.
For LZW, two patents were issued in the USA (but in other countries as well), the one filed by Welch himself being assigned to Sperry Corporation (Welch’s employer) in 1983.
Sperry Corporation became Unisys in 1986.

How does it work

So.
Just to have a glimpse on the algorithm, consider this string: “The cat chases the mouse in the room.”
The word “the” occurs three times.
Replace it by “!” and the string becomes: “! cat chases ! mouse in ! room”.
Add this association (“the” to “!”) to an index, and you’ve reduced the length of the string from 36 to 30 characters.

Of course, things are way more complicated than this, but the main idea is that the algorithm works very well when there are many repetitive data.
And image files usually contain lots of repetitive data.

Battle of the formats

In 1986, Aldus Corporation released the first official TIFF specification, and in 1988 revision 5.0 was released, which included the ability to use LZW compression.
In 1987, CompuServe created the GIF file format, the GIF specification requiring the use of the LZW algorithm to compress the data stored in each GIF file.

The holder of Welch’s LZW patent, Unisys (which maintains a portfolio of about 1500 patents), was motivated to monetize this patent as much as possible and it had to be fast, too, as the patent availability was 20 years.
Overall, the total number of licensees was about 100, among which Adobe was licensed in 1990 for the use of LZW patent for PostScript and Aldus was licensed in 1991 for the use of the Unisys LZW patent in TIFF.

Licensed LZW in TIFF generated a wave of discontent, so Aldus quickly introduced JPEG compression in TIFF (as of revision 6.0 in June 1992) but it had serious design errors and limitations, making things even worse (this was later corrected and replaced with a totally new TIFF/JPEG specification).

But it was not before 1993 that Unisys finally became aware that the GIF file format, very popular already, was using their patent-protected LZW algorithm.
And CompuServe had no clue they were infringing on LZW patent.
In 1994 Unisys and CompuServe came to an understanding which, for various reasons, generated a huge protest reaction, the matter being reported by many newspapers including the Time Magazine.

Many upset developers and users removed their GIF files or converted them to JPEG (yes, JPEG again, it’s royalty-free!).
But JPEG uses lossy compression, so one of the protesting groups, formed by leaders of the online graphics community, began working on a lossless and patent-free version of GIF.

Their efforts produced the PNG specification.

Epilog

As an epilog, by 2004 all Welch (i.e., Unisys) LZW patents expired in all countries where they were issued (IBM patent on LZW expired by 2006).

  • TIFF specifications are now controlled by Adobe and LZW can be freely used with it.
  • Adobe uses for PDF an LZ-77 based compression algorithm named “DEFLATE.”
  • GIF format is still popular.
  • PNG became one of the most important graphics file formats in the world.

In the upcoming articles, we will provide some explanations on bitmaps as well as some short overviews on the most common bitmap file formats, including TIFF, GIF, and PNG.

Bye for now!

Bogdan

10/17/2019 edit

If you want to learn more about compression and hyper-compression of images and PDF files, we have some resources for you:

And also, if you wish to challenge our engines (based on our GdPicture.NET SDK) “live” with your documents, you can try our AvePDF widgets below: