4 ms·

As the article points out, this guy is the Z in LZ- which also forms the compression portion of the Deflate algorithm (zip/gzip). A huge portion of the lossless

As the article points out, this guy is the Z in LZ- which also forms the compression portion of the Deflate algorithm (zip/gzip). A huge portion of the lossless compression algorithms of today are generationally based on Ziv's work. This is extremely well deserved.

smoyer 6y ago
The first compression algorithm I implemented (on and IBM PC/AT in the mid '80s) was LZW. It's my favorite type of algorithm - elegant but hard to get your head wrapped around. Once you "get it" it seems so obvious.
- ip26 6y ago
  Many good inventions are like that.
  - saltedonion 6y ago
    Nearly all break through inventions seem obvious in hindsight. I guess putting the pieces together and connecting the dots looking forward is what’s incredibly hard. The search space can still be immense.
- beagle3 6y ago
  LZW is just a (nontrivial and very effective) trick to improve on the early behavior of LZ78; they are both asymptotically optimal. 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.
  - jimis 6y ago
    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. Please do! I would love to see a concise and readable implementation in Python.
  - user-the-name 6y ago
    It's a bit of a shame that the LZ78-LZW linage of algorithms basically died out at that point. Most of modern lossless compression is instead based on the LZ77-LZSS-... linage, which has a massive number of different improvements and variations.
userbinator 6y ago
...and LZ is such a simple algorithm - replacing repeated occurrences of a sequence with a shorter backreference - that I'm surprised it wasn't discovered sooner. Huffman wrote about his algorithm in the early 50s, but LZ only showed up in the late 70s.
- andi999 6y ago
  I think repeated sequences in data only became relevant when there was large image data. I mean, like Shannon was concerned about language transmitted.
  - beagle3 6y ago
    Not at all. Shannon's work is incredibly profound, and deals with distortion of analog signals, channel capacity under different constraints, and many other things. He was very much aware and discussing repeated sequences in the 1952 class in which Huffman constructed his code and proved it is optimal. (According to lore, Shannon said "hey, Fano and I have this Shannon-Fano code, which we know is close but not optimal. Improve on it and you can skip the final") 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.
- beagle3 6y ago
  The important contribution is not in the simple algorithm (which I suspect others have come up with before, and I know others have independently come up with after): 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.

smoyer 6y ago

The first compression algorithm I implemented (on and IBM PC/AT in the mid '80s) was LZW. It's my favorite type of algorithm - elegant but hard to get your head wrapped around. Once you "get it" it seems so obvious.

ip26 6y ago
Many good inventions are like that.
- saltedonion 6y ago
  Nearly all break through inventions seem obvious in hindsight. I guess putting the pieces together and connecting the dots looking forward is what’s incredibly hard. The search space can still be immense.
beagle3 6y ago
LZW is just a (nontrivial and very effective) trick to improve on the early behavior of LZ78; they are both asymptotically optimal. 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.
- jimis 6y ago
  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. Please do! I would love to see a concise and readable implementation in Python.
- user-the-name 6y ago
  It's a bit of a shame that the LZ78-LZW linage of algorithms basically died out at that point. Most of modern lossless compression is instead based on the LZ77-LZSS-... linage, which has a massive number of different improvements and variations.

userbinator 6y ago

...and LZ is such a simple algorithm - replacing repeated occurrences of a sequence with a shorter backreference - that I'm surprised it wasn't discovered sooner. Huffman wrote about his algorithm in the early 50s, but LZ only showed up in the late 70s.

andi999 6y ago
I think repeated sequences in data only became relevant when there was large image data. I mean, like Shannon was concerned about language transmitted.
- beagle3 6y ago
  Not at all. Shannon's work is incredibly profound, and deals with distortion of analog signals, channel capacity under different constraints, and many other things. He was very much aware and discussing repeated sequences in the 1952 class in which Huffman constructed his code and proved it is optimal. (According to lore, Shannon said "hey, Fano and I have this Shannon-Fano code, which we know is close but not optimal. Improve on it and you can skip the final") 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.
beagle3 6y ago
The important contribution is not in the simple algorithm (which I suspect others have come up with before, and I know others have independently come up with after): 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.