Lempel-Ziv-Welch (LZW) is a lossless data compression algorithm that was first published by Terry Welch in 1984 as a modification of the LZ77 and LZ78 compression algorithms developed by Jacob Ziv and Abraham Lempel (Duke). It is a dictionary based compression algorithm that is relatively simple for developers to implement and is widely used in GIF file formats (SFU).
Nagivate
Prior to the development of LZW, the most common form of compression was Huffman Coding. Huffman coding works by assigning probabilities to which letter will appear next in a given text (MIT). This has complications, as each text will have a different probability for certain letters. For example: “x” is one of the least common letters in standard texts, but would appear frequently in a math text. Another complication of Huffman’s method is the inherent dependence on both the English language and the probability of similar words occurring in different documents. In response to these shortcomings, Lempel and Ziv developed a dictionary-based, adaptive compression method. Welch later improved upon this method (Duke).
LZW is a dictionary-based compression method that takes advantage of repetitive patterns (MIT). Dictionary-based compression algorithms encode the data through referencing a dictionary. LZW is based on a standard character set dictionary of 256 characters. The data will be scanned and each time the algorithm encounters a substring of characters (ie: “th”, “tr”, “the”…) that substring will be added to the dictionary and encoded with a single number. To decompress the data, LZW does not require the dictionary assignments that were featured in the compression (Duke). This is because both the encoding and the decoding programs utilize the same 256 characters. To decompress, LZW reads an assigned character and “looks up” the character in the dictionary to see what substring it was applied to. This process is repeated until the information is decoded (MIT).
The initial patents for LZW were held by the Sperry Corporation, which later became Unisys Corporation. The first patent in the LZ family was filed in 1981. US patent 4,558,302 was issued to Terry Welch and Sperry Corporation on June 20,1983 (US 4558302 A).
The LZW method has been referenced in over one hundred additional patents, including ones as recent as 2013. Companies developing patented technologies that employ LZW include Unisys, Hewlett Packard, Apple, Google, Nielsen, Cisco, & Microsoft (US 4558302 A).
Many of the patents feature variations on the common theme of lossless data compression; however, in 2007 Apple filed US patent 8751022 B2, “Multi-take compositing of digital media assets”, in 2014 Hola Networks filed US patent 20150067918 A1, “System and method of improving internet communication by using intermediate nodes, and in 2009 Nielsen filed patent US 8503991 B2, “Methods and apparatus to monitor mobile devices”. While these patents employ the LZW method and in its traditional, compression-based purpose, they move beyond simple compression and directly apply it to three modern purposes technology is being used for. While the transmission of media files and more efficient internet connectivity are hardly controversial topics, the employment of the LZW method to better monitor mobile devices brings about questions of ethicality concerning fourth amendment rights. This places the LZW compression algorithm directly in the context of one of the hottest debates over the past five years.
To better understand additional patent-related controversies involving the LZW algorithm, it is important to have a solid understanding of patents. Patents are issued by a government and give the holder the sole right to exclude others from making, using, or selling an invention (USPTO). In most cases of patent law, the term of a patent is a maximum of twenty years, but commonly can also be six or ten years. Patents expire to encourage innovation and competition in the market. Imagine if drug patents never expired! Major pharmaceutical companies could potentially charge thousands of dollars for medications and would be able to rely on that income forever. The selling price would be well above the market price and innovation in the pharmaceutical field would be stagnant. Take a moment and apply this scenario to the technology industry.
Starting in 1993, Unisys began attempting to collect licensing fees for the use of the LZW compression algorithm. Only ten years into the twenty-year patent granted to Terry Welch and Unisys (which acquired Sperry Corporation) by the United States government, Unisys was perfectly within its legal right to being collecting licensing fees. However, the Graphics Interchange Format (GIF), the most popular image format of the moment used LZW compression to reduce the file size (Cloanto).
It was not the fact that Unisys began collecting royalties on the use of the LZW algorithm that angered the masses, but rather the fact that they began collecting royalties ten years after its invention when specification and standards that employed LZW had already been set in place. To be fair to Unisys, the explosion of LZW’s use to compress different technologies was unanticipated and to maintain tabs on every technology using LZW would have taking mammoth amounts of time and manpower. It is possible that in 1993, Unisys was just finding time to come up for air and begin monetizing its product.
Regardless of what led to the timing of the decision to collect licensing fees, the tech community was outraged and a group of leaders from the graphics community got together to form the Usenet comp.graphics discussion on replacing the GIF file format (Cloanto). These talks culminated in the creatinog of the Portable Network Graphic (PNG) file in 1995. Undeterred by patents, the PNG file was expected to replace the GIF.
Ultimately, a Usenet comp.graphics discussion, Thoughts on a GIF-replacement file format, culminuated int he creation of the Portable Network Grpahics (PNG) file in 1995. Undeterred by patents, the PNG file was expected to replace the GIF.
PNG files were comparable to GIF and TIFF files in that they employed a lossless data compression method that allowed data to be decompressed and restructured bit by bit into an exact replica of the original image (libpng).Because LZW uses a table structure to compress/ decompress image files, only horizontal redundancies could be removed. PNG files are compressed using a variation on LZW—LZ77. LZ77 alows for the files to be compressed both vertically and horizontally, so PNG files are much smaller than GIF files (Dev The Web).
While I argue that PNG files did not replace GIF files because they are not animated and therefore serve a different purpose in the current moment, they have grown in popularity over the past twenty years and were used on 62.4% of all websites as of 2013, opposed to GIF’s 62.3% W3 Techs). This .1% may seem very trivial, but in 2012, GIF was ahead of PNG by over 15% (W3 Techs). *see graphic at left
On June 20, 2003, twenty years after it was filed, Unisys's US patent for the LZW compression algorithm expired. Over the next year, patents filed in Canada, Japan, Germany, Italy, France, and the United Kingdom also expired. The GIF was (completely) free at last (US patent 4558302 A).
The past ten years have witnessed a resurgence of the GIF file in popular culture. As mentioned previously, GIF files were present on 62.4% of all websites in 2013, nine years after the expiration of the LZW patent (W3 Tech). The boom in GIF popularity was inspired by nostalgia, an increase in social media, and the rise of snackable content. Snackable content is easily consumable content that aims for ease in readability. Popular examples of snackable content include sites such as Buzzfeed, which specialize in GIF-centric “listicles”.
LZW is also found in numerous patents filed in the last ten years. As mentioned previously, Nielsen filed several patents referencing LZW in conjunction with the monitoring of mobile devices while Apple referenced in terms of the transmission of media files. These not only place LZW directly in a modern context, but also speak to the way that LZW enables scalability of technology.
We can view the history of the LZW compression algorithm and the various soft technologies that it impacted through the lens of Christina Haas’ Social Dynamics, or Scientific Truth, or Sheer Human Cussedness: Design Decision in the Evolution of User Interface.
In this chapter, Hass argues that evolution in technology is not “inevitable or self-determining” but that they are driven by human factors—such as stubbornness (137). This stubbornness inspiring innovation and evolution of technology is seen directly in the PNG file format. While the PNG file offers a lossless image format that is preferred by many graphic designers today, it was invented not to fill that purpose, but to replace the GIF after an argument arose in the tech community. While we cannot discount the fact that the PNG file plays a different role than the GIF file, we need to note that we able to rather clearly view the evolution of PNG through Haas’ framework of cussedness.
The history of the LZW algorithm’s usage can also be viewed through the Vygotskian framework. The main argument of Vygotsky’s framework is that social interaction has a crucial role in the development of cognition. The manner in which LZW is used has evolved drastically over time and these changes can be attributed to a variety of forms of social interaction—be they the desire to send easy to interpret animated files, monitor the communications and social interactions of others, or more effectively transmit media to peers. These social interactions have also inspired the conflicts (or cussedness) that have inspired alternatives to using the LZW method.