Origin

Data compression is classified into two categories: lossy compression, like MP3 and JPEG, which sacrifices some data for size reduction, and lossless compression, where data is preserved while still achieving significant file size reduction.

The journey began in 1948 when Claude Shannon laid the groundwork for information theory, prompting research into optimal coding for data compression. Shannon and Fano were the pioneers of the Shannon-Fano coding method, which organizes symbols into a binary tree. However, it lacked optimality, as it did not produce a prefix code, leading to potential ambiguities in decoding.

During his tenure at MIT, Fano posed a challenge to his students: improve upon existing compression algorithms or take the final exam. Graduate student Huffman opted for the former and, despite initial struggles, conceived the Huffman algorithm—a method that builds a binary tree based on character frequency, ensuring no encoding serves as a prefix to another and minimizing total encoding length.

Despite its brilliance, the Huffman algorithm has a significant drawback: it relies on prior knowledge of character frequencies, which is often unfeasible.

Breakthrough

In the 1970s, the emergence of the internet magnified the need for dynamic compression techniques. It was then that Ziv and Lempel, collaborating from the Technion-Israel Institute of Technology, sought to address this challenge. Ziv's strength in statistics complemented Lempel's prowess in computer science and Boolean algebra.

During a sabbatical at Bell Labs in 1977, the duo produced a groundbreaking paper titled "A Universal Algorithm for Sequential Data Compression." They introduced an innovative "sliding window" algorithm that focuses on identifying repeated data sequences rather than relying on character frequencies. This development, known as LZ77, operates effectively without preprocessing and achieves remarkable compression ratios in a single pass.

In the following year, they further refined their approach, resulting in LZ78, which enhanced data reconstruction from compressed formats.

Chaos

Despite its immense potential, the LZ algorithm initially languished in obscurity. It wasn't until 1984 that Terry Welch of DEC developed the LZW algorithm, which built upon LZ and became integral to Unix's compress program. As Unix gained popularity, so did the LZ algorithms, ushering in a period of intense competition.

In 1985, Thom Henderson created ARC, software that could compress multiple files, addressing the inefficiencies of slow dial-up internet. The following year, Phillip Katz discovered ARC, but found its speed lacking. He revamped the core components in assembly language, launching PKARC.

This led to a legal battle when Henderson accused Katz of plagiarism, with ARC ultimately prevailing in court. Undeterred, Katz combined the LZ77 and Huffman algorithms to develop a new compression method called deflate, alongside the ZIP file format and PKZIP software. PKZIP quickly eclipsed ARC in both speed and efficiency, establishing dominance during the DOS era.

The open nature of the ZIP format led to the creation of the open-source info-zip group, which released free tools for ZIP and unzip functionalities. Later, Jean-loup Gailly and Mark Adler introduced gzip, based on deflate, which eventually replaced compress on Unix systems.

In 1991, Nico Mak developed a user-friendly front-end for PKZIP, known as WinZip, allowing users to compress files through a graphical interface. WinZip’s success stemmed from its accessibility, quickly becoming a staple in the 1990s before Windows integrated ZIP functionality directly into its operating system.

Conclusion

From LZ77 to LZW, compress, deflate, and gzip, the evolution of lossless compression algorithms has culminated in a vast network of technologies. Despite their variations, the core principles remain true to the original LZ algorithm. These algorithms play a crucial role in compressing images, text, and data transmitted over the internet, significantly impacting our daily digital interactions. It is no exaggeration to assert that the LZ algorithm and its successors have profoundly influenced the technological landscape of today.