What is the best solution for Inversion of Burrows-Wheeler 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.
-1
-
4$\begingroup$ "This method" with or without the optimizations mentioned in the article? Did you use a trie? $\endgroup$ – Peter Shor Sep 22 '11 at 13:17
-
4$\begingroup$ Did you ask the question because of this competition? gild.com/challenges/details/244 Either way I doubt this is research level. $\endgroup$ – Chao Xu Sep 22 '11 at 16:11
-
2$\begingroup$ @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...). $\endgroup$ – Jukka Suomela Sep 22 '11 at 18:19
-
2$\begingroup$ @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. $\endgroup$ – Jukka Suomela Sep 22 '11 at 18:21
-
2$\begingroup$ Please also read the FAQ. $\endgroup$ – Kaveh Sep 22 '11 at 21:28
11
$\begingroup$
$\endgroup$
Do you mean construction or inversion of BWT?
For construction, the best algorithm is probably the one by Okanohara and Sadakane. 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.
I am not that familiar with BWT inversion algorithms. The papers of Kärkkäinen and Puglisi at ESA 2010 and CCP 2011 might provide a good starting point.
-
$\begingroup$ Inverting the suffix array permutation is O(n) isn't it? $\endgroup$ – Chad Brewbaker Sep 26 '11 at 18:18
