1
$\begingroup$

Given a suffix array of a string $w$, it's possible to construct the Burrows-Wheeler transform of $w$ by subtracting one from the indices of the suffix array (wrapping around if necessary), then outputting the characters in $w$ that appear in that position.

However, to the best of my knowledge, there doesn't seem to be an algorithm to directly construct a suffix array for $w$ given the Burrows-Wheeler transform of the string $w$. It's still possible to do so in linear time by inverting the transform to get back $w$ and then constructing the suffix array directly, but that doesn't make any use of the transformed array.

Is there a fundamental reason why the reverse direction would be "harder" than the forward direction?

Thanks!

$\endgroup$
  • $\begingroup$ When you invert the BWT, you get the suffix array as a byproduct. $\endgroup$ – Jouni Sirén May 4 '14 at 14:23
2
$\begingroup$

It's possible to build the suffix array of $s$ in linear time from $s$ and $BWT(s)$ in a somewhat easy way. You do need to build a rank-select data structure on $s$ in order to do this.

To see how to do this, look at Ferragina and Manzini's paper "The FM-Index". The LF mapping they describe also essentially computes the suffix array.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.