Hacker News new | ask | show | jobs
by StillBored 1680 days ago
Was going to say, this but tiny correction, its the LZ variant that does this, as will most of them. Deflate is just two pass compression of LZSS followed by Huffman. The LZ variant will pick out repeat patterns, while the second will compress the byte representation of the resulting stream if a particular set of values is over represented. AKA its all variations of X, Y, Z in different orders those might get assigned 2 bit values rather than the 8 they normally might take up.

(so this a bit of a rant I have about people calling deflate a compression algorithm, its an algorithm composed of two other fundamental ones).
2 comments
Jasper_ 1680 days ago
What a weird take. Have you written a deflate/inflate implementation? Deflate really isn't just LZSS (I assume you mean something like Haruhiko Okumura's LZSS?), followed by Huffman, it's a very intertwined and sophisticated combination of LZ77 and Huffman. How the two work together is integral to why Deflate works as well as it does.

The optimal parse here isn't always to pick the greediest match from the LZ77 perspective and then "run it through Huffman", you have to know the Huffman cost model when picking your LZ77 matches.

link
StillBored 1680 days ago
I wrote a zip decompressor many years ago, the compression side wasn't really much of a target, because the focus was on compressing with a more speed focused algorithm. At the time it was a pretty distinct portion of my decompression pass. I didn't know they were picking matches based on the compressed size vs just longest match, but I guess it makes sense, but I don't see why that "intertwines" it anymore than any other adjustment one makes to how one finds matches (which is AFAIK generally the largest change in all the LZ variations).

edit: Just as a note, actually doing it as two distinct passes rather than at the same time would be silly since its going to significantly slow it down. So just because its doing the entire thing as a single "pass" doesn't count IMHO.

link
klodolph 1680 days ago
I’ve written a deflate decompressor and I’m not sure what correction you are trying to make. It seems like you’re replying to this comment to show off some details you know about deflate.
link