1. An improvement in an indexing method for efficient approximate string search of a query string s against a collection of data strings S corresponding to a gram dictionary D in a computer system comprising: preprocessing the dictionary D into a plurality of grams of varying length between q min and q max ; starting from a current position in the query string s, searching for the longest substring that matches a gram in the dictionary D, if no such gram exists in the dictionary D, then materializing a substring of length g min starting from the current position; checking if the found or materialized substring is a positional substring already found in the query string s, and if so, then not producing a positional gram corresponding to the found or materialized substring, otherwise producing a positional gram corresponding to the found or materialized substring; and indexing the current position by one to the right in the query string and repeating the searching and checking until the current position in the query string S is greater than |s|−q min +1, where |s| is the length of query string s, so that a gram index list for query string s having variable gram length is generated denoted as the set of positional grams VG(s, D, q min , q max ).
1. An improvement in an indexing method for efficient approximate string search of a query string s against a collection of data strings S corresponding to a gram dictionary D in a computer system comprising: preprocessing the dictionary D into a plurality of grams of varying length between q min and q max ; starting from a current position in the query string s, searching for the longest substring that matches a gram in the dictionary D, if no such gram exists in the dictionary D, then materializing a substring of length g min starting from the current position; checking if the found or materialized substring is a positional substring already found in the query string s, and if so, then not producing a positional gram corresponding to the found or materialized substring, otherwise producing a positional gram corresponding to the found or materialized substring; and indexing the current position by one to the right in the query string and repeating the searching and checking until the current position in the query string S is greater than |s|−q min +1, where |s| is the length of query string s, so that a gram index list for query string s having variable gram length is generated denoted as the set of positional grams VG(s, D, q min , q max ). 2. The improvement of claim 1 where preprocessing the dictionary D into a plurality of grams of varying length between q min and q max comprises: generating a frequency trie of q max -grams for the strings for the dictionary D; collecting gram frequencies by counting on a trie without generating the shorter grams for the dictionary D, except for those grams at the end of a string; and selecting high quality grams.