Hi Ivan,
Please send me an e-mail! Perhaps we can figure something out.
453 karma · joined February 28, 2019
Please send me an e-mail! Perhaps we can figure something out.
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?
Huffman coding is a static minimum-redundancy code. What this means is that it finds an optimal assignment of bit sequences to letters in the input alphabet (commonly US-ASCII or extensions). This however means that Huffman coding can not exploit redundancies that stem from the concrete sequence of characters. For example, you could easily predict that an `e` comes after `Th`, but Huffman coding can not know that.
Hence after applying the Burrows-Wheeler transform you need to have some sort of a higher-order transform (i.e. a transform that considers more than just individual bytes) which somehow reaps from the changed distribution of the result of the algorithm. But we will get to that in a second.
The joke here is that the Burrows-Wheeler transform is closely related to suffix trees and suffix arrays, which are often used in bioinformatics and HPC for full-text search. If you wanted to find a pattern of length `p` in a text of length `n`, if you already have a suffix tree of the original text, the search is linear in the length /of the pattern/ - i.e. O(p). The suffix tree stores all suffixes of a string in a compressed manner (i.e. it has a linear space overhead, approximately O(20n) as given by Gusfield, D. (1997). Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. Cambridge University Press), so you can search for a word in it by simply traversing from the root node to an internal or leaf node by following a sequence of bytes that comprise the word.
As such, a suffix tree (and equivalently suffix array and the BWT, which is trivially computed from a suffix array) form something which can be thought of as a static PPM model. Notably real world implementations of PPM use suffix trees as a part of their main storage data structure (e.g. PPMd). What this all means is that given a suffix tree, we can very cheaply give the probability distribution for the next byte that follows a given fixed-order sequence of bytes. This is nice, because then e.g. an order-2 predictor would be able to tell that `Th` is followed by `e` once enough data has been gathered.
As you can probably guess, the more preceding bytes you know, the better will be your estimate for what is the most likely next byte. But the larger your context, the more expensive the searches and computations become due to pointer chasing in the suffix tree.
So how do we remedy this? We notice that the Burrows-Wheeler transform essentially clusters similar contexts together, meaning that a low order predictor (= faster, simpler) on BWT compresses as well as a high order predictor (= slow, complicated) on the original data, at the cost of an extra transformation. This is viable, because the Burrows-Wheeler transform can be quickly computed and there have been recent advancements in running it on the GPU. So what this means is that bzip3 uses BWT + a low order predictor with an arithmetic coder to encode the bytes, meaning that it can make use of high order statistics for compression and performs comparably at a faster speed.
Thank you for your benchmark!
As you may be aware, different compression tools fill in different data type niches. In particular, less specialised statistical methods (bzip2, bzip3, PPMd) generally perform poorly on vaguely defined binary data due to unnatural distribution of the underlying data that at least in bzip3's case does not lend well to suffix sorting.
Conversely, Lempel-Ziv methods usually perform suboptimally on vaguely defined "textual data" due to the fact that the future stages of compression that involve entropy coding can not make good use of the information encoded by match offsets while maintaining fast decompression performance - it's a long story that I could definitely go into detail about if you'd like, but I want to keep this reply short.
All things considered, data compression is more of an art than science, trying to fit in an acceptable spot on the time to compression ratio curve. I created bzip2 as an improvement to the original algorithm, hoping that we can replace some uses of it with a more modern and worthwhile technology as of 2022. I have included benchmarks against LZMA, zstandard, etc. mostly as a formality; in reality if you were to choose a compression method it'd be very dependent on what exactly you're trying to compress, but my personal stance is that bzip3 would likely be strictly better than bzip2 in all of them.
bzip3 usually operates on bigger block sizes, up to 16 times bigger than bzip2. additionally, bzip3 supports parallel compression/decompression out of the box. for fairness, the benchmarks have been performed using single thread mode, but they aren't quite as fair towards bzip3 itself, as it uses a way bigger block size. what bzip3 aims to be is a replacement for bzip2 on modern hardware. what used to not be viable decades ago (arithmetic coding, context mixing, SAIS algorithms for BWT construction) became viable nowadays, as CPU Frequencies don't tend to change, while cache and RAM keep getting bigger and faster.
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...
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 :).
As for the compression: probably an artifact of a bigger block size and a closer-to-optimal entropy coding stage in bzip3 (simple model + binary arithmetic coding; fast suffix sorting due to research of Ilya Grebnov) vs bzip2's suboptimal implementation of what could have been Package-Merge that currently assigns excessively long Huffman codes (as I discovered while doing research for my data compression book); also probably the RLEs everywhere that Seward considers a mistake, small BWT blocks, etc. You could try the tool https://pastebin.com/6DUKs4q9, which eliminates the redundancy associated with the Malbolge encoding (which bzip3 kind of catches on without any preprocessing, while bzip2 not entirely) and drastically improves performance of all other compressors:
% ./a d <blc.mb >blc.n
% bzip3 -vfb50 blc.n
blc.n: 48175489 -> 647179 bytes, 1.34%, 0.11 bpb
% bzip3 -vfb50 blc.mb
blc.mb: 48175489 -> 1025582 bytes, 2.13%, 0.17 bpbI also don't see robust error handling in your code, which usually costs lines of code (especially in C) too.
The difference in delta technique is certainly not negligible, as my code still uses Colin Percival's algorithm, while you seem to have settled on something else. It's also important to point out that being "better than xdelta" means pretty much the same as "having more than nothing", because xdelta has already been superseded 20 years ago by bsdiff[1], which in turn would ideally be superseded by my project.
[1]: https://www.daemonology.net/bsdiff/ time ./bsc e ../linux.tar linux.bsc -e2 -b16 -T
68.69s user 1.14s system 99% cpu 117M memory 1:09.84 total
% bzip3 -e -j 6 -b 50 corpus/calgary.tar
% bzip3 -j 6 -b 50 corpus/calgary.tar
bzip3 - A better and stronger spiritual successor to bzip2.
Copyright (C) by Kamila Szewczyk, 2022. Licensed under the terms of GPLv3.
Usage: bzip3 [-e/-d/-t/-c] [-b block_size] input output
Operations:
-e: encode
-d: decode
-t: test
Extra flags:
-c: force reading/writing from standard streams
-b N: set block size in MiB
-j N: set the amount of parallel threads
% cat corpus/calgary.tar | bzip3 -b 10 -e -c | wc -c
807959
% wc -c linux.tar.zst linux.bz3 134980904 linux.tar.zst 129255792 linux.bz3
what bzip3 aims to be is a replacement for bzip2 on modern hardware. what used to not be viable decades ago (arithmetic coding, context mixing, SAIS algorithms for BWT construction) became viable nowadays, as CPU Frequencies don't tend to change, while cache and RAM keep getting bigger and faster.
it should be noted that while using 16 times larger block sizes than bzip2 while providing compression ratios up to 10%-50% better at a cost of, as empirically shown, 17 seconds per 1.3GB of data, is a pretty good trade-off and if bzip2 wanted to get anywhere close to that (e.g. using the C API to tweak the block size), it'd have to sacrifice a lot of its performance.
Which is mainly why I'll never reveal how my Malbolge tooling exactly works - uncertainity is stronger than reason. Maybe because of the mindset people have that "if an explanation is published, it must be simple" paired together with "it's incredibly long and boring, so i'm not going to read it".
And indeed, there existed a small bug in my generator code, which was discovered after 1.5 years, because that's how long it took for someone to try reading and understanding the entire blog post...
> anything can be trivially transpiled to any turing-complete language regardless of the "difficulty" of the language once basic operators are established
Yes! It already was. There exists the Nagoya toolchain which I'm aware of, but it's generated code simply is too inefficient and unstable (from my testing) to be ran on contemporary machines. To write efficient Malbolge programs, like I just did, you'd need to implement a good chunk of "basic" operations in Malbolge (or, for the record, low level assembly which maps really well to Malbolge itself).
> the entire sadistic point of the esoteric exercise is to dwell in the agony of unaccomplishment, not roll it up using a toolchain.
It's easy to program assembly, it's hard to write a compiler that targets good assembly. As humans we've been striving to make good compilers for ages, yet still we're not even close. So, I'd say, the fact that I made it _using_ a toolchain makes it even more impressive.
> this audience knows anything can be trivially transpiled to any turing-complete language
This is the definition of Turing-completeness and I'd be surprised if this audience didn't know it. But I wouldn't be so sure about it being trivial. Two questions:
1) How do you "obviously" target cyclic tag systems and the Rule 110 automation?
2) How do you make it efficient? If we assume the simplest way of transpiling, we'll get nowhere near _actual usability_ (to some degree) which MalbolgeLisp exhibits.
I used my existing project called asm2bf: https://github.com/kspalaiologos/asmbf (feel free to check it out), as a base for the high level assembler. And the original Lisp has been written in a tweaked version of it.
Once I was done, I optimised the high level version, and then took the asm2bf compiler output and did a few optimisations manually on it (everything that my peephole optimisation didn't catch).
In fact, many relatively credible places I've seen, like my national-language Wikipedia use the word "impossible" - I just want to break the myth :).
BTW: In the rules, I can only see "Please don't do things to make titles stand out, like using uppercase or exclamation points, or saying how great an article is. It's implicit in submitting something that you think it's important." - I don't think my submissions breaks this rule (please let me know if it does!). To adress the other point, the original title/name is in the README (and it's MalbolgeLisp v1.1, or the repo name, as you wish - malbolge-lisp), not in the Github description. I felt like it's not descriptive enough and might be misleading (since you could interpret it as a malbolge interpeter _in_ lisp).