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

Abstract

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—based on backward search and dynamic strings manipulation—to work in a context-wise fashion, using automata on words. Let $n$, $\sigma$, and $H_k$ be the text length, the alphabet size, and the $k$-th order empirical entropy of the text, respectively. Moreover, let $H_k^*=\min \{H_k+1,\lceil \log \sigma \rceil \}$. Under the word RAM model with word size $w\in \Theta (\log n)$, our algorithm builds the BWT in average $\mathcal {O}(nH_k^*)$ time using $nH_k^* + o(nH_k^*)$ bits of space, where $k=\log _\sigma (n/\log ^2 n)-1$. 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.