Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Dissecting the gzip format (2011)

infinitepartitions.com

Post reply on HN
Print view View original

41–50 of 68 posts

Re: Dissecting the gzip format (2011)

#41

Post by Suppafly »

noirscape wrote: post #32
Filligree wrote: post #20

One 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-…

Is that by any chance related to how the TAR format was developed? Considering the big thing with TAR is that you can also concatenate it together (the format is quite literally just file header + content ad infinitum; it was designed for tape storage - it's also the best concatenation format if you need to send an absolute truckloads of files to a different computer/drive since the tar utility doesn't need to index…

I assume tar came first just for grouping things together and then compression came out and they were combined together. That's why the unix tarballs were always tar.gz prior to gz having the ability to do both things.

Re: Dissecting the gzip format (2011)

#42

Post by Arkanosis »

mbreese wrote: post #26
Filligree wrote: post #20

One 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-…

In bioinformatics we use a modified gzip format called bgzip that exploits this fact heavily. The entire file is made of concatenated gzip chunks. Each chunk then contains the size of the chunk (stored in the gzip header). This lets you do random access inside the compressed blocks more efficiently. Sadly, the authors hard coded the expected headers so it’s not fully gzip compatible (you can’t add your own arbitrary…

On top of enabling indexing, it reduces the amount of data lost in the event of data corruption — something you get for free with block-based compression algorithms like BWT-based bzip2 but is most of the time missing from dictionary-based algorithms like LZ-based gzip.

I don't think many people use that last property or are even aware of it, which is a shame. I wrote a tool (bamrescue) to easily recover data from uncorrupted blocks of corrupted BAM files while dropping the corrupted blocks and it works great, but I'd be surprised if such tools were frequently used.

Re: Dissecting the gzip format (2011)

#43

Post by andrewf »

jcranmer wrote: post #29
hk1337 wrote: post #6

Why 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.

Using gzip as a baseline, bzip2 provides only modest benefits: about a 25% improvement in compression ratio, with somewhat more expensive compression times (2-3×) and horrifically slow decompression times (>5×). xz offers a more compelling compression ratio (about 40-50% better), at the cost of extremely expensive compression time (like 20×), but comparable decompression time to gzip. zstd, the newest kid on the box,…

Adding to this: I like looking at graphs like https://calendar.perfplanet.com/images/2021/leon/image1.png . In this particular example, the "lzma" (ie xz) line crosses the zstd line, meaning that xz will be compress faster for some target ratios, zstd for others. Meanwhile zlib is completely dominated by zstd.

Different machines and different content will change the results, as will the optimization work that's gone into these libraries since someone made that chart in 2021.

Re: Dissecting the gzip format (2011)

#44

Post by blibble »

Filligree wrote: post #20

One 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-…

I've used this trick to build docker images from a collection of layers on the fly without de/recompression

Re: Dissecting the gzip format (2011)

#45

Post by mbreese »

Arkanosis wrote: post #42
mbreese wrote: post #26

Earlier quoted context omitted.

In bioinformatics we use a modified gzip format called bgzip that exploits this fact heavily. The entire file is made of concatenated gzip chunks. Each chunk then contains the size of the chunk (stored in the gzip header). This lets you do random access inside the compressed blocks more efficiently. Sadly, the authors hard coded the expected headers so it’s not fully gzip compatible (you can’t add your own arbitrary…

On top of enabling indexing, it reduces the amount of data lost in the event of data corruption — something you get for free with block-based compression algorithms like BWT-based bzip2 but is most of the time missing from dictionary-based algorithms like LZ-based gzip. I don't think many people use that last property or are even aware of it, which is a shame. I wrote a tool (bamrescue) to easily recover data from un…

Why do you think I wanted to add hashes and encryption at the block level? :)

I’ve had to do similar things in the past and it’s a great side-feature of the format. It’s a horrible feeling when you find a corrupted FASTQ file that was compressed with normal gzip. At least with bgzip corrupted files, you can find and start recovery from the next block.

Re: Dissecting the gzip format (2011)

#46

Post by yyyk »

userbinator wrote: post #2

Besides 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…

>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.

Re: Dissecting the gzip format (2011)

#47

Post by sgarland »

hk1337 wrote: post #6

Why 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.

Parallel compression (pigz [0]) and decompression (rapidgzip [1]), for one. When you're dealing with multi-TB files, this is a big deal.

[0]: https://github.com/madler/pigz

[1]: https://github.com/mxmlnkn/rapidgzip

Re: Dissecting the gzip format (2011)

#49

Post by Too »

jcranmer wrote: post #29
hk1337 wrote: post #6

Why 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.

Using gzip as a baseline, bzip2 provides only modest benefits: about a 25% improvement in compression ratio, with somewhat more expensive compression times (2-3×) and horrifically slow decompression times (>5×). xz offers a more compelling compression ratio (about 40-50% better), at the cost of extremely expensive compression time (like 20×), but comparable decompression time to gzip. zstd, the newest kid on the box,…

> if you care about compression time, gzip is the winner

Not at all. Lots of benchmarks show zstd being almost one order of magnitude faster, before even touching the tuning.

Re: Dissecting the gzip format (2011)

#50

Post by lxgr »

umvi wrote: post #36
jcranmer wrote: post #29

Earlier quoted context omitted.

Using gzip as a baseline, bzip2 provides only modest benefits: about a 25% improvement in compression ratio, with somewhat more expensive compression times (2-3×) and horrifically slow decompression times (>5×). xz offers a more compelling compression ratio (about 40-50% better), at the cost of extremely expensive compression time (like 20×), but comparable decompression time to gzip. zstd, the newest kid on the box,…

> at the same compression time/decompression time as gzip In my experience zstd is considerably faster than gzip for compression and decompression, especially considering zstd can utilize all cores. gzip is inferior to zstd in practically every way, no contest.

Practically, compatibility matters too, and it's hard to beat gzip there.
Post reply on HN