We investigate uniquely decodable match-length functions (MLFs) in conjunction with Lempel-Ziv (1977) type data compression. An MLF of a data string is a function that associates a nonnegative 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. 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 (see Proc. IEEE, vol.82, no.6, p.872, 1994).

A pair of real-valued sequences A=(a/sub 1/,a/sub 2/,...,a/sub N/) and B=(b/sub 1/,b/sub 2/,...,b/sub N/) is called complementary if the sum R(/spl middot/) of their autocorrelation functions R/sub A/(/spl middot/) and R/sub B/(/spl middot/) satisfies R(/spl tau/)=R/sub A/(/spl tau/)+R/sub B/(/spl tau/)=/spl Sigma//sub i=1//sup N$/ -/sup /spl tau//a/sub i/a/sub i+/spl tau//+/spl Sigma//sub j=1//sup N-/spl tau//b/sub j/b/sub j+/spl tau//=0, /spl forall//spl tau//spl ne/0. In this paper we introduce a new family of complementary pairs of sequences over the alphabet /spl alpha//sub 3/=+{1,-1,0}. The inclusion of zero in the alphabet, which may correspond to a pause in transmission, leads both to a better understanding of the conventional binary case, where the alphabet is /spl alpha//sub 2/={+1,-1}, and to new nontrivial constructions over the ternary alphabet /spl alpha//sub 3/. For every length N, we derive restrictions on the location of the zero elements and on the form of the member sequences of the pair. We also derive a bound on the minimum number of zeros necessary for the existence of a complementary pair of length N over /spl alpha//sub 3/. The bound is tight, as it is met by some of the proposed constructions, for infinitely many lengths.>