SIMPLE UNIVERSAL LOSSY DATA-COMPRESSION SCHEMES DERIVED FROM THE LEMPEL-ZIV ALGORITHM

Two universal lossy data compression schemes, one with fixed rate and the other with fixed distortion, are presented, based on the well-know n Lempel-Ziv algorithm. In the case of fixed rate R, our universal los sy data compression scheme works as follows: first pick a codebook B-n consisting of all reproduction sequences of length n whose Lempel-Ziv codeword length is less than or equal to nR, and then use B1 to encod e the entire source sequence n-block by n-block. This fixed-rate data compression scheme is universal in the sense that for any stationary, ergodic source or for any individual sequence, the sample distortion p erformance as n --> infinity is given almost surely by the distortion rate function. A similar result is shown in the context of fixed disto rtion lossy source coding.