Match-length functions for data compression

We investigate uniquely decodable match-length functions (in short, MLFs) in conjunction with LZ-type data compression. A MLF of a data string is a function that associates a non-negative integer with each position of the string. The MLF is used to parse the input string into phrases. The codeword for each phrase consists of a pointer to the beginning of a maximal match consistent with the MLF value at that point. We propose several sliding window variants of LZ compression employing different MLF strategies. Following the techniques of Wyner and Ziv, we show that the proposed methods are asymptotically optimal for stationary ergodic sources and that their convergence compares favorably with the LZ1 variant of Wyner and Ziv