Jacob Ziv — The Man Who Compressed The World

I am so pleased to see that Jacob Ziv has received the IEEE Medal of Honor. Along with Abraham Lempel, he created two lossless compression methods (LZ-77 and LZ-78) and which are the basis of a wide range of compressed file types including ZIP and GIF/PNG files. In many previous compression methods, there was some loss of bits when decompressing, but Lempel and Ziv found a way to compress data so that commonly occurring bit sequences could be represented by fewer bits than less common ones. Basically, if the sky is mainly blue with some white clouds, we give a short code for blue, and a longer one for white.

Around 1977, Abraham Lempel and Jacob Ziv developed the Lempel–Ziv class of adaptive dictionary data compression techniques (also known as LZ-77 coding), which are now some of the most popular compression techniques. The LZ-77 coding scheme is especially suited to data which has a high degree of repetition and makes back-references to these repeated parts. Typically a flag is normally used to identify coded and unencoded parts, where the flag creates back-references to the repeated sequence. An example piece of text could be:

‘The receiver requires a receipt for it. This is automatically sent when it is received.’

This text has several repeated sequences, such as ‘ is ’, ‘it’, ‘en’, ‘re’ and ‘ receiv’. For…