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.
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this communityWhat 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.
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.