Inequalities and Algorithms for Universal Data Compression

We describe nonasymptotic uniform bounds on the performance of data-compression algorithms in cases where the length $N$ of the training sequence (“history”) that is available to the encoder is not large enough so as to yield the ultimate compression, namely the entropy of the source. Two characteristic ultimate goals are considered: The lth-order entropy $H(X_1^\ell)$, and the associated conditional entropy $H(X_1^{\ell-k}|X_{-k+1}^0)$. The bounds are based on classical information-theoretic convexity arguments. Nevertheless, it is demonstrated that convexity arguments that work for some cases are totally useless for others. Furthermore, these classical convexity arguments, when properly used, lead to efficient universal data-compression algorithms for each of the cases considered. We limit the discussion to fixed-to-variable, uniquely decipherable codes.