3 ms·
I implemented LZ77 when I was at university as I was trying to load gifs for an image processing project. I was absolutely blown away by the simplicity and eleg
by iamflimflam1 5y ago
I implemented LZ77 when I was at university as I was trying to load gifs for an image processing project. I was absolutely blown away by the simplicity and elegance algorithm. Need to have a look at LZ4.
- dunham 5y agoI believe GIFs use LZW which is based on LZ78 - the one that builds a dictionary as it goes. (It's been decades since I looked at this one.) LZ77 emits verbatim text and instructions to go back x and copy y characters. A lot of compressors are based on this, including PNG, gzip, lz4, snappy. I think this is partially due to earlier patent issues with LZ78. (LZ4 or Snappy would be a good intro, gzip has extra stuff like huffman encoding tacked on.) You might also be interested in the Burrows-Wheeler transform, which bzip2 is based on. It's completely different and kinda magical. The original paper is here: https://www.hpl.hp.com/techreports/Compaq-DEC/SRC-RR-124.pdf