Indexing Text with Approximate -grams.pdfVIP

Indexing Text with Approximate q-grams Gonzalo Navarro a,1, Erkki Sutinen b and Jorma Tarhio c aDepartment of Computer Science, University of Chile. gnavarro@dcc.uchile.cl b Department of Computer Science, University of Joensuu. sutinen@cs.joensuu.fi c Department of Computer Science and Engineering, Helsinki University of Technology. tarhio@cs.hut.fi Abstract We present a new index for approximate string matching. The index collects text q-samples, that is, disjoint text substrings of length q , at fixed intervals and stores their positions. At search time, part of the text is filtered out by noticing that any occurrence of the pattern must be reflected in the presence of some text q-samples that match approximately inside the pattern. Hence the index points out the text areas that could contain occurrences and must be verified. The index parameters permit load balancing between filtering and verification work, and provide a com- promise between the space requirement of the index and the error level for which the filtration is still efficient. We show experimentally that the index is competitive against others that take more space, being in fact the fastest choice for intermediate error levels, an area where no current index is useful. Key words: Approximate string matching, text databases, q-gram indices. 1 Introduction and Related Work Approximate string matching is a recurrent problem in many branches of computer science, with applications to text searching, computational biology, pattern recognition, signal processing, etc. The problem is: Given a long text T1...n of length n, and a (comparatively short) pattern P1...m of length m, both sequences over an alphabet Σ of size σ , retrieve all the text substrings (or “occurr