libsais

This is one of the most useful documents on the web regarding bzip2 implementation. I wrote a bzip2 encoder in Rust [1] a couple of years ago and it would have been an uphill struggle without Joe Tsai's work. Like Tsai did for his Go implementation, I used the 'SA-IS' algorithm for computing the Burrows-Wheeler Transform. Unlike the algorithm used in the reference implementation of bzip2, it is linear time, which in practice means it has much better upper-bound performance (though is typically somewhat slower on average). The problem of suffix array construction, which SA-IS solves (with computation of the BWT being a natural corollary), is a very interesting one in which theoretical and practical advances are still being made. There is a notable implementation of SA-IS by Ilya Grebnov which is spectacularly fast due to usage of technique

Here some other BWT compressors in the large text compression benchmark (look for "BWT" in "Alg" column): http://mattmahoney.net/dc/text.html And here a BWT library with benchmarks: https://github.com/IlyaGrebnov/libsais#benchmarks