A simplistic, universal lossy source code
A conceptually simple lossy source code, achieving distortion at most D, may be described as follows. A source sequence of length n from a finite alphabet A is parsed into blocks of some length k<n, which are placed in a dictionary. Among all potential codebooks containing source sequences of length k, one selects the smallest one such that every member of the dictionary is within distortion D of some member of the codebook. The codebook is then encoded and used to encode the blocks of the source sequence in the usual manner; i.e., each block is represented by the index of the closest codeword in the codebook. We show that if the block length k is chosen to minimize the encoding rate for the given source sequence, then this coding method is universal in the sense that for any stationary, ergodic source with the alphabet A, the encoding rate approaches the source rate-distortion function, R(D), as n increases.