Re:IEEE Medal of Honor Goes to Data Compression Pioneer Jaco...
by smoyer on Sunday January 17, 2021 @07:58PM
(#25817018)
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.
[ Parent
| on HN ]
Re:IEEE Medal of Honor Goes to Data Compression Pioneer Jaco...
by beagle3 on Monday January 18, 2021 @04:07AM
(#25819760)
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.
Re:IEEE Medal of Honor Goes to Data Compression Pioneer Jaco...
by user-the-name on Monday January 18, 2021 @06:02AM
(#25820476)
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.
Re:IEEE Medal of Honor Goes to Data Compression Pioneer Jaco...
by jimis on Monday January 18, 2021 @05:16AM
(#25820216)
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.
Re:IEEE Medal of Honor Goes to Data Compression Pioneer Jaco...
by ip26 on Sunday January 17, 2021 @10:02PM
(#25817660)
Many good inventions are like that.
Re:IEEE Medal of Honor Goes to Data Compression Pioneer Jaco...
by saltedonion on Sunday January 17, 2021 @11:16PM
(#25818058)
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.