|
|
|
|
|
by jgbyrne
806 days ago
|
|
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. |
|