LZW

The LZW compression algorithm tells a singular story, that of a theoretical discovery that took years to find its practical form. It all began in 1977, when Abraham Lempel and Jacob Ziv published a hermetically-titled article in the IEEE Transactions on Information Theory: "A Universal Algorithm for Sequential Data Compression". Their work presented a method using phrase dictionaries that slide over already-read text, progressively building new patterns by adding symbols to existing sequences.

The following year, the two researchers returned to the same journal with a refined version of their algorithm. These publications remained nonetheless highly abstract, laying theoretical foundations but leaving the reader wanting when it came to concrete applications. It wasn't until 1984 that a third party entered the scene and transformed this academic work into a usable technology.

Terry Welch was working at the Sperry Research Center when he published his article "A Technique for High-Performance Data Compression" in Computer magazine. His contribution revolutionized Lempel and Ziv's approach. Welch had the idea of pre-populating the dictionary with the 256 standard ASCII characters rather than starting with an empty dictionary. This modification enabled immediate processing of all simple characters, including on their first appearance. The remaining codes, from 256 to 4095 in a 12-bit dictionary, could thus serve exclusively for newly discovered sequences.

The LZW algorithm was born, bearing the initials of its three creators. Its strength lay in its ability to detect and eliminate redundancies while guaranteeing perfect restoration of the original data. Unlike other methods, LZW never sent raw characters but only codes, generating substantial gains on files containing repetitive patterns.

A remarkable characteristic of this algorithm was its autonomy during decompression. The decoder didn't need to receive the dictionary used for compression; it could reconstruct it identically by applying the same rules as the compressor. This property made LZW memory-efficient and fast to execute.

The computer industry embraced this innovation. In 1987, CompuServe launched the GIF (Graphics Interchange Format) format, which exploited LZW to compress images. This format quickly became indispensable on early networks and then on the Internet, notably thanks to its ability to store numerous images in a single file and manage transparency. UNIX also integrated the algorithm into its compress command, while the TIFF and PDF formats adopted it for their specific needs.

LZW's performance varied considerably depending on the type of data processed. Natural language texts, rich in redundancies, suited it perfectly, as did images containing vast uniform areas. On such content, the algorithm commonly achieved compression rates of 50% or more. Binary files, however, yielded more unpredictable results: some compressed better than ordinary text, while others stubbornly resisted any processing.

The practical implementation of LZW required solving some technical puzzles. The trickiest arose during decompression, when the decoder encountered a code before having been able to define it. This baroque situation occurred with sequences of the type (string, character, string, character, string), where the algorithm emitted a code that the decompressor hadn't yet had the opportunity to create. A specific exception mechanism was therefore needed to handle these particular cases.

LZW's success story took an unexpected turn in the 1990s. Unisys, holder of a patent on the algorithm, began demanding royalties for any commercial use. This sudden claim provoked an outcry in the computing community and prompted the development of the PNG (Portable Network Graphics) format as a free alternative to GIF. The patent finally expired in 2003 in the United States and in 2004 elsewhere, at last freeing the algorithm from these legal constraints.

Dictionary size directly influenced compression efficiency. A 12-bit dictionary, capable of storing 4096 entries, often represented a satisfactory balance between compression rate and memory consumption. The algorithm gained performance with large files, as the dictionary had more opportunities to identify and reuse recurring patterns.

On small files, LZW showed its weaknesses. The storage cost of the dictionary could exceed the compression benefit, making the compressed file larger than the original. Variants like LZWS (Lempel-Ziv-Welch-Setia) attempted to dynamically adapt the strategy according to data size, with mixed success.

The LZW algorithm established enduring principles in the field of compression: the use of adaptive dictionaries, lossless compression, the importance of autonomy during decompression. It occupies a special place in the computing ecosystem. More recent methods certainly offer better compression rates, but its relative simplicity makes it an excellent pedagogical tool for understanding the fundamental mechanisms of data compression. It remains used in certain specific applications where its robustness and execution speed compensate for its limitations. In the history of information technologies, LZW remains one of the first compression algorithms to have achieved lasting commercial success and truly universal adoption.