Compression of strings with approximate repeats

We describe a model for strings of characters that is loosely based on the Lempel Ziv model with the addi-tion that a repeated substring can be an approximate match to the original substring; this is close to the situation of DNA, for example. Typically there are many explanations for a given string under the model, some optimal and many suboptimal. Rather than com-mit to one optimal explanation, we sum the probabili-ties over all explanations under the model because this gives the probability of the data under the model. The model has a small number of parameters and these can be estimated from the given string by an expectation-maximization (EM) algorithm. Each iteration of the EM algorithm takes O(n2) time and a few iterations are typically sufficient. O(n2) complexity is impracti-cal for strings of more than a few tens of thousands of characters and a faster approximation algorithm is also given. The model is further extended to include approximate reverse complementary repeats when an-alyzing DNA strings. Tests include the recovery of pa-rameter estimates from known sources and applications to real DNA strings