Fast BWT in small space by blockwise suffix sorting

We present a new space- and time-efficient algorithm for computing the Burrow-Wheeler transform (BWT). For any choice of a parameter upsilon E [3, n(2/3)], the computation of BWT for a text of length n takes O(n log n + vn) worst-case time and O(n log n + root upsilon n) average-case time using O(n log n/root upsilon) bits of space in addition to the text and the BWT. For example, if upsilon = log(2) n, the time is O(n log2 n) in the worst case and O(n log n) on an average with the additional space requirement of O(n) bits. The algorithm is alphabet-independent: it uses only character comparisons, and the complexities do not depend on the alphabet size unless upsilon does. A practical implementation is 2-3 times slower than one of the fastest and most space-efficient previous algorithms while needing only one-third of the main memory. The algorithm is based on suffix arrays, but unlike any other algorithm, it can construct the suffix array a small block at a time without storing the rest of the suffix array anywhere. (c) 2007 Elsevier B.V. All rights reserved.