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

51–60 of 181 posts

Re: Bzip3: A spiritual successor to BZip2

#51

Post by altairprime »

unnah wrote: post #37
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.

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?

Re: Bzip3: A spiritual successor to BZip2

#52

Post by chefandy »

loeg wrote: post #33
chefandy wrote: post #30

Earlier quoted context omitted.

Yeah I'm sick of this. Did you know you can't even use ext2/3/4 together on the same partition? What a mess.

The ext4/3 filesystems, notably, can read/write ext2 (and for ext4: ext3) filesystems in a compatible way.

Oh yeah true

Re: Bzip3: A spiritual successor to BZip2

#53

Post by thrtythreeforty »

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.

Thank you for the reference. I learned something new today. That algorithm is wild. If you had shown me the transform and asked if it had an inverse, I would have said of course it doesn't, it's too weird.

Re: Bzip3: A spiritual successor to BZip2

#54

Post by hinkley »

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.

Do zless, zcat and zgrep support zstd everywhere? And I mean everywhere? VMs? Alpine? FreeBSD? OSX? Openwrt?

Nothing is shittier than sshing into a box that doesn’t understand half of your command line tricks. Or the clever shell script you just tested six ways to Sunday. It’s like fighting with your hands tied behind your back.

Re: Bzip3: A spiritual successor to BZip2

#55

Post by vardump »

lexicality wrote: post #44
cwillu wrote: post #41

Earlier quoted context omitted.

Simple enough to be safe, at the cost of performance: uncompress and compare to the original.

And what do you do if it doesn't match?

Isn't it obvious? Warn the user, who can now use something else instead.

Re: Bzip3: A spiritual successor to BZip2

#56

Post by lexicality »

vardump wrote: post #55
lexicality wrote: post #44

Earlier quoted context omitted.

And what do you do if it doesn't match?

Isn't it obvious? Warn the user, who can now use something else instead.

That only works if the "user" is an interactive TTY with a human on the other end of it though. What if I tried using this for compressing automatic backups? Do I need an error handling routine that uses something else?

Re: Bzip3: A spiritual successor to BZip2

#57

Post by wongarsu »

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

Additional benchmarks on the same dataset:

    uncompressed               - 19'291'709'440
    bzip2 -9                   -  3'491'493'993 (sanity check)
    zstd -16 --long            -    593'915'849
    zstd -16 --long=31         -    122'909'756 (requires equivalent argument in decompressor due to needing ~4GB RAM)
    zstd -19 --long            -    505'728'419
    zstd -19 --long=31         -    106'601'594 (requires equivalent argument in decompressor)
    zstd --ultra -22           -    240'330'522
    zstd --ultra -22 --long=31 -     64'899'008 (requires equivalent argument in decompressor)
    rar a -m5 -md4g -s -mt8    -     64'837'044
As you notice my sanity check actually has a slightly different size. Not sure why. The benchmark is a bit underspecified because new perl versions were released in the interim. I used all releases up to perl-5.37.1 to get to the correct number of files. Just treat all numbers to have about 2% uncertainty to account for this difference.

I can't provide compression/decompression times, but the --long or --long=31 arguments should not have major impact on speed, they mostly impact used memory. --long=31 requires setting the same in the decompressor, making that option mostly useful for internal use, not archives meant for public consumption.

As you can see, the benchmark chosen by the author mostly comes down to finding similar data that's far away. I wonder if bzip3 can do this better than other algorithms (especially in less memory) or simply chose default parameters that use more memory.

Edit: added more benchmarks

Re: Bzip3: A spiritual successor to BZip2

#58

Post by forty »

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.

Haha I also studied as part of a student project and I remember my computer science teacher saying "it's dark magic" ^^

Re: Bzip3: A spiritual successor to BZip2

#59

Post by sophiebits »

hinkley wrote: post #54
loeg wrote: post #22

Earlier quoted context omitted.

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.

Do zless, zcat and zgrep support zstd everywhere? And I mean everywhere ? VMs? Alpine? FreeBSD? OSX? Openwrt? Nothing is shittier than sshing into a box that doesn’t understand half of your command line tricks. Or the clever shell script you just tested six ways to Sunday. It’s like fighting with your hands tied behind your back.

> other than backwards compatibility

Re: Bzip3: A spiritual successor to BZip2

#60

Post by chasil »

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…

The author of lzip goes into some degree of excitement on the reliability and recoverability of the lzip format compared to xz.

https://www.nongnu.org/lzip/xz_inadequate.html

I personally back up about a terabyte each week, and I use 7-zip because it has built-in encryption, which is required because of the HR data in the backup. Thank heavens for xargs -P.

I could use "openssl enc" combined with any pure compression utility, but I don't want to make decompression impossible if I get hit by a bus.

Post reply on HN