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

Bzip3: A spiritual successor to BZip2

github.com

Post reply on HN
Print view View original

111–120 of 181 posts

Re: Bzip3: A spiritual successor to BZip2

#111

Post by hcs »

SeptiumMMX wrote: post #63
linsomniac wrote: post #2

Highlight (benchmark of Perl source code): The results follow: xz -T16 -9 -k - 2'056'645'240 bytes (c=12m09s, d=4m40s) bzip2 -9 -k - 3'441'163'911 bytes (c=17m16s, d=9m22s) bzip3 -b 256 - 1'001'957'587 bytes (c=7m10s, d=4m6s? Unclear on source page) bzip3 -b 511 - 546'456'978 bytes (c=7m08s, d=4m6s? Unclear) zstd -T12 -16 - 3'076'143'660 bytes (c=6m32s, d=3m51s) edit: Adding times and compression levels

Given that it's BWT, the difference should be the most prominent on codebases with huge amounts of mostly equivalent files. Most compression algorithms won't help if you get an exact duplicate of some block when it's past the compression window (and will be less efficient if near the end of the window). But here's a practical trick: sort files by extension and then by name before putting them into an archive, and the…

Handy tip for 7-Zip, the `-mqs` command line switch (just `qs` in the Parameters field of the GUI) does this for you. https://7-zip.opensource.jp/chm/cmdline/switches/method.htm#...

Re: Bzip3: A spiritual successor to BZip2

#112

Post by supertrope »

andix wrote: post #88
palaiologos wrote: post #82

Earlier quoted context omitted.

Hi, tool author here! Thank you for your benchmark! As you may be aware, different compression tools fill in different data type niches. In particular, less specialised statistical methods (bzip2, bzip3, PPMd) generally perform poorly on vaguely defined binary data due to unnatural distribution of the underlying data that at least in bzip3's case does not lend well to suffix sorting. Conversely, Lempel-Ziv methods us…

Shouldn't a modern compression tool, targeting a high compression rate, try to switch its compression method on the fly depending on the input data? I have no idea about compression, just a naive thought.

7-Zip can apply a BCJ filter before LZMA to more effectively compress x86 binaries. https://www.7-zip.org/7z.html. Btrfs’ transparent compression feature checks if the first block compressed well; if not it gives up for the rest of the file.

Re: Bzip3: A spiritual successor to BZip2

#113

Post by bawolff »

jltsiren wrote: post #104
bawolff wrote: post #70

Earlier quoted context omitted.

Yeah. BWT and zero knowledge proofs are my goto examples of CS things that seem like pure magic.

Public-key cryptography is magic. Zero-knowledge proofs are a consequence that's difficult to find on your own but easy to understand once you've seen it. I remember seeing someone (probably Avi Wigderson) demonstrating a zero-knowledge proof for graph coloring on an overhead projector when I was starting my second year studying CS. He had a slide with a graph, multiple slides with different permutations of the same…

Magical things are usually built up from the trivial examples.

Graph colouring is usually used as a teaching example for zkp, because of how easy it is to understand. Its still amazing how you can go from that example to "Here is a file that anyone can verify (non-interactively) which shows i have a passport and that passport is not from a country sanctioned by the usa but otherwise does not reveal anything about me" or "I will not reveal my ip or any other identifying/unique info but i will prove i have not been previously blocked from this website including during the other times i anonoymously accessed this website"

Re: Bzip3: A spiritual successor to BZip2

#114

Post by adastra22 »

Brian_K_White wrote: post #99
adastra22 wrote: post #95

Earlier quoted context omitted.

What does that have to do with zstd?

It directly addresses "How much does that matter? All currently supported releases at least."

No it doesn’t? You can get zstd on macOS just fine. We’re talking about zstd, not bash, and supported releases not what ships with the distribution.

Re: Bzip3: A spiritual successor to BZip2

#115

Post by gopalv »

altairprime wrote: post #51
unnah wrote: post #37

Earlier quoted context omitted.

The Burroughs-Wheeler transform has been described as a unique algorithm idea in that there are no non-trivial variations or related algorithms, unlike more conventional compression algorithms, which can be tweaked and improved in so many ways. There is no general compression theory in which BWT could be described as a special case. It looks to me that the above still holds: Bzip2 and Bzip3 are simply combining more…

Can BWT be combined with zstd, which uses asymmetric numeral systems?

> BWT be combined with zstd

