How does this compare to existing BWT-based compressors on things like the Large Text Compression Benchmark?
Bzip3: A spiritual successor to BZip2
121–130 of 181 posts
Re: Bzip3: A spiritual successor to BZip2
#122Small 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.
That only works if the standard actually describes what you're supposed to do with extra data at the end, and everyone agrees.
In practice, there have been antivirus bypasses that made use of AV scanners treating the additional data differently from common extraction software (I believe it was winrar?).
One could argue that a text document with a corrupt file size byte should still be decodeable. One could also argue that the file is completely corrupt and should be treated as such. Knowing that there will be tools that will take the first approach regardless, I'd stick to just decoding the extra data and marking the file as potentially damaged rather than send the user down a data recovery rabbit hole for a file that'll decompress just fine.
Re: Bzip3: A spiritual successor to BZip2
#123Earlier quoted context omitted.
How much does that matter? All currently supported releases at least.
Seriously? There are places still migrating off of Java 8. And pet servers still exist in the wild.
Java 8 will be supported until 2032 if you pick the right distro, and that distro comes with zstd in the repos (if not pre-installed).
And if your system is so old that you don't have access to eight-year-old software, I don't see why the rest of the world needs to accommodate you. Sticking with weird and old software is fine, but that comes with the risk of having to deal with everyone else moving on.
Re: Bzip3: A spiritual successor to BZip2
#124Earlier quoted context omitted.
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?
Your automatic backups may actually be corrupted by random bit flips. Happens quite a lot with ZFS NAS systems where the admin forgot to set up a scrub job and still uses incremental backups.
Any read or write could fail for a multitude of reasons. The chance of an entire file being lost is rather small, but it's still an edge case that can happen in the real world if the FS flips to read only at just the wrong time. Hell, on platforms like macOS, you can't even assume fsync returning success will actually write floating data to storage!
Re: Bzip3: A spiritual successor to BZip2
#125> 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…
[dead]
Re: Bzip3: A spiritual successor to BZip2
#126Earlier 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?
I think you would just need ANS, not the rest of zstd.
Re: Bzip3: A spiritual successor to BZip2
#127strange that bzip3 is not yet listed on the large text compression benchmark http://mattmahoney.net/dc/text.html
But it does have many, many BWT based implementations. Might be interesting to benchmark it against e.g. bsc[1]
Re: Bzip3: A spiritual successor to BZip2
#128Everytime someone says I'm too smart, i remember this kind of black magic and inmediately answer: no, im not
Re: Bzip3: A spiritual successor to BZip2
#129I'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…
> 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 sorts symbols with the same context (of _any_ length) so they appear next to each other, and relies on adaptation to update your learned statistics as you move from one context to the next, without ever explicitly tracking context boundaries [0].
[0] N.J. Larsson, "The Context Trees of Block Sorting Compression," 1998. https://ieeexplore.ieee.org/abstract/document/672147
Re: Bzip3: A spiritual successor to BZip2
#130Earlier quoted context omitted.
zstd is a great setup, for sure, but the build system they use is patently awful. Can someone make an autoconf or hell, even CMake build system for them pleasee???
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.