What is the achievement of Jacob Ziv, a pioneer of data compression, and his half-life?


Lance Fisher

Music streaming and image / video transfer are technologies that are indispensable in modern society, but in order to use these technologies, it is indispensable to 'compress a huge file size to a small size' as a premise. IEEE Spectrum's Techra Perry is approaching what was revolutionary and how such lossless compression technology was created, and the half-life and achievements of its creator, Jacob Ziv.

From WinZips to Cat GIFs, Jacob Ziv's Algorithms Have Powered Decades of Compression --IEEE Spectrum

◆ What is lossless compression technology?

There are two main types of

compression for music and image files: ' lossless compression ' and 'lossy compression'. In general, lossy compression is often used. For example, converting a obtained music file to MP3 or converting a digital image to a JPEG file corresponds to lossy compression.

Lossy compression uses a method called 'removing bits from digital data.' Since the data in the part that is difficult for human senses to perceive is deleted, the deterioration is not noticeable, but since some data is lost due to compression, the compressed data cannot be restored.

On the other hand, regarding lossless compression called 'lossless compression,' Perry describes it as 'just like magic.' Lossy compression is the same as lossy compression in that it erases bits to reduce the file size and facilitates storage and transfer, but lossless compression says that the erased bits can be restored by a command. The big difference is.

Jacob Ziv was the creator of the algorithm that enables such lossless compression.

Jiv, along with computational scientist

Abraham Lempel , published a paper in 1977 entitled 'A universal algorithm for sequential data compression.'

Lossless compression technology that continues to the present day is based on this paper, and without the algorithm 'LZ77' published in the paper, the format of GIF or TIFF might not have been born. It's possible that humans couldn't email large files and shipped them to disk, continued to buy CDs instead of music distribution, or couldn't watch videos on Facebook or Twitter.

As mentioned above, Mr. Jiv received the 'IEEE Medal of Honor' in 2021 for his outstanding contributions to information theory and data compression technology and his outstanding leadership in research.

◆ Half-life of Jacob Ziv, creator of lossless compression technology

Jiv was born in 1931 in the Israeli city of

Tiberias as a child of Russian immigrants. Jiv, who was a kid who came up with the idea of turning a music stand into a lamp while practicing the violin, enrolled in Technion-Israel Institute of Technology to study electrical engineering as he grew up. He received his PhD in science in 1955 and was engaged in the development of communication systems as a senior researcher at the Israeli Ministry of Defense until 1959.

Regarding the development at the Israeli Ministry of Defense, Mr. Jiv recalls, 'No engineer in the group, including myself, had a more basic understanding of electronics.' 'The six of us had to teach each other. Choose a book and study together ... like a Jew studying the Hebrew Bible. That wasn't enough,' said Jiv. Is talking.

The goal of this research group was to build a telemetry system using transistors instead of vacuum tubes. The research group also called Bell Labs in the United States and asked them to send 100 transistor samples.

Later, Jiv was selected by the Israeli Ministry of Defense as one of several researchers studying in the United States. Since this study abroad program allowed researchers to freely choose their research field, Mr. Jiv decided to study communication technology at the Massachusetts Institute of Technology (MIT).

After studying information theory and communication technology in the United States for two years, Jiv was in charge of the communication department at the Israeli Ministry of Defense after returning to Japan. Then in 1970 he became a faculty member at Technion-Israel Institute of Technology.

At Technion-Israel Institute of Technology, Jiv met Lempel, co-author of a lossless compression algorithm treatise, and began discussing improvements in lossless compression.

◆ Algorithm 'LZ77' that started everything

The Huffman code was at the forefront of lossless compression at the time. The Huffman coding approach begins by searching for a sequence of bits in a data file and sorting them in order of frequency. Then, assign a short bit string to the most frequent characters and a long bit string to the characters that do not appear often, and the encoder creates a dictionary of encoding.

Huffman coding is still used in Lossless JPEG etc. even in modern times, but the point that data must be read in two parts, 'to calculate the frequency of data' and 'to encode data'. Is a drawback. It was also pointed out that saving the code 'dictionary' together with the encoded data would increase the size of the compressed file.

After many discussions trying to solve this problem, they came up with the idea of an algorithm that 'looks for a unique sequence of bits and compresses the data at the same time.' LZ77, which was created based on this idea, encodes the data in order from the beginning, and each time it checks whether the sequence of interest 'has appeared before'. And if it is an existing sequence, replace the symbol string with a pointer to the existing sequence. This method was epoch-making in that the data could be read only once and the processing time was greatly reduced.

After that, they developed an algorithm called LZ78, which was an extension of LZ77 in 1978. LZ78 is similar to LZ77 in that it encodes data from the beginning, but the point is to encode while making predictions.

At the time, Lempel and Jiv were also faculty members at Technion-Israel Institute of Technology, while Lempel also worked at Sperryland and Jiv at the Bell Labs. Jiv thought about patenting the algorithm he developed, but until the 1980s in the United States, software patents weren't granted and could only be patented as part of the hardware. And Bell Labs wasn't interested in patenting the algorithm as part of the hardware.

Meanwhile, Lempel's employer, Sperryland, is willing to implement the algorithm in hardware and obtain a patent. The two patented the algorithm by implementing the LZW , announced in 1984, on hardware.

◆ Many achievements of Mr. Jiv

Although Mr. Jiv regrets not being able to obtain a patent for the LZ78 directly, 'I am pleased with the fact that the LZW has become popular and the LZW has made us famous. I enjoyed further research with this. '

In fact, the papers published by Mr. Jiv are famous for the 1977 and 1978 treatises, but after that, Mr. Jiv published about 100 peer-reviewed treatises. He also gave lectures at Technion-Israel Institute of Technology until 1985, influencing many students and paving the way for researchers.

At the time of writing, 89-year-old Jiv was reportedly suffering from glaucoma, which weakened his eyesight, and the last paper published in January 2021 was published. The treatise is about a study that started in 2019 and describes a technique that allows subjects' DNA to be compared with past samples to see if mutations are occurring. This technology makes it easy for doctors to understand a patient's genetic disorder and for researchers to compare the DNA of new and existing viruses. It is said that this technology uses the same approach as data compression.

in Software,   Science, Posted by logq_fa