Compression Boosting in Optimal Linear Time Using the Burrows-Wheeler Transform

In this paper we provide the first compression booster that turns a zeroth order compressor into a more effective k-th order compressor without any loss in time efficiency. More precisely, let A be an algorithm that compresses a string s within λ|s|H 0*(s)+ bits of storage in O(T(|s|)) time, where H 0*(s) is the zeroth order entropy of the string s. Our booster improves A by compressing s within λ|s|H k*(s) + log 2 |s| + gk bits still using O(T(|s|)) time, where H k*(s) is the k-th order entropy of s. The idea of a "compression booster" has been very recently introduced by Giancarlo and Sciortino in [7]. They combined the Burrows-Wheeler Transform with dynamic programming and achieved our same compression bound but with running time O(T(|s|)) + Ω(|s| 2). We start from the same premises of [7], but instead of using dynamic programming we design a linear time optimization algorithm based on novel structural properties of the Burrows-Wheeler Transform.