Yesterday, I posted a Definition of The Day on BWT and mentioned it can be reversed - read on to find out how!
T-ranking involves labelling each character in a text T such that its label indicates the number of previous occurrences of this character in T. For example, given a string T = abaaba$, we have TR = a0b0a1a2b1a3$
Using the method described in my previous post, we obtain BWT(TR) = a0b0b1a1$a2a3
How do we reverse it to obtain T again? We need the first column F = M of our matrix M that we used to compute BWT(TR). We can get this by lexicographically sorting BWT(TR), to obtain F = $a0a1a2a3b0b1. Remember that the rows of matrix M are lexicographically sorted, so F is very easy to obtain.
We now have the first and last columns of matrix M. Following our example, and given that the length of T is n, we have:
F L = M[n-1]
We now have to follow a path from the $ in F to its corresponding letter in L, which is a1. We find this letter in F and read its corresponding letter in L, which is b0. We then find b0 in F, and...
This is called LF-mapping. Following this path, and stopping just before we reach the $ in column L, gives us the reverse of the original text T'' = $a0b0a2a1b1a3. We reverse this (and remove the ranks) and obtain our original text T = abaaba$.
The example I used in this post is based upon these slides.