Average Linear Time and Compressed Space Construction of the Burrows-Wheeler Transform

The Burrows-Wheeler Transform is a text permutation that has revolutionized the fields of pattern matching and text compression, bridging the gap existing between the two. In this paper we approach the BWT-construction problem generalizing a well-known algorithm\u2014based on backward search and dynamic strings manipulation\u2014to work in a context-wise fashion, using automata on words. Let n , \u3c3 , and Hk be the text length, the alphabet size, and the k -th order empirical entropy of the text, respectively. Moreover, let H 17k=min{Hk+1,\u2308log\u3c3\u2309} . Under the word RAM model with word size w 08\u398(logn) , our algorithm builds the BWT in average O(nH 17k) time using nH 17k+o(nH 17k) bits of space, where k=log_\u3c3(n/log2n) 121 . We experimentally show that our algorithm has very good performances (essentially linear time) on DNA sequences, using about 2.6 bits per input symbol in RAM