Patent ID: 7584173
Filing Date: 2009-09-01
Classification: G06F,Y10S

Abstract:
1. A computer-implemented method for identifying, in a list of texts, texts whose edit distance from a search string is less than a threshold value, said method comprising: (a) obtaining by a computer the search string and the threshold value; (b) selecting by the computer a first text from the list of texts as a present computation text; (c) computing by the computer, column-by-column, a grid of edit distance values between the search string and the present computation text, wherein the computing further comprises the steps of: after an individual column is computed, identifying a range of rows of the grid extending from a first row that includes a cell of the individual column that has an edit distance value lower than the threshold value to a last row that includes a cell of the individual column that has an edit distance value lower than the threshold value; in a next column, not computing the edit distance values of cells in rows of the grid that are below the range, in response to a border cell of the next column having an edit distance value at least equal to the threshold value; in the next column, computing the edit distance values of the cells in rows of the grid that are below the range, in response to a border cell of the next column having an edit distance value lower than the threshold value; in the next column, computing the edit distance values of the cells in rows of the grid that are in the range and one higher; and in the next column, computing the edit distance value of each of the individual cells in rows of the grid that are above the range, based only on the edit distance value of a cell that is below each individual cell, only until a cell with an edit distance value at least equal to the threshold value is computed; (d) stopping the computing in response to computing a column whose minimum value of edit distance is at least the threshold value; (e) in response to completing the computing and a computed edit distance from the present computation text to the search string being below the threshold value, generating by the computer an indication that the edit distance of the present computation text from the search string is less than the threshold value; (f) in response to either stopping the computing, or completing the computing and the edit distance from the present computation text to the search string not being below the threshold value, generating by the computer an indication that the edit distance of the present computation text from the search string is not less than the threshold value; (g) in response to completing the computing, selecting by the computer a next text, in the list after the present computation text, as the present computation text; (h) in response to stopping the computing, selecting by the computer a next text, in the list after the present computation text, as the present computation text, wherein the next text does not share with the present computation text a prefix corresponding to columns of the grid up to and including the column whose minimum value of edit distance is at least the threshold value; (i) in response to step (h) returning to step (c); (j) in response to step (g), returning to step (c), but re-using in step (c) columns of the grid computed for previous said computation text that correspond to a prefix shared by the previous computation text and the present computation text; and (k) continuing to perform steps (c) through (j) until step (g) or step (h) reaches an end of the text list.