On The Collapse of the q-Gram Filtration
E. Stuinen, Wojciech Szpankowski · Purdue e-Pubs (Purdue University System) · 1998
AbstraclIn the approximate pattern malching problem, the lext area to be searl;;bc(] for an occurrence ora paltern can be pruned by applying a filtration condilion.A q-gram based filtration condition defines potcntiallexl areas in terms of pauem q-grams, i.e., strings of length q.A [ext area will be checked by an accurate method only if the set of the q-grams in the lext area satisfies a certain condition.One hopes thai 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 eITor level k is relatively small comparctllo the pattern length, but loses its efficiency quite sharply with an increasing k.This is a phase transition phenomenon Ihat is quite ofLen observed in nature.In lhis paper, we present 0. theorelical explanation for this phenomenon which will excuse us to introduce advanced malhemalical ano.lysis based on certain languages.correlalion polynomials, gencr.ltingfunctions and complex analysis.II is our view that nOlhing can be more exciting and rewarding than finding a thcoreticaljustification for an abrupt manifestation of nature.