3 ms·
> The following year, the two researchers issued a refinement, LZ78. That algorithm became the basis for the Unix compress program used in the early ’80s; WinZi
by 0xcde4c3db 6y ago
> The following year, the two researchers issued a refinement, LZ78. That algorithm became the basis for the Unix compress program used in the early ’80s; WinZip and Gzip, born in the early ’90s; and the GIF and TIFF image formats.
I don't understand the inclusion of WinZip and gzip here. Those are based on DEFLATE, which I thought was deliberately derived from LZ77 and LZSS rather than anything particular to the LZ78/LZW lineage (for patent reasons). Am I confused about something?
- beagle3 6y agoI'm finding conflicting web docs about what algorithms pkzip prior to 2.0 (deflate == gzip) used. There were "shrink" and "implode", they had some run-length encoding, and some entropy coding (shannon fano trees, later replaced by huffman coding in deflate). My vague memory says there was an LZW among them, with PKZIP 0.8 or something, but I'm not sure. What I am sure about, is that the predecessor to PKZIP, "PKARC", most certainly did use LZW; It was compatible with SEA ARC, but much, much faster (like 5x or so). SEA sued Phil Katz, and his response was to drop ARC compatibility and release PKZIP which was faster and better -- though the incumbent "deflate" method did not appear until version 2 a few years later.
- zmodem 6y agoShrink is LZW, Implode is LZ77 + Shannon-Fano/Huffman. See https://www.hanshq.net/zip2.html https://www.hanshq.net/zip2.html
- zmodem 6y agoI think it's the article that's confused, or being a bit careless with the details. Like you say, Deflate is based on LZ77, and I think it's not just for patent reasons but because it's a nice algorithm. More modern algorithms like LZMA is also LZ77 based.