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

151–160 of 181 posts

Re: Bzip3: A spiritual successor to BZip2

#151

Post by eru »

palaiologos wrote: post #83
crazygringo wrote: post #71

Earlier quoted context omitted.

But shouldn't Huffman coding already detect that same predictability and compress it the same? What I don't get isn't the benefits of BWT on its own. It's why BWT should add any additional benefit if you're already doing Huffman.

Hi, tool author here. Huffman coding is a static minimum-redundancy code. What this means is that it finds an optimal assignment of bit sequences to letters in the input alphabet (commonly US-ASCII or extensions). This however means that Huffman coding can not exploit redundancies that stem from the concrete sequence of characters. For example, you could easily predict that an `e` comes after `Th`, but Huffman coding…

You are spot on.

Btw, the Burrows-Wheeler transform is often explained as taking the last column.

I find it easier to understand why it works if you think of BWT as sorting all rotations of your string by from their _second_ character onwards, and then writing down all the first characters.

Re: Bzip3: A spiritual successor to BZip2

#152

Post by lexicality »

palaiologos wrote: post #76
lexicality wrote: post #39

> DO NOT COMPRESS ANY DATA WITH THIS PROGRAM UNLESS YOU ARE PREPARED TO ACCEPT THE POSSIBILITY, HOWEVER SMALL, THAT THE DATA WILL NOT BE RECOVERABLE. I know every open source project (and quite a lot of expensive proprietary ones!) come with a "btw this software might wipe your computer, if it does that's your fault lol" clause in their license but I can't imagine trying to convince anyone else that using this for an…

Hi! Tool author here. Almost every single open source compression tool contains a clause like this. For example, the one in the README that you see has been directly lifted from the bzip2 README. Almost all open source projects come with such a no-warranty scheme. 7-Zip, zstandard, xz-utils, etc; as exemplified by a quote from the license text of the MIT license: > THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY O…

I did acknowledge that.

My point was more if you went into a store to buy some cereal and you had two options: "Cornflakes" and "Cornflakes 2 - they're better!" but you noticed that while both packets had standard legal nonsense on them but Cornflakes 2 had "This cereal almost certainly does not contain broken glass" as well, personally I think human nature would make me go with the packet that didn't bring up broken glass in the first place - even if both of them have the exact same chance of containing it

Re: Bzip3: A spiritual successor to BZip2

#153

Post by dist-epoch »

alkh wrote: post #110
eqvinox wrote: post #105

Earlier quoted context omitted.

Did you confuse gzip and xz? You mention numbers from xz and then suddenly talk about gzip? These two are not related…

Hey, I didn't confuse them but I guess I should have been more specific. I've addressed 2 main points in my text. 1) In my opinion, for the vast majority of cases you don't need to be worried about comparability, as you can easily install better alternatives to gzip for platforms a lot of people use. 2) I think zstd can become a primary replacement for gzip due to its high speed of compression and good compression ra…

zstandard at level 21 with some tweaked parameters (larger dictionaries) will give you xz/lzma compression ratios, while still being faster.

Re: Bzip3: A spiritual successor to BZip2

#154

Post by matthberg »

pxeger1 wrote: post #17

The author is super cool. They are one of very few people to write any substantial programs in Malbolge, a programming language designed to be cryptographically hard to use (or something like that)

The Wikipedia page on Malbolge was quite the horrific read, downright amazing to have a lisp written in it.

Here's the program as talked about on HN:

https://news.ycombinator.com/item?id=38850961

https://github.com/kspalaiologos/malbolge-lisp

The cursed language: https://en.wikipedia.org/wiki/Malbolge

And the variant used by the program: https://esolangs.org/wiki/Malbolge_Unshackled

Re: Bzip3: A spiritual successor to BZip2

#155

Post by arp242 »

ThatGuyRaion wrote: post #130
loeg wrote: post #32

Earlier quoted context omitted.

Just install the binary package from whatever distro you use? Why do you need to build it? But if it matters, FreeBSD has a pretty trivial BSDmake build of it: https://github.com/freebsd/freebsd-src/blob/main/lib/libzstd... https://github.com/freebsd/freebsd-src/blob/main/usr.bin/zst... You could easily do something similar in GNU make or whatever without the dependencies on the FBSD build system. It's basically just…

> Just install the binary package from whatever distro you use? Why do you need to build it? Cuz I'm actually a packaging maintainer for a couple different old operating systems. Regardless I thank you for being thankful even though I feel like you were being backhanded and demeaning on a number of levels.

> you were being backhanded and demeaning on a number of levels.

What an awful comment to make.

Re: Bzip3: A spiritual successor to BZip2

#156

Post by Sesse__ »

crazygringo wrote: post #77
loxias wrote: post #75

Earlier quoted context omitted.

> What I don't get isn't the benefits of BWT on its own. It's why BWT should add any additional benefit if you're already doing Huffman. Ahhhh. Now we're on the same page. :) Seeing how it helps when combined is somewhat subtle/non-obvious. I believe it relates to BWT and Huffman both being approximations of something more optimal. The two transforms could also have different window sizes -- one rarely does BWT on a…

Thanks. Yeah, I can see how that would make more sense if BWT was redundant under a theoretically perfect Huffman compression, but it happens to pick up some things that real-world Huffman encoders don't, with their practical limits on CPU and memory.

Nearly any real-world Huffman encoder is trivially optimal, i.e., given a set of symbols with probabilities, it is easy to construct the optimal set of output bits for each symbol. (There are some exceptions in that if you have a huge amount of symbols, or some that are extremely rare, you can bound the upper length and get a non-optimal code. This matters very little in practice, i.e., less than 0.1% in a typical setting. And of course, if you allow fractional bits or probabilities that change based on context, then you can do better, but then it's no longer Huffman.)

BWT is orthogonal to Huffman; like LZ, it exploits that some symbol _sequences_ are more common than others, while Huffman is about the optimality of coding each symbol on its own.

Re: Bzip3: A spiritual successor to BZip2

#157

Post by skrebbel »

loeg wrote: post #22
jgalt212 wrote: post #18

I poke around in this space periodically, but I've never found a compelling reason to move away from gzip.

zstd is faster and provides better compression than gzip at every point on the curve. There is no reason to use gzip these days other than backwards compatibility.

> There is no reason to use gzip these days other than backwards compatibility

And forward compatibility. The Lindy effect says gzip is likelier to be widely available across platforms and tools in the long term than zstd.

Re: Bzip3: A spiritual successor to BZip2

#158

Post by Brian_K_White »

adastra22 wrote: post #114
Brian_K_White wrote: post #99

Earlier quoted context omitted.

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.

You can get bash4 or 5 too, as I already said. I can't help you with your depth of experience. I didn't even say zstd was unfit to depend on, just that it was a fair question.

Re: Bzip3: A spiritual successor to BZip2

#159

Post by jgalt212 »

jgalt212 wrote: post #18

I poke around in this space periodically, but I've never found a compelling reason to move away from gzip.

After reading this, I see lots of zstd fans around here, and with good reason. That being said, I think our shop will stick with gzip until zstd arrives in the Python Standard Library.

Re: Bzip3: A spiritual successor to BZip2

#160

Post by maginx »

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.

I feel exactly the same, and have also implemented it backwards and forwards. I've thought about it in my sleep, trying to recall how it REALLY works. Happens every few years ;-) I always thought it was probably obvious to everyone else what the "magic" is.
Post reply on HN