IEEE Medal of Honor Goes to Data Compression Pioneer Jacob Ziv
spectrum.ieee.org
spectrum.ieee.org
This is extremely well deserved.
Rather, it was what Lempel and Ziv proved about both of their simple algorithms -- The one published in 1977, usually referred to as LZ77 which is the basis of all <length,distance> variants, and the one published in 1978, usually referred to as LZ78 which is the basis of LZW, and other <word,char> variants.
They proved that for a very large class of sources (those described by markov models, context trees, among many others), these algorithms asymptotically give the best possible compression. In fact, some applications (also proved correct by Ziv) use the compressed datastream statistics to estimate source entropy, because it's much easier to implement than any direct measurement.
Both Ziv and Lempel did a lot of other things; However, Lempel did more in the area of switching systems and his other contributions are numerous and interesting, but were less profound in any specific field -- Whereas Ziv's contribution to Information Theory through the last 60 years or so has been much more profound.
The algorithm is easy, but the analysis of its effectiveness is not at all easy.
then you have monsters like this
Shannon's original paper, "A mathematical theory of communication" is very readable (especially discrete sources and channels; you need some calculus for the continuous sources and channel stuff), and yet touches on many things and has many insights. At least as late as 2000, one very-well-published prof at the uni I was attending told me that whenever he wants to break out to a new direction, he rereads it 5-10 times and realizes another thing that Shannon considered trivial and that was yet unexplored.
Also, there's basically no repeated sequences in large image data. JPEG, H264 and all their friends are all about compressible approximations that are still close enough, and which rarely if ever have repeated data.
LZ78 is incredibly simple, elegant AND easy to get your your head around. I had implemented it once in 2 lines of Python. some 25 years ago. If I can shake the rust maybe I'll be able to rederive it.
Most of modern lossless compression is instead based on the LZ77-LZSS-... linage, which has a massive number of different improvements and variations.
I had implemented it once in 2 lines of Python. some 25 years ago. If I can shake the rust maybe I'll be able to rederive it.
Back when I attended faculty, I had a project assigned to me titled "Lempel-Ziv compression of binary strings" or something like that. It was one of the most fun projects I worked on.
.Z, .zip, .7z, .gz, .xz, .bz2. Of course, many use LZ77 or LZMA, LZ stands for Lempel–Ziv, but only the Z remained in the format.
(To be even more pedantic, all modern algorithms are descendants of LZSS, which was one of the first improvements on LZ77.)
Out of the ones you listed, only .Z and .bz2 are not LZ77-LZSS descendants.
.Z is an implementation of LZW, which is a descendant of LZ78, which is a significantly different (but still related) algorithm to LZ77. It never really caught on beyond a few implementations of LZW, though.
.bz2 is the only one completely unrelated to Ziv's work. It uses the Burrows-Wheeler transform, instead.
.Z was used for compress(1), probably because pack(1) used .z, but where did that come from?
My best theory is that it's from Steve Zucker who wrote pack(1) at RAND. There were other versions of pack(1) too, but if his was the first, it seems possible that he choose the z extension for Zucker.
Does anyone have more info or other theories?
EDIT: wikipedia says it did but changed to use Huffman encoding due to patents? But those patents have expired.