Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

bzip3

github.com

Post reply on HN
Print view View original

121–130 of 133 posts

Re: bzip3

#121

Post by Szpadel »

cb321 wrote: post #41
ot wrote: post #12

The benchmarks are disingenuous, to the point of looking cherry-picked. The block size for bzip3 is set to 512MB, but the window size for zstd is left to its default (8MB I believe for high levels). So in this corpus, which is made up of all versions of Perl source code concatenated, the window is too small to see all the identical files and just match them. Also corpora made out of very long repetitions are pretty m…

I just tried a tar file of a git clone of the linux kernel sources where the most recent commit is 72c395024dac5e215136cbff793455f065603b06 (early Feb of this year). zstd -19 got a slightly smaller size (3582930348 bytes vs bz3 -b 511's 3597411687 bytes or 0.4% advantage to zstd). More significantly 4-core zstd decompression was 2.05 seconds vs a whopping 297 seconds for bzip3 -dj4 - 145x or over 2 orders of magnitud…

[dead]

Re: bzip3

#123

Post by palaiologos »

algorithm314 wrote: post #122
spyc wrote: post #111

Earlier quoted context omitted.

How is this source code the original source and which parts? Please elaborate.

Source of agiannis_text. He probably decompiled it.

Tool author here. Sure, out of all bait in this thread I will bite this one. Curiously, it seems like Konstantinos has opened this ticket, i.e. https://github.com/iczelia/bzip3/issues/177, and open-sourced his algorithm here -- https://codeberg.org/kagiannis/gdcc-2021. As the allegation is very serious, I will also copy the edited version of this response to my website.

I have not seen his tool before, or even was aware of it. However, once you take a closer look, you notice that these two tools could not be more dissimilar. Agiannis' compressor uses a compact context representation to group bytes, followed by RLE and prefix coding. Bzip3 combines repetition removal (here via a run-length code -- prior to the BWT -- and LZP of Charles Bloom), a full Burrows–Wheeler transform, and a richer (thus slower) statistical arithmetic coder. The use of RLE for post-coding the BWT output dates as far back to Julian Seward, perhaps even further. The RLE and LZP are applied before the Burrows-Wheeler transform (as opposed to the implementation in `text', which makes a big difference). Bzip3 uses a proper SAIS library for the forward and backward transforms. Konstantinos' entropy coder seems to use FPC (bytewise prefix codes over adaptively selected subblocks), bzip3 uses an idea similar to this of bcm, which itself descends from Mahoney and ancient work of JS Vitter on arihtmetic coding, where a bitwise arihtmetic coder is input mixed probability estimates from exponential-moving averages with probability refinement.

You are welcome to conduct your own analysis, but this is the gist of it -- perhaps Konstantinos has convinced himself that he had invented run-length coding?

Re: bzip3

#124

Post by teiferer »

mitxela wrote: post #120
teiferer wrote: post #32

Earlier quoted context omitted.

It's beyond me why such foundational libraries don't have formal correctness proofs attached these days.

formal correctness proof is ridiculously hard, like, insanely hard, have you ever tried writing one for any real algorithm (not a platonic ideal quicksort)?

I have. And it is ridiculously hard.

But having your decompression algorithm not produce what you compressed earlier is also ridiculously bad.

So, seems worth the effort, given that AI can do lots the heavy lifting these days.

Re: bzip3

#125

Post by bmacho »

LtWorf wrote: post #53
red_admiral wrote: post #46

Why LGPL when the original license is more permissive? ( https://sourceware.org/bzip2/manual/manual.html )

Please stop questioning people's choice of license. If you don't like it, you're entitled to not using it.

Different people have different licence preferences. "Why this and not that" questions usually don't spark joy. (Might seem fine for the individual who asks it, but not really in a community.)

Re: bzip3

#126

Post by account42 »

idoubtit wrote: post #99
andruby wrote: post #72

Earlier quoted context omitted.

> “bzip3 is not yet listed on the large text compression benchmark” It is now And it comes in relatively well, in my opinion. I'm a compression amateur, but bzip3 is the first entry I recognize as a general purpose compression program.

Yes, bzip3 compresses that 1GB text file into 170 MB while zstd needs 213 MB (SI units, from my own tests with the "enwik9" file of the GP's page, and the latest releases of both programs, same commands). But the decompression (memory and speed) is a different story. On my desktop, decompressing with zstd requires 128 MB and 1 s, while bzip3 uses 3.2 GB and 90 s. Without `-b 511`, bzip3's ratio decreases and decompre…

Bzip2 has also always be a pig on decompression so I was fearing that this was the catch here as well.

Might still be useful as an archival compression format even if it will be less useful for distribution.

Re: bzip3

#127

Post by account42 »

_flux wrote: post #100
sehw wrote: post #73

For data recovery of archival stuff it's better to keep it uncompressed, no?

So apparently zamadatix's point wasn't well taken, but I think it could be an effective approach to store the same data twice over to increase the likelihood of successful recovery. Could be even be even ten times, or e.g. 6+4 with redundant recovery coding. Although you do have a point that the compressed data might be more difficult to decipher, if it doesn't have sufficient redundancy to skip bad parts, or if it i…

Error correction codes would be a much better use than simply duplicating the data.

Re: bzip3

#128

Post by account42 »

LtWorf wrote: post #53
red_admiral wrote: post #46

Why LGPL when the original license is more permissive? ( https://sourceware.org/bzip2/manual/manual.html )

Please stop questioning people's choice of license. If you don't like it, you're entitled to not using it.

You're also entitled to not comment on discussions you're not interested in. License discussion is very much relevant for anything that might end up being used for data interchange.

Re: bzip3

#129

Post by self_awareness »

TonyTrapp wrote: post #74
self_awareness wrote: post #28

Any relation to Iczelion from the masm32 tutorial?

Those tutorials are about as old as the author of the repository.

Yes, that's why I was wondering about any relations.

But later I've read that there was some kind of Anime called Iczelion (or it was the hero name, whatever). Author also is interested in anime, I guess that's the reason for nickname similarity. Mystery solved.

Re: bzip3

#130

Post by sylware »

vintermann wrote: post #22
adrian_b wrote: post #8

Earlier quoted context omitted.

No. It is an unrelated algorithm.

It's a very strange algorithm completely different from most compression methods, that's what makes it interesting IMO. But it's probably not realistically competitive, since one needs to do more after the burrows-wheeler transform, and all that "more" has been ridiculously more optimized in zstd and other modern compression methods. Compressing bwt-transformed data is easier, but that doesn't mean it's easy to furth…

I saw bellard neural net compression benchmarks. If you have time and performant system, based on the semantic of the data to compress, neural net seems tough to beat.

It is a matter of good compromises: speed and efficacy. I even wonder if LZMA2 is worth replacing bzip2.

Post reply on HN