ON THE PERFORMANCE OF DATA-COMPRESSION ALGORITHMS BASED UPON STRING-MATCHING

Lossless and lossy data compression algorithms based on string matchin g are considered. In the lossless case, a result of Wyner and Ziv is e xtended, In the lossy case, a data compression algorithm based on appr oximate string matching is analyzed in the following two frameworks: 1 ) the database and the source together form a Markov chain of finite o rder; 2) the database and the source are independent with the database coming from a Markov model and the source from a general stationary, ergodic model. In either framework, it is shown that the resulting com pression rate converges with probability one to a quantity computable as the infimum of an information-theoretic functional over a set of au xiliary random variables; the quantity is strictly greater than the ra te distortion function of the source except in some symmetric cases. I n particular, this result implies that the lossy algorithm proposed by Steinberg and Gutman is not optimal, even for memoryless or Markov so urces.