Lossy Lempel-Ziv like compression algorithms for memoryless sources

Abstract

We analyze Lempel-Ziv (LZ78) like schemes for lossy compression of memoryless sequences. Given a distortion level and an input sequence x̄, the encoder splits the input sequence into phrases, representing each phrase by a potentially distorted phrase of the same length. Unlike the memoryless case, the distorted representation of a phrase is not uniquely defined by the LZ78 parsing mechanism. The crux of extending the LZ78 parsing scheme for the lossy setting is in the choice of the several possible representations of every phrase of x̄. Indeed, certain natural generalizations of the Lempel Ziv parsing scheme to the lossy case have been shown to be suboptimal. We consider Codelet Parsing, a LZ78 like algorithm which chooses a representation of x̄ based on the notion of lower mutual information. Given a distortion level, string and a type, the lower mutual information is a single-letter characterization of the size of set of sequences of the type matching the string to within the specified distortion level. In this paper, we try to understand the Codelet Parsing algorithm, by considering an indealization of the same, and showing that the coding rate of the idealized algorithm is asymptotically optimal. The emphasis in this paper is not the tightest analysis possible, but relative simplicity in analysis that can still bring out many of the empirically observed phenomena of Codelet Parsing. © 2011 IEEE.