HNHacker News
TopNewBestAskShowJobs

jgbyrne

18 karma · joined August 15, 2020

submissionscomments
jgbyrne··on Bzip2 Format Specification (2016) [pdf]
I think it really helps to stop thinking about the string as a linear sequence with a beginning and end, and instead consider an unbroken loop of characters. Literally imagine the string written into a circle like the letters on an Enigma rotor.

Then you can consider the construction of all the substrings of length 2, length 3, and so on. You may also wish to consider the same induction, but working backwards from its conclusion. Start by considering the set of n length substrings, then the n-1 length substrings, etc.

Either way, your objective should be to convince yourself that you can reconstruct the whole ring from the BWT. At this point it is not hard to make the final leap to understand how it can be applied to regular strings.

jgbyrne··on Bzip2 Format Specification (2016) [pdf]
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 techniques like cache prefetching [2]. It's worth a look for anyone interested in really high performance software compression.

[1] https://github.com/jgbyrne/banzai/

[2] https://github.com/IlyaGrebnov/libsais

jgbyrne··on Migrating from Warp to Axum
I did the exact same thing with my imageboard, plainchant [1]. I had the same experience that you did with Warp: the routing model was extremely clever, but never came to feel intuitive or ergonomic to me.

[1] https://github.com/jgbyrne/plainchant

jgbyrne··on A-Levels: The Model is not the Student
There is good evidence that comprehensive school pupils were disadvantaged and independent school pupils were advantaged, when you dig beneath the overall averages.