language: en

On the Collapse of the q-Gram Filtration

E. SUTINEN
University of Helsinki,
Finland
W. SZPANKOWSKI
Purdue University,
U.S.A.

Abstract In the approximate pattern matching problem, the text area to be searched for an occurrence of a pattern can be pruned by applying a filtration condition. A q-gram based filtration condition defines potential text areas in terms of pattern q-grams, i.e., strings of length q. A text area will be checked by an accurate method only if the set of the q-grams in the text area satisfies a certain condition. One hopes that the filtration limits the number of checks to a minimum, thus making the algorithm quite efficient. However, computer experiments show that the filtration method works fine for cases when the allowed error level k is relatively small compared to the pattern length, but loses its efficiency quite sharply with an increasing k. This is a phase transition phenomenon that is quite often observed in nature. In this paper, we present a theoretical explanation for this phenomenon which will excuse us to introduce advanced mathematical analysis based on certain languages, correlation polynomials, generating functions and complex analysis. It is our view that nothing can be more exciting and rewarding than finding a theoretical justification for an abrupt manifestation of nature.

Keywords: Algorithm Analysis, Approximate Pattern Matching.

1 Introduction