# Reversing Burrows-Wheeler Transform

17 Mar 2017

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]