Product: Lempel-Ziv Algorithm Developers: Professor Jacob Ziv and Professor Abraham Lempel Start of Development: 1977
Distinguished Professor Jacob Ziv of the Technion’s Faculty of Electrical Engineering, and Professor Abraham Lempel of the Technion’s Computer Science Department released the LZ77 in 1977 – the original version of the Lempel-Ziv algorithm, and released the second version, LZ78, in 1978. The two versions formed the basis for essential compression formats such as TIFF, PNG, ZIP and GIF, and played a key role in PDF and MP3 formats. The technology is an algorithm for lossless compression, with no prior knowledge of properties. Many compression technologies that are currently used online in memory devices, in computers, and in telecommunications were based on this algorithm.
This algorithm, which transformed the field of file compression, emerged from an entirely different problem: Professors Ziv and Lempel, at the time young researchers at the Technion, were studying the complexity of a given sequence (or its proximity to a random sequence). They measured this by the maximum number of different strings obtained by parsing the sequence. They realized that they had come upon an effective tool for compressing sequences.
The algorithm excels in the following features:
(a) universality – there is no need for advanced knowledge of the content of the input
(b) speed – linear with a coefficient close to one
(c) optimality – for input originating from an ergodic source, as the input increases, the output tends to the optimum(entropy)
(d) the greater the input, the lower the likelihood that any other device or algorithm could outperform it.
The algorithm developers won a long list of prestigious awards, including the Institute of Electrical and Electronics Engineers (IEEE) Golden Jubilee Award, the ACM Theory and Practice Award, the Hamming Medal, and the Rothschild Award.
Despite its monumental significance and its widespread, perpetual use across the globe, the developers did not receive direct compensation for having developed the algorithm.
At zero cost, the Lempel-Ziv algorithm gave the world an effective technology that enables the quick transfer of visual and other types of data without data loss. The impact of the algorithm is apparent for companies that develop technology (telecommunication and TV companies, for example). It reaches all end users, including billions of cellphone users.
In 2004, the IEEE proclaimed the Lempel-Ziv algorithm a Milestone in Electrical Engineering and Computing.
In the picture: The Technion logo is made up of the names of the files that use Lempel-Ziv's method of data compression. Artist: Anat Har-Gil
