Abraham Lempel

Lempel co-invented the LZ77 and LZ78 lossless data compression algorithms with Jacob Ziv, publishing them in the IEEE Transactions on Information Theory in 1977 and 1978 respectively. LZ77 uses a sliding-window approach and LZ78 builds an explicit dictionary, and together they established the two foundational paradigms of dictionary-based compression.

ZIP uses DEFLATE, which combines LZ77 with Huffman coding, while GIF uses LZW, a variant of LZ78 developed by Terry Welch in 1984. PNG also uses a variant of LZ77, and gzip, 7-Zip, and many document formats all rely on algorithms descended from the 1977 and 1978 Lempel-Ziv papers.

Unisys, which held the patent on the LZW algorithm used in GIF, began enforcing licensing fees against software developers and websites using GIF images in the mid-1990s. This controversy motivated the creation of the PNG format as a patent-free alternative, and the relevant patents expired in the early 2000s.

Lempel was a professor at the Technion – Israel Institute of Technology in Haifa, where he and Jacob Ziv developed the LZ algorithms in the late 1970s. He later led data compression research at HP Labs in Israel and held numerous patents related to compression technology.