  We extend Ziv and Lempel's model of finite-state encoders to the realm of
lossy compression of individual sequences. In particular, the model of the
encoder includes a finite-state reconstruction codebook followed by an
information lossless finite-state encoder that compresses the reconstruction
codeword with no additional distortion. We first derive two different lower
bounds to the compression ratio that depend on the number of states of the
lossless encoder. Both bounds are asymptotically achievable by conceptually
simple coding schemes. We then show that when the number of states of the
lossless encoder is large enough in terms of the reconstruction block-length,
the performance can be improved, sometimes significantly so. In particular, the
improved performance is achievable using a random-coding ensemble that is
universal, not only in terms of the source sequence, but also in terms of the
distortion measure.
