8 ms·
Dissecting the gzip format (2011)
- userbinator 2y agoBesides a persistent off-by-one error, and the use of actual trees instead of table lookup for canonical Huffman, this is a pretty good summary of the LZ+Huffman process in general; and in the 80s through the mid 90s, this combination was widely used for data compression, before the much more resource-intensive adaptive arithmetic schemes started becoming popular. It's worth noting that the specifics of DEFLATE were designed by Phil Katz, of PKZIP fame. Meanwhile, a competing format, the Japanese LZH, was chosen by several large BIOS companies for compressing logos and runtime code. Note that real-world GZIP decoders (such as the GNU GZIP program) skip this step and opt to create a much more efficient lookup table structure. However, representing the Huffman tree literally as shown in listing 10 makes the subsequent decoding code much easier to understand. Is it? I found the classic tree-based approach to become much clearer and simpler when expressed as a table lookup --- along with the realisation that the canonical Huffman codes are nothing more than binary numbers.
- lifthrasiir 2y agoThe lookup table here would be indexed by a fixed number of lookahead bits, so it for example would duplicate shorter codes and put longer codes into side tables. So a tree structure, either represented as an array or a pointer-chasing structure would be much simpler.
- 082349872349872 2y agoI'd agree with TFA that canonical Huffman, although interesting, would be yet another thing to explain, and better left out of scope, but it does raise a question: In what other areas (there must be many) do we use trees in principle but sequences in practice? (eg code: we think of it as a tree, yet we store source as a string and run executables which —at least when statically linked— are also stored as strings)
- mxmlnkn 2y ago> In what other areas (there must be many) do we use trees in principle but sequences in practice? Heapsort comes to mind first.
- commandlinefan 2y agoAuthor here! I actually did a follow-up where I looked at the table-based decoding: https://commandlinefanatic.com/cgi-bin/showarticle.cgi?article=art007 https://commandlinefanatic.com/cgi-bin/showarticle.cgi?artic...
- yyyk 2y ago>before the much more resource-intensive adaptive arithmetic schemes started becoming popular The biggest problem was software-patent stuff nobody wanted to risk before they expired.
- jmillikin 2y ago(2011) Formatted version: https://infinitepartitions.com/cgi-bin/showarticle.cgi?article=art001 https://infinitepartitions.com/cgi-bin/showarticle.cgi?artic...
- PROMISE_237 2y ago[dead]
- deleted 2y ago[deleted]
- hk1337 2y agoWhy do people use gzip more often than bzip? There must be some benefit but I don’t really see it, you can split and join two bzipped files (presumably CSV so you can see the extra rows). Bzip seems to compress better than gzip too.
- zie 2y agoMuscle memory. We've been doing gzip for decades and we are too lazy to remember the zstd commands to tar, assuming the installed version of tar has been updated.
- gloflo 2y ago... --auto-compress ... foo.tar.zstd
- PROMISE_237 2y ago[dead]
- zie 2y agoThat's cool! Is that a GNU tar only thing? Based on it being a longopt, I'm guessing a GNU tar only thing. That's the problem with these things, it takes a while to get pushed to all the installed copies of tar running around. Perhaps it's time to check: * MacOS Sonoma(14.6) has tar --auto-compress and --zstd * OpenBSD tar does not appear to have it: https://man.openbsd.org/tar * FreeBSD does: https://man.freebsd.org/cgi/man.cgi?query=tar Not quite fully baked yet.
- qhwudbebd 2y agoBoth libarchive ("bsdtar") and GNU tar have -a, which I guess are the only two upstream tar implementations that are still relevant? You're right, it can take a while for these things to propagate downstream though.
- 2y ago
- 082349872349872 2y agoHas anyone taken the coding as compression (when you create repeated behaviour, stuff it in the dictionary via creating a function; switching frameworks is changing initial dicts; etc.) metaphor seriously?
- eapriv 2y agoYes. https://caseymuratori.com/blog_0015 https://caseymuratori.com/blog_0015
- PROMISE_237 2y ago[dead]
- commandlinefan 2y agoSounds like LZW compression to me - is what you're thinking of different than that?
- 082349872349872 2y agoDifferent in terms of applying the same principle to produce "semantically compressed" code — instead of having each new dictionary entry be a reference to an older one along with the new symbol, each new function will refer to older ones along with some new literal data. (If that still doesn't make sense, see the sibling comment to yours.)
- PROMISE_237 2y ago[dead]
- PROMISE_237 2y ago[dead]
- PROMISE_237 2y ago[dead]
- Filligree 2y agoOne of my favorite gzip party tricks is that (ungzip (cat (gzip a) (gzip b))) == (cat a b). That is to say, the concatenation of two gzip streams is still a valid gzip file. This hasn't ever been practically useful, but it means you can trivially create a 19-layer gzip file containing more prayer strips than there are atoms in the universe, providing a theological superweapon. All you need to do is write it to a USB-stick, then drop the USB-stick in a river, and you will instantly cause a heavenly crisis of hyperinflation.
- Joker_vD 2y ago> This hasn't ever been practically useful, I used it a couple times to merge chunks of gzipped CSV together, you know, like "cat 2024-Jan.csv.gz 2024-Feb.csv.gz 2024-Mar.csv.gz > 2024-Q1.csv.gz". Of course, it only works when there is no column headers.
- kajaktum 2y agoI think ZSTD is also like this.
- wwader 2y agoI think the alpine package format do use this in combination with tar being similar https://wiki.alpinelinux.org/wiki/Apk_spec https://wiki.alpinelinux.org/wiki/Apk_spec
- hansvm 2y agoIt's kind of nice whenever you find yourself in an environment where, for whatever reason, you need to split a payload before sending it. You just `ungzip cat *` the gzipped files you've collected on the other end.
- Hakkin 2y agoThis is true for a few different compression formats, it works for bzip2 too. I've processed a few TBs of text via `curl | tar -xOf - | bzip2 -dc | grep` for tar files with lots of individually compressed bz2 files inside.
- mbreese 2y ago
- Laiho 2y agoIf you prefer reading Python, I implemented the decompressor not too long ago: https://github.com/LaihoE/tiralabra https://github.com/LaihoE/tiralabra
- kuharich 2y agoPast comments: https://news.ycombinator.com/item?id=6920822 https://news.ycombinator.com/item?id=6920822