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₀*(s)+ bits of storage in O(T(|s|)) time, where H₀*(s) is the zeroth order entropy of the string s. Our booster improves A by compressing s within λ|s|H_k*(s) + log₂ |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|²). 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.