This doesn't follow the original paper very closely, although I think the
device of putting an end-of-string marker into the data instead of including
the start index as a separate datum is an improvement over the original
algorithm. My own "explorable explanation" of the algorithm, at
http://canonical.org/~kragen/sw/bwt, is visually uglier, and is very similar to this page in many
ways, but it may still be of some interest: it follows the original paper more closely, which is likely to be
useful if you're trying to understand the paper. Also, I used an
inverse-transform algorithm that was efficient enough that you could imagine
actually using in practice, while still being easy to explain (from the
original paper)—but, like the page linked, I didn't use an efficient suffix-array-construction
algorithm to do the forward transform. I did link to the three that have been discovered.
This doesn't follow the original paper very closely, although I think the device of putting an end-of-string marker into the data instead of including the start index as a separate datum is an improvement over the original algorithm. My own "explorable explanation" of the algorithm, at http://canonical.org/~kragen/sw/bwt, is visually uglier, and is very similar to this page in many ways, but it may still be of some interest: it follows the original paper more closely, which is likely to be useful if you're trying to understand the paper. Also, I used an inverse-transform algorithm that was efficient enough that you could imagine actually using in practice, while still being easy to explain (from the original paper)—but, like the page linked, I didn't use an efficient suffix-array-construction algorithm to do the forward transform. I did link to the three that have been discovered.
I forget when I did this but apparently sometime around 02010: https://web.archive.org/web/20100616075622/http://canonical....
I think my JS code in that page is a lot more readable than the minified app.js served up with this page.