# 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.