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

Share on Facebook
Share on Twitter
Share on LinkedIn
Please reload

Please reload

Related Posts
PhDomics by Fatima