Ever upload a selfie to Facebook? Email your latest PowerPoint presentation to your boss? If so, chances are that the information was large and cumbersome and that your computer compressed this information to transmit it across the World Wide Web. And, if so, it is also likely that behind your computer or phone’s compression system was the Lempel-Ziv algorithm.
The Lempel-Ziv algorithm was invented by Jacob Ziv and Abraham Lempel in the 1970s. On November 9, Israeli-born Ziv, now 85, will receive the EMET Prize for his work in the fields of data compression, information theory and statistical communication theory. The EMET Prize ceremony will take place at the Jerusalem Theater by invitation only.
The EMET Prize is considered the Israeli Nobel Prize, and, in fact, most Israeli Nobel winners first received the EMET Prize.
Other EMET Prize winners this year include Oded Kotler and Yevgeny Arye (Culture and Art), Zelig Eshhar and Alexander Levitzki (Life Sciences), Assaf Razin (Social Sciences), and David Heyd (Humanities).
Ziv is the first-ever computer engineer awardee in the exact sciences category – largely for his work on the Lempel-Ziv algorithm.
The Lempel-Ziv algorithm is the first widely used universal data compression method for computers. With the algorithm, a large English text file can typically be compressed to about half of its original size. It can also be used to compress GIF, TIFF and PDF files.
The system works with what Ziv calls pointers.
“It’s like a TV guide,” Ziv says. “Every time a program repeats during the week, the full description of that program is not reprinted. The guide just notes, ‘See page this or that.’ This is a pointer and it saves space. It’s quite simple, but no one else thought of it.”
While there are many statistical compression codes that were invented before and after Lempel-Ziv, they are all based on the assumption that the information being transmitted is statistical and that the transmitters (computer or man) know what the statistics are.
“I was bothered by this a priori assumption for a long time,” Ziv tells The Jerusalem Post
Ziv first became interested in information theory as a young man working for the scientific department of the Defense Ministry (today Rafael Advanced Defense Systems Ltd).
“We had just come off the War of Independence, and it was clear we needed to develop more advanced systems, but no one knew how,” recalls Ziv. “On one hand, we sort of taught ourselves. Like in a yeshiva, we would sit around together and study how from books.”
At the same time, the ministry decided to send a group of its top employees to get PhDs in a relevant subject of their choice. Ziv was selected and applied to get a doctorate in information technology from the Massachusetts Institute of Technology.
At MIT, Ziv studied under Claude Shannon, considered the father of information theory and the founder of one of the classical communication theories. Ziv completed his degree in two years and returned to work at the Defense Ministry, which by this time had become Israel’s R&D Military.
Soon he and a group of ministry researchers left their posts to teach and do research at the Technion-Israel Institute of Technology, helping it gain its standing as one of the top international technology schools in the world and, Ziv believes, setting the stage for transforming Israeli students into the Start-up Nation.
The groundwork for the Lempel-Ziv algorithm was laid on a drive to reserve duty.
“Professor Lempel and I were both at the Technion and we got called for miluim [reserve duty],” recalls Ziv. “We shared a car and during the ride we discussed the challenge. Even after we got back and each went on sabbatical, we continued to research and test together.”
When the team figured out the algorithm, they published two public scientific papers on their theory and stopped there. At the time, they did not think too much about the application of their work.
When the Lempel-Ziv algorithm was developed, the practical impact was not felt at first. In fact, Ziv says people were not that interested, because there was little real need for data compression for communication. In the 1970s, it was mostly used for magnetic decoding or reducing the transmission rate for noisy (error-filled) channels.
“All we had at the time were small PCs,” says Ziv.
Then the Internet hit the marketplace and there was a huge need for it.
“The Internet is the reason why this algorithm is now integrated into all classical communication algorithms that have been used for transmitting data error free, as well as in JPEG and other algorithms,” Ziv explains.
Today, personal computers and even phones have huge memory capacity. But only a couple of decades ago, memory was expensive, so you had to compress if you wanted to store a lot of data. When traffic spiked on the Internet, there was no other choice but to compress it, too. Today, there is so much data being generated that data compression is always needed and will always be needed.
Lempel-Ziv is still the most common data compression algorithm that people are using for error-free data compression. It can also be used for predictive analytics and machine learning.
The first company to patent software based on the Lempel-Ziv algorithm was the Sperry Rand Corporation. Ultimately, Microsoft and IBM also grabbed hold of its value.
“The nice thing about the algorithm is that it is so simple that it is very easy for somebody to get his own version,” says Ziv.
Researchers in other fields are regularly finding new ways to apply the algorithm. Geneticists are examining if Lempel-Ziv can be leveraged to transmit the human genetic code faster and cheaper to research genetic disorders and treat patients better.
The Lempel-Ziv algorithm is built into the first Sony-Philips DVDs. It can be used to classify music, such as if you listen to a recorded piece of music and want to find out whether it is Mozart or Beethoven.
A group of students at the Technion are currently considering whether Lempel-Ziv could be used to identify people by the way they type on their personal keyboard, like a fingerprint. If so, this could be a breakthrough in communications security.
Ziv, who won 1993’s Israel Prize for exact sciences, says he is proud of receiving the EMET Prize and thinks it provides encouragement for Technion students to work harder and aim higher. However, he is modest about his accomplishments.
He tells the Post
that research is part smarts and part luck.
“Research is not like solving a mathematical problem, such as finding the square root of something,” says Ziv. “With research you are dealing with the unknown. Sometimes you don’t know what it is you are looking for. Or, sometimes, you find something that was not even what you were looking for, but it is really interesting.”
He says that young scientists should not put people like himself on pedestals. Before his successes, there were a lot of failures – that is just part of research.
“You have to try many times and fail and fail and fail,” says Ziv.
He says he thinks the reason the Technion is so renowned and Israel is the Start-up Nation is not because Jews are inherently smarter, but because of the emphasis the country and the Jewish nation historically put on learning over everything else.
“You get an edge when you understand the importance of learning for the sake of learning, regardless of whether there is application,” he says.This article was written in cooperation with the EMET Prize.