Universal Almost Sure Data Compression

An n-code is a mapping cₙ from the set Aⁿ of sequences of length n drawn from a finite set A into the set of finite length binary sequences B^. A decoder with distortion D is a map from B^ back into Aⁿ that sends cₙ(aⁿ₁) into a sequence that agrees with aⁿ₁ in all but at most $Dn$ places. We describe a sequence of codes and associated decoders of distortion D such that, for almost every sequence from an ergodic process, the number of bits per A-symbol converges almost surely to $R(D)$, the optimal compression attainable for the process. The codes are universal in that the statistics of the process need not be known in advance. Expected value results of this type were first obtained by Davisson and, independently, Fittinghof; almost sure results for the invertible case $(D = 0)$ are implicitly contained in the Ziv-Lempel algorithm. Our results also apply, virtually without change in proof, to random fields.