Patent Document ID: 20040220920
Application ID: 10775576
Patent Status: 0

Claim One:
1. A method for identifying among a list of texts those that have edit distance from a search string that is less than a threshold, said method comprising: beginning with a first text from a list of texts as a computation text; providing a search string and a threshold value; performing a column-by-column grid computation of edit distance between the search string and the computation text, stopping early if a column minimum value is at least the threshold; if the edit distance is computed and is below the threshold, then reporting that the computation text is close to the search string in edit distance; if all columns are computed, then setting the next computation text to the next text in the list after the present computation text; if not all columns are computed, then setting the next computation text to the next text in the list after the present computation text that does not share with the present computation text the prefix corresponding to the columns up to and including the column with minimum value at least the threshold; applying the same procedure as for the first computation text, but re-using columns corresponding to any prefix shared with the present computation text; continuing until the text list is exhausted.