BWT can be combined with anything which does RLE and get a benefit.

What does it does is give RLE more to work with.

Re: Bzip3: A spiritual successor to BZip2

#116

Post by abetusk »

mmastrac wrote: post #4

I've studied the Burrows-Wheeler Transform, I understand the transformation, I've re-implemented it countless times for kicks, I see how it improves compressability, but for the life of me the intuition of _why_ it works has never really clicked. It's a fantastic bit of algorithmic magic that will always impress me to see it.

Isn't it basically run length encoding but on patterns? Sorting lexicographical on all rotations means blocks of patterns get grouped together, which means you can do compression more easily, right?

Re: Bzip3: A spiritual successor to BZip2

#117

Post by Zamiel_Snawley »

ggm wrote: post #106

Small request: write a header or tail block which records the compression efficiency. Bzip2 doesn't. Gzip does. Knowing the uncompressed size can be vital. Yes, there is a risk of lying and making zip bombs.

Shouldn’t knowing how big it’s supposed to be make it easier to stop a zip bomb? Just stop decompressing once you hit the size from the header.

Re: Bzip3: A spiritual successor to BZip2

#118

Post by twotwotwo »

A random thought that Might Work, Who Knows(tm): first compress long-ish repetitions in the input and store the copies separately from the literals (like zstd). Then run just blocks of literals through the BWT before entropy coding.

The idea is that the BWT can help take advantage of however much context remains after the copies are snipped out, whether that's one byte or a few, and shrinking the input with the LZ-ish step may make it faster. It might be strictly worse than using PPM or basic context modeling like Brotli's; either of those can be "aware" of the preceding bytes even when they come from copies rather than literals.

It's implied in "successor to bzip2" and a lot of the comments, but it's worth highlighting that high-compression algorithms, especially those that are also slow to decompress, are a pretty specialized niche now. Using zstd or brotli at low to medium settings sometimes speeds things up by reducing network or storage transfers more than their CPU use slows you down. (Especially when your storage transfers are network transfers.) Even when compressing isn't a net speedup, you pay fairly little time for the saved space. Even lowish levels of zstd and brotli often eke out decent compression ratios for big inputs since, with modern quantities of RAM, their MBs-long history windows let them take advantage of long-range matches.

Re: Bzip3: A spiritual successor to BZip2

#119

Post by jwr »

I still remember going crazy about bzip (the first one) and re-compressing all my data with it.

And then I remember discovering, several years later, that bzip (the first one) is an obsolete format that is now difficult to even decompress.

I learned my lesson and now use horribly sub-optimal formats that I'm sure will stick around for a long time, if not forever.

Re: Bzip3: A spiritual successor to BZip2

#120

Post by jltsiren »

bawolff wrote: post #113
jltsiren wrote: post #104

Earlier quoted context omitted.

Public-key cryptography is magic. Zero-knowledge proofs are a consequence that's difficult to find on your own but easy to understand once you've seen it. I remember seeing someone (probably Avi Wigderson) demonstrating a zero-knowledge proof for graph coloring on an overhead projector when I was starting my second year studying CS. He had a slide with a graph, multiple slides with different permutations of the same…

Magical things are usually built up from the trivial examples. Graph colouring is usually used as a teaching example for zkp, because of how easy it is to understand. Its still amazing how you can go from that example to "Here is a file that anyone can verify (non-interactively) which shows i have a passport and that passport is not from a country sanctioned by the usa but otherwise does not reveal anything about me"…

Things that look magical often stop being magical when you have the right perspective and the right abstractions. The step from a toy example to proving any verifiable statement is just NP-completeness. Which is simple enough that undergraduates are often expected to understand it.

Interactive zero-knowledge proofs are also technically non-interactive. They are defined in terms of the verifier evaluating a transcript of the protocol. If the verifier accepts some causal assumptions about the provenance of the transcript, they will accept the proof. If they disagree with the assumptions, the proof is indistinguishable from random noise they could generate themself. An interactive commitment – challenge – response protocol is one possible causal assumption. A source of randomness could replace the challenges, making the protocol non-interactive. Or there could be a pre-committed secret, making a single-round protocol effectively non-interactive.

These are things a sufficiently interested CS undergraduate can prove and understand. Public-key cryptography, on the other hand, remains magical. There are many things people assume to be true. Which need to be true for public-key cryptography to function. Empirically these things seem to be true, but nobody has been able to prove them. And I don't think anyone really understands them.

Post reply on HN