Faster Average Case Low Memory Semi-External Construction of the Burrows-Wheeler Transform

The Burrows Wheeler transform has applications in data compression as well as full text indexing. Despite its important applications and various existing algo-rithmic approaches the construction of the transform for large data sets is still challenging. In this paper we present a new semi external memory algorithm capable of constructing the transform in time O(n log2 log n) on average if su-cient internal memory is available to hold a fixed fraction of the input text. In the worst case the run-time is O(n log n log log n).