Jacob Ziv Honored
Joanna Goodrich (via Hacker News):
IEEE Life Fellow Jacob Ziv will receive this year’s IEEE Medal of Honor “for fundamental contributions to information theory and data compression technology, and for distinguished research leadership.”
Ziv and Abraham Lempel developed two lossless data compression algorithms: Lempel-Ziv 77 in 1977 and LZ78 the following year. The two procedures enable perfect data reconstruction from compressed data and are more efficient than previous algorithms. They allowed for the development of GIFs, PNG, and ZIP files.
Here are the papers for LZ77 and LZ78.
In the second of the two papers that introduced these algorithms they are analyzed as encoders defined by finite-state machines. A measure analogous to information entropy is developed for individual sequences (as opposed to probabilistic ensembles). This measure gives a bound on the data compression ratio that can be achieved. It is then shown that there exist finite lossless encoders for every sequence that achieve this bound as the length of the sequence grows to infinity. In this sense an algorithm based on this scheme produces asymptotically optimal encodings.
