3 ms·
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,
by 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 agoI 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 agoIt'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.