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[0] 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]

Â $ Â Â Â Â Â Â Â a0

Â a0Â Â Â Â Â Â Â b0

Â a1Â Â Â Â Â Â Â Â b1

Â a2Â Â Â Â Â Â Â Â a1

Â a3Â Â Â Â Â Â Â $

Â b0Â Â Â Â Â Â Â Â a2

Â b1Â Â Â Â Â Â Â a3

Â

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$.

Â

Amazing right?!

Â

The example I used in this post is based upon these slides.

[75]