[Retr0id]

I still struggle to get my head around BWT. I understand what it does conceptually and why it helps, and I can read code that implements it, but I don't fully get it - there's a mental disconnect for me somewhere. Mainly, I can't convince myself that computing the inverse transform is possible.

It's one of those algorithms that I can say for sure I'd never have been able to come up with on my own.

[jgbyrne]

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.

[queuebert]

It's one of those things you saturate your brain with for a few days, then put it down, and two weeks later in the shower you figure it out.