A suboptimal lossy data compression based on approximate pattern matching

A practical suboptinal (variable source coding) algorithm for lossy data compression is presented, This scheme is based on approximate string matching, and it naturally extends the lossless Lempel-Ziv data compression scheme, Among others we consider the typical length of an approximately repeated pattern within the first n positions of a stationary mixing sequence where D percent of mismatches is allowed, We prove that there exists a constant r(0)(D) such that the length of such an approximately repeated pattern converges in probability to 1/r(0)(D) log n (pr.) but it almost surely oscillates between 1/r(-infinity)(D) log n and 2/r(1)(D) log n, where r(-infinity)(D) > r(0)(D) > r(1)(D)/2 are some constants, These constants are natural generalizations of Renyi entropies to the lossy environment. More importantly, we show that the compression ratio of a lossy data compression scheme based on such an approximate pattern matching is asymptotically equal to ro(D), We also establish the asymptotic behavior of the so-called approximate waiting time N-l which is defined as the time until a pattern of length l repeats approximately for the first time. We prove that log N-l/l --> r(0)(D) (pr.) as l --> infinity. In general, r(0)(D) > R(D) where R(D) is the rate-distortion function, Thus for stationary mixing sequences we settle in the negative the problem recently investigated by Steinberg and Gutman by showing that a lossy extension of the Wyner-Ziv scheme cannot be optimal.