<p>Do you mean construction or inversion of BWT?</p>

<p>For construction, the best algorithm is probably the one by <a href="http://dx.doi.org/10.1007/978-3-642-03784-9_9">Okanohara and Sadakane</a>. It takes $O(n)$ time and usually requires $2n$ to $2.5n$ bytes of memory for an input of length $n$. There is an implementation available at <a href="https://code.google.com/p/csalib/">Google code</a>.</p>

<p>I am not that familiar with BWT inversion algorithms. The papers of Kärkkäinen and Puglisi at <a href="http://dx.doi.org/10.1007/978-3-642-15775-2_39">ESA 2010</a> and <a href="http://www.cs.helsinki.fi/juha.karkkainen/publications/ccp2011.pdf">CCP 2011</a> might provide a good starting point.</p>

CC BY-SA 3.0
2011-09-26T18:18:31.073Z
Inverting the suffix array permutation is O(n) isn't it?
Chad Brewbaker
CC BY-SA 3.0
2011-09-22T14:48:37.567Z
2011-09-22T14:48:37.567Z
Jouni Sirén
<p>What is the best solution for Inversion of <a href="http://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transform" rel="nofollow">Burrows-Wheeler Transform</a>?</p>

<p>One with the least number of steps.
(Best solution => One with a smaller average-case or worst-case time complexity)</p>

<p>Hopefully, a smaller time-complexity than  <a href="http://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transform#Example" rel="nofollow">this one</a>.</p>

CC BY-SA 3.0
2011-09-22T13:17:19.893Z
"This method" with or without the optimizations mentioned in the article? Did you use a trie?
Peter Shor 
CC BY-SA 3.0
2011-09-22T13:52:25.860Z
@Peter : yes, I'm working with those optimizations but the basic methos is the same.I wanted to know if there exists a better method.
vivek
CC BY-SA 3.0
2011-09-22T16:11:58.550Z
Did you ask the question because of this competition? http://www.gild.com/challenges/details/244 Either way I doubt this is *research level*.
Chao Xu
CC BY-SA 3.0
2011-09-22T17:53:28.737Z
@ChaoXu : yes, it's that competition, and yes, I'm not doing a research, if that is what you meant.
vivek
CC BY-SA 3.0
2011-09-22T18:02:14.493Z
@Downvoter: You should have the sense to tell me the exact reason. Without knowing what I did wrong, I'll be doing the same thing again.
vivek
CC BY-SA 3.0
2011-09-22T18:19:21.483Z
@vivek: I downvoted. Jouni Sirén's answer already pointed out that your question was not clear: the title is about the inverse transform, while the text seems to refer to the construction. Peter Shor's comment also pointed out that your question did not do a very good job at explaining exactly what you know already and what you have tried. Chao Xu hinted that your question might also be off-topic; it is currently formulated so that it does not sound like a research-level question (note that you did not specify exactly what you mean by "best": theory vs. practice, memory vs. time...).
Jukka Suomela
CC BY-SA 3.0
2011-09-22T18:21:17.750Z
@vivek: In brief, there are many opportunities for improving your question. Please edit it to remove any ambiguities, and to clarify exactly what you know already, what you want to know, and why. Show that you are serious and you have done your homework.
Jukka Suomela
CC BY-SA 3.0
2011-09-22T18:29:29.643Z
@JukkaSuomela : Nice explanation. I'll keep this in mind.
vivek
CC BY-SA 3.0
2011-09-22T21:28:27.607Z
Please also read the [FAQ](http://cstheory.stackexchange.com/faq).
Kaveh
CC BY-SA 3.0
2011-09-22T22:27:32.687Z
@Kaveh: Yes, read that one. Though I had missed it initially.Now I know this site is only for CS students.
vivek
CC BY-SA 3.0
2011-09-22T22:53:27.170Z
@vivek, the site is not for CS students, it is mainly for *researchers* in TCS.
Kaveh
CC BY-SA 3.0
2011-09-25T14:01:33.143Z
http://math.stackexchange.com/questions/66513/best-solution-for-inverse-of-burrows-wheeler-transform
Tsuyoshi Ito
<ds.algorithms>
Inverse of Burrows-Wheeler Transform
vivek
# Inverse of Burrows-Wheeler Transform

(Asked by: username_0 on 2011-09-22)

What is the best solution for Inversion of [Burrows-Wheeler Transform](http://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transform)?

One with the least number of steps.
(Best solution => One with a smaller average-case or worst-case time complexity)

Hopefully, a smaller time-complexity than [this one](http://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transform#Example).

**Tags:** ds.algorithms
> **Comments:**
> **username_1**: "This method" with or without the optimizations mentioned in the article? Did you use a trie?  
> **username_0**: @Peter : yes, I'm working with those optimizations but the basic methos is the same.I wanted to know if there exists a better method.  
> **username_2**: Did you ask the question because of this competition? http://www.gild.com/challenges/details/244 Either way I doubt this is *research level*.  
> **username_0**: @ChaoXu : yes, it's that competition, and yes, I'm not doing a research, if that is what you meant.  
> **username_0**: @Downvoter: You should have the sense to tell me the exact reason. Without knowing what I did wrong, I'll be doing the same thing again.  
> **username_3**: @vivek: I downvoted. Jouni Sirén's answer already pointed out that your question was not clear: the title is about the inverse transform, while the text seems to refer to the construction. Peter Shor's comment also pointed out that your question did not do a very good job at explaining exactly what you know already and what you have tried. Chao Xu hinted that your question might also be off-topic; it is currently formulated so that it does not sound like a research-level question (note that you did not specify exactly what you mean by "best": theory vs. practice, memory vs. time...).  
> **username_3**: @vivek: In brief, there are many opportunities for improving your question. Please edit it to remove any ambiguities, and to clarify exactly what you know already, what you want to know, and why. Show that you are serious and you have done your homework.  
> **username_0**: @JukkaSuomela : Nice explanation. I'll keep this in mind.  
> **username_4**: Please also read the [FAQ](http://cstheory.stackexchange.com/faq).  
> **username_0**: @Kaveh: Yes, read that one. Though I had missed it initially.Now I know this site is only for CS students.  
> **username_4**: @vivek, the site is not for CS students, it is mainly for *researchers* in TCS.  
> **username_5**: http://math.stackexchange.com/questions/66513/best-solution-for-inverse-of-burrows-wheeler-transform  

---

## 1 answers

### Answer by username_6 on 2011-09-22. Score: 11 | Accepted answer

Do you mean construction or inversion of BWT?

For construction, the best algorithm is probably the one by [Okanohara and Sadakane](http://dx.doi.org/10.1007/978-3-642-03784-9_9). It takes $O(n)$ time and usually requires $2n$ to $2.5n$ bytes of memory for an input of length $n$. There is an implementation available at [Google code](https://code.google.com/p/csalib/).

I am not that familiar with BWT inversion algorithms. The papers of Kärkkäinen and Puglisi at [ESA 2010](http://dx.doi.org/10.1007/978-3-642-15775-2_39) and [CCP 2011](http://www.cs.helsinki.fi/juha.karkkainen/publications/ccp2011.pdf) might provide a good starting point.

> **Comments:**
> **username_7**: Inverting the suffix array permutation is O(n) isn't it?  

---

