Optimal compression boosting in optimal linear time using the Burrows-Wheeler Trasform

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 the time and space efficiency. More precisely, let $\alg$ be an algorithm that compresses a string~$s$ within $\lambda |s| \hlk{0}(s) + \mu$ bits of storage in $\Ob{T(|s|)}$ time, where $\hlk{0}(s)$ is the zeroth order entropy of the string $s$. Our booster improves $\alg$ by compressing~$s$ within $\lambda |s| \hlk{k}(s) + \log_2 |s| + g_k$ bits still using $O(T(|s|))$ time, where $\hlk{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 [CPM 2003]. They combined the Burrows-Wheeler Transform with dynamic programming and achieved our same compression bound but with running time $O(T(|s|)) + \Omega(|s|^2)$. We start from the same premises of Giancarlo and Sciortino, but instead of using dynamic programming we design a linear time optimization algorithm based on novel structural properties of the Burrows-Wheeler Transform.