BWT

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 …