Patent ID: 7444326

Claim:
A method of indexing a query substring Q against a collection of data strings in a database D, the method comprising the steps of: a) preprocessing each string σ in database D to generate a plurality of overlapping q-grams of a predetermined length q, augmenting each q-gram with information indicating its position within string σ to form a tuple comprising the position information and the q-gram, and creating an index of a plurality of positional q-gram tuples; b) parsing the query substring Q into a plurality of overlapping positional q-grams of length q; c) searching each index in database D to retrieve potential matches between the query Q substring plurality of overlapping q-grams and the preprocessed database D plurality of overlapping q-grams, a potential match defined as having a predetermined number of matching overlapping q-grams; d) applying position-directed filtering to the potential matches retrieved in step c) to form a candidate set including only those potential matches with a majority of q-grams in the same position order as substring query Q; e) defining a predetermined maximum edit distance k between the query substring Q and database D; f) after applying the position-directed filtering, calculating the edit distance between each candidate substring and the query substring; and g) verifying the candidate set by removing from the candidate set each candidate substring having an edit distance greater than k.