Dissecting the gzip format (2011)
infinitepartitions.com
Dissecting the gzip format (2011)
1–10 of 68 posts
Re: Dissecting the gzip format (2011)
#2Besides 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.
Re: Dissecting the gzip format (2011)
#3(2011)
Formatted version: https://infinitepartitions.com/cgi-bin/showarticle.cgi?artic...
Re: Dissecting the gzip format (2011)
#4[deleted]
Re: Dissecting the gzip format (2011)
#5Besides 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…
The 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.
Re: Dissecting the gzip format (2011)
#6Why 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.
Re: Dissecting the gzip format (2011)
#7Why 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.
bzip2 is substantially slower to compress and decompress, and uses more memory.
It does achieve higher compression ratios on many inputs than gzip, but xz and zstd are even better, and run faster.
Re: Dissecting the gzip format (2011)
#8Why 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.
bzip2 is substantially slower to compress and decompress, and uses more memory. It does achieve higher compression ratios on many inputs than gzip, but xz and zstd are even better, and run faster.
TBF zstd runs most of the gamut, so depending on your settings you can have it run very fast at a somewhat limited level of compression or much lower at a very high compression.
Bzip is pretty completely obsolete though. Especially because of how ungodly slow it is to decompress.
Re: Dissecting the gzip format (2011)
#9Why 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.
Muscle 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.
Re: Dissecting the gzip format (2011)
#10Earlier quoted context omitted.
bzip2 is substantially slower to compress and decompress, and uses more memory. It does achieve higher compression ratios on many inputs than gzip, but xz and zstd are even better, and run faster.
TBF zstd runs most of the gamut, so depending on your settings you can have it run very fast at a somewhat limited level of compression or much lower at a very high compression. Bzip is pretty completely obsolete though. Especially because of how ungodly slow it is to decompress.
> TBF zstd runs most of the gamut
Yep. But bzip2 is much less flexible; reducing its block size from the default of 900 kB just reduces its compression ratio. It doesn't make it substantially faster; the algorithm it uses is always slow (both to compress and decompress). There's no reason to use it when zstd is available.