How it began
Abraham Lempel and Jacob Ziv developed the algorithm in 1977 at the Technion, the Israel Institute of Technology, in Haifa. It was first published in the IEEE Transactions on Information Theory in May 1977 under the title A Universal Algorithm for Sequential Data Compression. Lempel taught computer science at the Technion from 1963 and Ziv taught electrical engineering there. According to Ziv, Lempel concentrated on the practical aspects while he focused on the theory.
How it works
The algorithm replaces strings of characters with single codes called tokens. Each time it meets a new string it outputs the string and adds it to a table, or dictionary. The next time that string appears, it outputs only the code. The first 256 codes are assigned to the standard 8-bit character set, so a 12-bit code allows a dictionary of almost 4,000 tokens. Because the string is sent along with the token the first time, the receiver can rebuild the original message without being sent the dictionary.
How it spread
Ziv and Lempel followed the 1977 paper with a second one, Compression of Individual Sequences via Variable-Rate Coding, in the same journal in September 1978. IEEE Spectrum describes the Lempel-Ziv work as having paved the way for the GIF, PNG and ZIP file formats. The IEEE plaque states that the algorithm became a basis for enabling efficient data transmission over the internet.
What lasted
On September 6, 2004, the IEEE dedicated a Milestone plaque for Lempel-Ziv Data Compression in the front lobby of the Technion building in Haifa, with both authors present. The citation credits the 1977 algorithm with making efficient internet data transmission possible. Lempel retired from the Technion in 2004. Both men died in 2023, and IEEE Spectrum remembered Ziv as co-author of the algorithms behind GIF, ZIP and other formats.
