Lempel–Ziv Compression

At the Technion in Haifa, computer scientist Abraham Lempel and information theorist Jacob Ziv published "A Universal Algorithm for Sequential Data Compression" (LZ77) in 1977, followed by LZ78 in 1978. Their key idea was that a compressor need not know the statistics of the data in advance: it replaces repeated strings with short references to earlier occurrences, building its dictionary as it reads. The method works well on almost any kind of data and is fast to decode.

Terry Welch's 1984 variant, LZW, powered GIF images, the TIFF format and the Unix compress tool, while LZ77 combined with Huffman coding became DEFLATE, the engine of ZIP, gzip, PNG and web page compression. Nearly every computer and phone runs Lempel–Ziv methods daily. The work was named an IEEE Milestone in 2004, and Ziv received the IEEE Medal of Honor in 2021.