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

141–150 of 181 posts

Re: Bzip3: A spiritual successor to BZip2

#141

Post by lifthrasiir »

omoikane wrote: post #87
chasil wrote: post #60

Earlier quoted context omitted.

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…

> https://www.nongnu.org/lzip/xz_inadequate.html I have replaced all my previous uses of xz with lzip ever since I read that page (via https://news.ycombinator.com/item?id=32210438 ), but for some reason lzip never seem to rise to the same level of fame as xz. bzip3 also wasn't benchmarked against lzip.

I think you should just skip both xz and lzip, because that essay is in my opinion technically correct but also only deals with a very much minor concern [1]. If you want the recovery out of archives, you should use dedicated formats like PArchive and not ordinary archives with half-baked recovery attempts.

[1] Previously: https://news.ycombinator.com/item?id=39873122

Re: Bzip3: A spiritual successor to BZip2

#142

Post by omoikane »

lifthrasiir wrote: post #141
omoikane wrote: post #87

Earlier quoted context omitted.

> https://www.nongnu.org/lzip/xz_inadequate.html I have replaced all my previous uses of xz with lzip ever since I read that page (via https://news.ycombinator.com/item?id=32210438 ), but for some reason lzip never seem to rise to the same level of fame as xz. bzip3 also wasn't benchmarked against lzip.

I think you should just skip both xz and lzip, because that essay is in my opinion technically correct but also only deals with a very much minor concern [1]. If you want the recovery out of archives, you should use dedicated formats like PArchive and not ordinary archives with half-baked recovery attempts. [1] Previously: https://news.ycombinator.com/item?id=39873122

For my personal backup use, I actually use RAR with recovery records, optionally with encryption if it's sensitive. I was only using xz in places where I couldn't use RAR (e.g. for work), and those places tend to also have lzip available.

Re: Bzip3: A spiritual successor to BZip2

#144

Post by ajb »

mnw21cam wrote: post #27
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 remember the lecturer commenting on what sort of sick and twisted mind could come up with such a ridiculous convoluted notion when I was taught it at university.

Wheeler was also one of the inventors of the "closed subroutine" AKA function, which had to be implemented via a hack as machines of the time did not include ISA support for "return":

https://en.m.wikipedia.org/wiki/Wheeler_Jump

Re: Bzip3: A spiritual successor to BZip2

#145

Post by thomasmg »

Improving BWT is great!

In my view, improving "long range" compression has the biggest potential. There are many, many algorithms and implementations for very short range (huffman, arithmetic, ANS) and short range (LZ, BWT), but not that much research has gone into "long range" yet. There's deduplication, and large-window LZ / BWT.. but not much more yet. What is missing is efficietly (and with little memory) finding similarities on multi-GB data sets. I think sorting by similarity would help there. Or did I miss research in this area?

Re: Bzip3: A spiritual successor to BZip2

#146

Post by ku1ik »

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…

Ooh, that’s neat. How much improved do you get from this? Is it more single or double digit % diff?

Re: Bzip3: A spiritual successor to BZip2

#147

Post by unnah »

thesz wrote: post #138
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…

It definitely is related to prediction by partial match (PPM). BWT sorts rotated data and what is achieved is that same suffixes group together: ... "Bzip2 and Bzip3 are simply combining more" "Bzip3 are simply combining moreBzip2 and " The preceding (to suffix) character goes to end and then gets outputted. This is much like PPM going backward. There is a PPM* algorithm (unbounded context length) where authors consi…

Wow, thanks. As always, the best way to learn more on the internet is to be confidently and totally wrong!

Re: Bzip3: A spiritual successor to BZip2

#148

Post by unnah »

derf_ wrote: post #129
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…

> There is no general compression theory in which BWT could be described as a special case. I would not really say this is true. BWT is spiritually similar to the various Prediction by Partial Matching (PPM) algorithms, except that instead of needing to decide how much context (i.e., preceding symbols) to use to model the next symbol, and carefully learning the probabilities for each unique context, it naturally sort…

Thanks for the reference, looks interesting.

Re: Bzip3: A spiritual successor to BZip2

#149

Post by Borg3 »

palaiologos wrote: post #80
Borg3 wrote: post #36

Earlier quoted context omitted.

Same here. Storage is not that expensive so I do NOT care to squize every byte out of archive. Also, im more into retro, so portability and memory usage is more importand for me :)

Hi, tool author here! Regarding your first remark: high ratio data compression has its time and place, and I personally understand that to many people it is not very desirable. In a lot of scenarios something as plain and simple as LZ4 generally suffices. On the other hand, there is an unofficial (= unsupported) port of bzip3 to older (386+) machines that run MS-DOS6.22. I have prepared it for a retrocomputing meetin…

Oh nice. Ill will look at it at some point to check things out and to see if I can compile it here and there out of the box :)

Re: Bzip3: A spiritual successor to BZip2

#150

Post by eru »

crazygringo wrote: post #71
loxias wrote: post #68

Earlier quoted context omitted.

I always understood it as working because of the predictability of a symbol/letter/token given the previous one. Sorting all the shifts of a string puts all the characters in order, then looking at the last column shows you all the _preceding_ characters. If there's any predictability there (which there often is), it's now easier to compress. It's sorta like an entropy coder in that way. I've never thought of it as b…

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.

> But shouldn't Huffman coding already detect that same predictability and compress it the same?

Huffman coding only works on individual letters. It doesn't know anything about relationships between adjacent letters.

Post reply on HN