6 ms·

Previously: “Hi, tool author here.” A useful explanation of Burrows-Wheelers transform as used by bzip3: https://news.ycombinator.com/item?id=42902407 https://

Previously: “Hi, tool author here.” A useful explanation of Burrows-Wheelers transform as used by bzip3: https://news.ycombinator.com/item?id=42902407 https://news.ycombinator.com/item?id=42902407 “bzip3 is not yet listed on the large text compression benchmark” It is now: https://mattmahoney.net/dc/text.html https://mattmahoney.net/dc/text.html (2 years ago, 176 comments) https://news.ycombinator.com/item?id=42899713 https://news.ycombinator.com/item?id=42899713 (4 years ago, 104 comments) https://news.ycombinator.com/item?id=31324439 https://news.ycombinator.com/item?id=31324439

p-e-w 10d ago
> “Hi, tool author here.” A useful explanation of Burrows-Wheelers transform as used by bzip3 FWIW, the Burrows-Wheelers transform is also used by bzip2, so this isn’t a new feature even though that quote kinda sounds like it is.
- altairprime 9d ago
  It’s also used in this paper blending an aspect of LZ77 with BWT: https://arxiv.org/abs/1502.05937 https://arxiv.org/abs/1502.05937 https://github.com/nicolaprezza/lz-rlbwt https://github.com/nicolaprezza/lz-rlbwt Which leads me to wonder if someone did, in fact, solve how to ‘combine zstd and bzip’ (so to speak) since the last time.
- mitxela 9d ago
  They missed an opportunity to call it the Wheel-Burrow algorithm didn't they
andruby 10d ago
> “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.
- deleted 9d ago
  [deleted]
- idoubtit 9d ago
  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 decompression requires about the same memory as zstd. But the decompression is still two orders of magnitude slower.
  - abrookewood 9d ago
    This should get more attention - those decompression requirements are a massive impost.
  - account42 9d ago
    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.
  - ahknight 8d ago
    Feels like it's the opposite of what it should be. It's fine to impose the world on the compression side, but decompression should be optimized for low-end devices. This is where deflate and zstd get it.
deleted 9d ago
[deleted]
altairprime 9d ago
> It is now: Matt added bzip3 to the benchmark seemingly after the last year thread. If the zstd benchmark, last update at max 22 in 2016, were to be updated for today’s zstd (for long-range if nothing else) after coming across this thread, what would be the most compact possible list of option sets to benchmark to reflect the value of LR et al.?

p-e-w 10d ago

> “Hi, tool author here.” A useful explanation of Burrows-Wheelers transform as used by bzip3 FWIW, the Burrows-Wheelers transform is also used by bzip2, so this isn’t a new feature even though that quote kinda sounds like it is.

altairprime 9d ago
It’s also used in this paper blending an aspect of LZ77 with BWT: https://arxiv.org/abs/1502.05937 https://arxiv.org/abs/1502.05937 https://github.com/nicolaprezza/lz-rlbwt https://github.com/nicolaprezza/lz-rlbwt Which leads me to wonder if someone did, in fact, solve how to ‘combine zstd and bzip’ (so to speak) since the last time.
mitxela 9d ago
They missed an opportunity to call it the Wheel-Burrow algorithm didn't they

andruby 10d ago

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

deleted 9d ago
[deleted]
idoubtit 9d ago
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 decompression requires about the same memory as zstd. But the decompression is still two orders of magnitude slower.
- abrookewood 9d ago
  This should get more attention - those decompression requirements are a massive impost.
- account42 9d ago
  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.
- ahknight 8d ago
  Feels like it's the opposite of what it should be. It's fine to impose the world on the compression side, but decompression should be optimized for low-end devices. This is where deflate and zstd get it.

deleted 9d ago

[deleted]

altairprime 9d ago

> It is now: Matt added bzip3 to the benchmark seemingly after the last year thread. If the zstd benchmark, last update at max 22 in 2016, were to be updated for today’s zstd (for long-range if nothing else) after coming across this thread, what would be the most compact possible list of option sets to benchmark to reflect the value of LR et al.?