Fast BWT in small space by blockwise suffix sorting

AbstractWe present a new space- and time-efficient algorithm for computing the Burrow–Wheeler transform (BWT). For any choice of a parameter v∈[3,n2/3], the computation of BWT for a text of length n takes O(nlogn+vn) worst-case time and O(nlogn+vn) average-case time using O(nlogn/v) bits of space in addition to the text and the BWT. For example, if v=log2n, the time is O(nlog2n) in the worst case and O(nlogn) 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 v 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