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

71–80 of 181 posts

Re: Bzip3: A spiritual successor to BZip2

#71

Post by crazygringo »

loxias wrote: post #68
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 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.

Re: Bzip3: A spiritual successor to BZip2

#72

Post by hinkley »

sophiebits wrote: post #59
hinkley wrote: post #54

Earlier quoted context omitted.

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

Other than that, Mrs Lincoln, how was the play?

Re: Bzip3: A spiritual successor to BZip2

#73

Post by hinkley »

adastra22 wrote: post #64
hinkley wrote: post #54

Earlier quoted context omitted.

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.

Yes, it's supported on all those platforms.

How far back?

Re: Bzip3: A spiritual successor to BZip2

#75

Post by loxias »

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.

> 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 whole 1GB file -- which introduce inefficiencies. Huffman coding is also only optimal in the very large alphabet and very long data limits. As your data length and alphabet size decrease, it gets less optimal.

Put differently, "I think that's a wonderfully phrased question, this _is_ my specialization/subfield, and I'm gonna need to chew on it for a while."

Re: Bzip3: A spiritual successor to BZip2

#76

Post by palaiologos »

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 OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

If you were willing to sign a commercial support contract with me on terms that we negotiated, I would be willing to provide you warranty.

If you were not aware, this is essentially the business model of WinRAR. The reason why tools like 7-Zip are not used by the public sector or companies (at least here) is that they provide no warranty in case of data loss. However, if you actually buy WinRAR, then you can hold them liable for damage to your archives. The "infinite 40 day trial" of WinRAR does not entitle you to compensation for damages and thus corporate entities and public entities have to buy WinRAR licenses. WinRAR has never cared about personal customers.

In general, having to cope with mild reliability of software is what you have to live with - you already get more than you paid for. Not to say that my tool is unreliable - I put a lot of effort into it, but it would put you in bad light to complain about something that you generously received for free :).

Re: Bzip3: A spiritual successor to BZip2

#77

Post by crazygringo »

loxias wrote: post #75
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.

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

Re: Bzip3: A spiritual successor to BZip2

#78

Post by jrockway »

loeg wrote: post #69
jrockway wrote: post #48

Earlier quoted context omitted.

I suppose the point of open source software is to edit the source code and make your own version. If you can't build it, you can't do that.

Zstd has lots of contributors who have all figured out how to edit and build it.

Yeah, not sure what the original commenter is complaining about. I did "git clone https://github.com/facebook/zstd", "cd zstd", "make" and have a working binary. Doesn't get easier than that.

Re: Bzip3: A spiritual successor to BZip2

#79

Post by CJefferson »

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?

Yes, it would actually be interesting to just have a bwt pass which does no compression, so we can then try lots of post compression options.

Re: Bzip3: A spiritual successor to BZip2

#80

Post by palaiologos »

Borg3 wrote: post #36
jgalt212 wrote: post #18

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

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 meeting in Ontario that I attended a while back. Let me know what you think :).

https://github.com/kspalaiologos/dev-urandom/blob/main/dos/B...

Post reply on HN