5 ms·

I love the explanation of how LZ77 works; compression algorithms often seem like they must use some sort of arcane magic, so it's great to lift the veil a bit.

I love the explanation of how LZ77 works; compression algorithms often seem like they must use some sort of arcane magic, so it's great to lift the veil a bit. I wonder: how many folks have Little Bunny Foo Foo stuck in their heads after reading this?

ck2 12y ago
Now go read about Markov chains which will blow your mind. Back in the late 80s I read an interview with Phil Katz who mentioned them to possibly improve PKZIP so I looked them up in the library. That's when it dawned on me there were people far, far more intelligent and clever in this world than I would ever be.
- mnw21cam 12y ago
  Now go and read about the Burrows-Wheeler block-sort algorithm, which is used by the bzip2 compression program. This can only be a product of a sick and twisted (but quite brilliant) mind.
  - mbrock 12y ago
    Wow, I remember skipping class to sit in the library and implement the Burrows-Wheeler transform. Such a wonderfully clever algorithm, particularly the inverse step!
    - draugadrotten 12y ago
      ...and while we talk about blown minds and algorithms, be sure to watch the beautofully executed Quick-sort with Hungarian (Küküllőmenti legényes) https://www.youtube.com/user/AlgoRythmics/videos https://www.youtube.com/user/AlgoRythmics/videos
userbinator 12y ago
The "arcane magic" impression likely comes from the heavy use of information theory concepts and maths that are encountered in the traditional literature. Probably necessary to analyse in detail, but quite daunting for the beginner. I find LZ to be particularly intuitive since it embodies the natural notion of "abbreviation" by referring to something we've seen before, and writing compressors/decompressors for the algorithm is relatively easy (especially decompressors.) On the other hand Huffman is somewhat less easy to grasp intuitively, but some aspects of its principle of reducing bits/symbol based on their frequency shows up in natural languages: the more common a word is, the shorter it tends to be. It's also a bit more difficult to implement.
- eru 12y ago
  And as words become more common (over time or in specific parts of the population), they often become shorter, too. Eg see the evolution from phone / mobile phone, to landline / phone.
Dylan16807 12y ago
The arcane part is what happens after the repetitions have been found and replaced. At that point you have the entropy encoding stage where more common tokens get shorter encodings and more rare tokens get longer encodings. The basic idea isn't too complex, but then optimizing it adds extra layers to efficiently store which tokens are common and which are rare. This results in something quite arcane indeed.
talideon 12y ago
LZ77 is pretty trivial as compression algorithms go. Go take a look at this video for a explanation accessible to non-developers: https://www.youtube.com/watch?v=goOa3DGezUA https://www.youtube.com/watch?v=goOa3DGezUA

ck2 12y ago

Now go read about Markov chains which will blow your mind. Back in the late 80s I read an interview with Phil Katz who mentioned them to possibly improve PKZIP so I looked them up in the library. That's when it dawned on me there were people far, far more intelligent and clever in this world than I would ever be.

mnw21cam 12y ago
Now go and read about the Burrows-Wheeler block-sort algorithm, which is used by the bzip2 compression program. This can only be a product of a sick and twisted (but quite brilliant) mind.
- mbrock 12y ago
  Wow, I remember skipping class to sit in the library and implement the Burrows-Wheeler transform. Such a wonderfully clever algorithm, particularly the inverse step!
  - draugadrotten 12y ago
    ...and while we talk about blown minds and algorithms, be sure to watch the beautofully executed Quick-sort with Hungarian (Küküllőmenti legényes) https://www.youtube.com/user/AlgoRythmics/videos https://www.youtube.com/user/AlgoRythmics/videos

userbinator 12y ago

The "arcane magic" impression likely comes from the heavy use of information theory concepts and maths that are encountered in the traditional literature. Probably necessary to analyse in detail, but quite daunting for the beginner. I find LZ to be particularly intuitive since it embodies the natural notion of "abbreviation" by referring to something we've seen before, and writing compressors/decompressors for the algorithm is relatively easy (especially decompressors.) On the other hand Huffman is somewhat less easy to grasp intuitively, but some aspects of its principle of reducing bits/symbol based on their frequency shows up in natural languages: the more common a word is, the shorter it tends to be. It's also a bit more difficult to implement.

eru 12y ago
And as words become more common (over time or in specific parts of the population), they often become shorter, too. Eg see the evolution from phone / mobile phone, to landline / phone.

Dylan16807 12y ago

The arcane part is what happens after the repetitions have been found and replaced. At that point you have the entropy encoding stage where more common tokens get shorter encodings and more rare tokens get longer encodings. The basic idea isn't too complex, but then optimizing it adds extra layers to efficiently store which tokens are common and which are rare. This results in something quite arcane indeed.

talideon 12y ago

LZ77 is pretty trivial as compression algorithms go. Go take a look at this video for a explanation accessible to non-developers: https://www.youtube.com/watch?v=goOa3DGezUA https://www.youtube.com/watch?v=goOa3DGezUA