# Asymmetry in converting Burrows-Wheeler transform to suffix array?

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!

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

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.