<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2014-05-04T11:37:41.253Z
2014-05-04T11:37:41.253Z
greg
<p>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.</p>

<p>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.</p>

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

<p>Thanks!</p>

CC BY-SA 3.0
2014-05-04T14:23:03.903Z
When you invert the BWT, you get the suffix array as a byproduct.
Jouni Sirén
<ds.algorithms><ds.data-structures>
Asymmetry in converting Burrows-Wheeler transform to suffix array?
templatetypedef
# Asymmetry in converting Burrows-Wheeler transform to suffix array?

(Asked by: username_0 on 2014-05-03)

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!

**Tags:** ds.algorithms, ds.data-structures
> **Comments:**
> **username_1**: When you invert the BWT, you get the suffix array as a byproduct.  

---

## 1 answers

### Answer by username_2 on 2014-05-04. Score: 3

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.


---

