IP Library › Granted Patent US 7,584,173

Granted Patent B2

US 7,584,173 · App. 10/775,576 · Granted Sep 1, 2009

Edit distance string search

View Patent ↗

Loading inventors, assignments & file history…

Monitor This Case

Get email alerts when status or documents change.

Order Certified Copies

Most orders are placed with the USPTO same day — all within 24 business hours.

Order via The Patent Place →

Pre-filled with this patent's details

Quick Facts

Patent No.: US 7,584,173
App. No.: 10/775,576
Granted: Sep 1, 2009
Kind: B2

External Links

USPTO Patent Center↗ Full Patent PDF↗

Abstract

A process determines for a search string which, if any, of the strings in a text list have edit distance from the search string less than a threshold. The process uses dynamic programming on a grid with search string characters corresponding to rows and text characters corresponding to columns. For each text string, computation proceeds by columns. If successive text strings share a prefix, then the columns corresponding to the prefix are re-used. If the minimum value in a column is at least the threshold, then the prefix corresponding to that and previous columns causes edit distance to be at least the threshold. So the computation for the present text is abandoned, and computations for any other texts that share the prefix are avoided.

Claims (200)

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.

2. The method of claim 1 , further comprising:

ordering the text list in a sequence to place text with shared prefixes adjacent to one another in the sequence.

3. The method of claim 1 , further comprising:

prior to step (b), sorting the texts in the list in lexicographical order.

4. The method of claim 1 , wherein:

computing comprises using dynamic programming to perform the computing.

5. 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 columns of the grid correspond to characters of the computation text and rows of the grid correspond to characters of the search string;

(d) stopping the computing in response to computing a column whose minimum value of edit distance is at least 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;

(i) in response to step (h) returning to step (c);

(k) continuing to perform steps (c) through (j) until step (g) or step (h) reaches an end of the text list;

(l) making an alternative list of texts to an original said list of texts in which each occurrence in the texts of a character in a set of characters is replaced by a determined character in the set;

(m) in response to the search string lacking all characters in said set of characters, using the alternative list of texts rather than the list of texts to identify those texts whose edit distance from the search string is less than the threshold value; and

(n) in response to the search string not lacking all characters in said set, using the list of texts to identify those texts whose edit distance from the search string is less than the threshold value.

6. The method of claim 5 , further comprising:

ordering the text list in a sequence to place texts with shared prefixes adjacent one to another in the sequence.

7. The method of claim 5 , further comprising:

prior to step (b), sorting the texts in the list in lexicographical order.

8. The method of claim 5 , wherein:

computing comprises

using dynamic programming to perform the computing.

9. 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;

re-using a column of the grid of a previous computation text for an individual column of the grid of the present computation text, in response to the present computation text not being a first said selected computation text and a preceding column of the grid of the present computation text having same edit distance values as a preceding column of the grid of the previous computation text, and at least one of the following conditions being true:

a character corresponding to an individual column of the grid of the present computation text and the character corresponding to the column of the previous computation text are both a same character and not a part of a prefix shared by the previous computation text and the present computation text,

the search string lacks the character corresponding to the individual column of the grid of the present computation text and the character corresponding to the column of the previous computation text; and

otherwise computing the individual column of the grid of the present computation text;

(d) stopping the computing in response to computing a column whose minimum value of edit distance is at least 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;

(i) in response to step (h) returning to step (c);

(k) continuing to perform steps (c) through (j) until step (g) or step (h) reaches an end of the text list.

10. The method of claim 9 , further comprising:

ordering the text list in a sequence to place texts with shared prefixes adjacent one to another in the sequence.

11. The method of claim 9 , further comprising:

prior to step (b), sorting the texts in the list in lexicographical order.

12. The method of claim 9 , wherein:

computing comprises

using dynamic programming to perform the computing.

13. A system for identifying, in a list of texts, texts whose edit distance from a search string is less than a threshold value, said system comprising:

a computer operable to

(a) obtain the search string and the threshold value;

(b) select a first text from the list of texts as a present computation text;

(c) compute, column-by-column, a grid of edit distance values between the search string and the present computation text;

wherein the computer is operable at step (c) to:

after an individual column is computed, identify 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 compute 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, compute 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, compute 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, compute 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) stop 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 the a computed edit distance from the present computation text to the search string being below the threshold value, generate 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, generate 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, select a next text, in the list after the present computation text, as the present computation text;

(h) in response to stopping the computing, select 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);

(k) continue to perform steps (c) through (j) until step (g) or step (h) reaches an end of the text list.

14. The system of claim 13 , wherein the computer is operable to:

order the text list in a sequence to place texts with shared prefixed adjacent one to another in the sequence.

15. The system of claim 13 , wherein the computer is further operable to:

prior to step (b), sort the texts in the list in lexicographical order.

16. The system of claim 13 , wherein the computer is adapted to use dynamic programming to comput the grid.

17. A system for identifying, in a list of texts, texts whose edit distance from a search string is less than a threshold value, said system comprising:

a computer operable to

(a) obtain the search string and the threshold value;

(b) select a first text from the list of texts as a present computation text;

(c) compute, column-by-column, a grid of edit distance values between the search string and the present computation text, wherein the columns of the grid correspond to characters of the computation text and rows of the grid correspond to characters of the search string;

(d) stop 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, generate 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, generate 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, select a next text, in the list after the present computation text, as the present computation text;

(i) in response to step (h) returning to step (c);

(k) continue to perform steps (c) through (j) until step (g) or step (h) reaches an end of the text list;

(l) make an alternative list of texts to an original said list of texts in which each occurrence in the texts of a character in a set of characters is replaced by a determined character in the set;

(m) in response to the search string lacking all characters in said set of characters, use the alternative list of texts rather than the list of texts to identify those texts whose edit distance from the search string is less than the threshold value; and

(n) in response to the search string not lacking all characters in said set, use the original list of texts to identify those texts whose edit distance from the search string is less than the threshold value.

18. The system of claim 17 , wherein the computer is operable to:

order the text list in a sequence to place texts with shared prefixes adjacent one to another in the sequence.

19. The system of claim 17 , wherein the computer is further operable to:

prior to step (b), sort the texts in the list in lexicographical order.

20. The system of claim 17 , wherein:

the computer is adapted to use dynamic programming to compute the grid.

21. A system for identifying, in a list of texts, texts whose edit distance from a search string is less than a threshold value, said system comprising:

a computer operable to

(a) obtain the search string and the threshold value;

(b) select a first text from the list of texts as a present computation text;

re-use a column of the grid of a previous computation text for an individual column of the grid of the present computation text, in response to the present computation text not being a first said selected computation text and a preceding column of the grid of the present computation text having same edit distance values as a preceding column of the grid of the previous computation text, and at least one of the following conditions being true:

otherwise compute the individual column of the grid of the present computation text;

(d) stop the computing in response to computing a column whose minimum value of edit distance is at least 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, generate 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, select a next text, in the list after the present computation text, as the present computation text;

(i) in response to step (h) returning to step (c);

(k) continue to perform steps (c) through (j) until step (g) or step (h) reaches an end of the text list.

22. The system of claim 21 , wherein the computer is further operable to:

order the text list in a sequence to place texts with shared prefixes adjacent one to another in the sequence.

23. The system of claim 21 , wherein the computer is further operable to:

prior to step (b), sort the texts in the list in lexicographical order.

24. The system of claim 21 , wherein:

the computer is adapted to use dynamic programming to compute the grid.

25. A computer-readable storage medium containing instructions which, when executed by a computer, cause the computer to identify, in a list of texts, texts whose edit distance from a search string is less than a threshold value, by performing steps comprising:

(a) obtaining the search string and the threshold value;

(b) selecting a first text from the list of texts as a present computation text;

(c) computing, column-by-column, a grid of edit distance values between the search string and the present computation text;

wherein the instructions cause the computer to perform the computing by further performing steps comprising:

in a next column, not 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 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 the 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 the 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 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 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 a next text, in the list after the present computation text, as the present computation text;

(h) in response to stopping the computing, selecting 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);

(k) continuing to perform steps (c) through U) until step (g) or step (h) reaches an end of the text list.

26. The medium of claim 25 , further containing instructions which cause the computer to perform:

ordering the text list in a sequence to place texts with shared prefixes adjacent to one another in the sequence.

27. The medium of claim 25 , further containing instructions which cause the computer to perform: prior to step (b), sorting the texts in the list in lexicographical order.

28. The medium of claim 25 , wherein the instructions cause the computer to perform the step of computing by using dynamic programming.

29. A computer-readable storage medium containing instructions which, when executed by a computer, cause the computer to identify, in a list of texts, these texts whose edit distance from a search string is less than a threshold value, by performing steps comprising:

(a) obtaining the search string and the threshold value;

(b) selecting a first text from the list of texts as a present computation text;

(c) computing, column-by-column, a grid of edit distance values between the search string and the present computation text, wherein the columns of the grid correspond to characters of the computation text and rows of the grid correspond to characters of the search string;

(d) stopping the computing in response to computing a column whose minimum value of edit distance is at least 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 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 a next text, in the list after the present computation text, as the present computation text;

(i) in response to step (h) returning to step (c);

(k) continuing to perform steps (c) through (j) until step (g) or step (h) reaches an end of the text list;

(l) making an alternative list of texts to an original said list of texts in which each occurrence in the texts of a character in a set of characters is replaced by a determined character in the set;

(m) in response to the search string lacing all characters in said set of characters, using the alternative list of texts rather than the list of texts to identify those texts whose edit distance from the search string is less than the threshold value; and

(n) in response to the search string not lacking all characters in said set, using the original list of texts to identify those texts whose edit distance form the search string is less than the threshold value.

30. The medium of claim 29 , further containing instructions which cause the computer to perform:

ordering the text list in a sequence to place texts with shared prefixes adjacent one to another in the sequence.

31. The medium of claim 29 , further containing instructions which cause the computer to perform:

prior to step (b), sorting the texts in the list in lexicographical order.

32. The medium of claim 29 , wherein the instructions cause the computer to perform the step of computing by using dynamic programming.

33. A computer-readable storage medium containing instructions which, when executed by a computer, cause the computer to identify, in a list of texts, texts whose edit distance from a search string is less than a threshold value, by performing steps comprising:

(a) obtaining the search string and the threshold value;

(b) selecting a first text from the list of texts as a present computation text;

otherwise computing the individual column of the grid of the present computation text;

(d) stopping the computing in response to computing a column whose minimum value of edit distance is at least 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 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 a next text, in the list after the present computation text, as the present computation text;

(h) in response to stopping the computing, selecting a next text, in the list after the present computation text, as the present computation text, wherein the next text that 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);

(k) continuing to perform steps (c) through (j) until step (g) or step (h) reaches an end of the text list.

34. The medium of claim 33 , further containing instructions which cause the computer to perform:

ordering the text list in a sequence to place texts with shared prefixes adjacent one to another in the sequence.

35. The medium of claim 33 , further containing instructions which cause the computer to perform:

prior to step (b), sorting the texts in the list in lexicographical order.

36. The medium of claim 33 , wherein the instructions cause the computer to perform the step of computing by using dynamic programming.

Assignments (15)

RELEASE OF SECURITY INTEREST IN PATENTS (REEL/FRAME 53955/0436) Recorded May 18, 2023

From: WILMINGTON TRUST, NATIONAL ASSOCIATION, AS NOTES COLLATERAL AGENT

To: AVAYA MANAGEMENT L.P.; AVAYA INC.; INTELLISIST, INC.; AVAYA INTEGRATED CABINET SOLUTIONS LLC

Reel/Frame 063705/0023 →

RELEASE OF SECURITY INTEREST IN PATENTS (REEL/FRAME 045034/0001) Recorded May 18, 2023

From: GOLDMAN SACHS BANK USA., AS COLLATERAL AGENT

To: ZANG, INC. (FORMER NAME OF AVAYA CLOUD INC.); AVAYA INC.; INTELLISIST, INC.; AVAYA INTEGRATED CABINET SOLUTIONS LLC; OCTEL COMMUNICATIONS LLC; VPNET TECHNOLOGIES, INC.; HYPERQUALITY, INC.; HYPERQUALITY II, LLC; CAAS TECHNOLOGIES, LLC; AVAYA MANAGEMENT L.P.

Reel/Frame 063779/0622 →

RELEASE OF SECURITY INTEREST IN PATENTS AT REEL 45124/FRAME 0026 Recorded Apr 26, 2023

From: CITIBANK, N.A., AS COLLATERAL AGENT

To: AVAYA HOLDINGS CORP.; AVAYA INC.; AVAYA MANAGEMENT L.P.; AVAYA INTEGRATED CABINET SOLUTIONS LLC

Reel/Frame 063457/0001 →

SECURITY INTEREST Recorded Sep 25, 2020

From: AVAYA INC.; AVAYA MANAGEMENT L.P.; INTELLISIST, INC.; AVAYA INTEGRATED CABINET SOLUTIONS LLC

To: WILMINGTON TRUST, NATIONAL ASSOCIATION

Reel/Frame 053955/0436 →

SECURITY INTEREST Recorded Jan 23, 2018

From: AVAYA INC.; AVAYA INTEGRATED CABINET SOLUTIONS LLC; OCTEL COMMUNICATIONS LLC; VPNET TECHNOLOGIES, INC.; ZANG, INC.

To: CITIBANK, N.A., AS COLLATERAL AGENT

Reel/Frame 045124/0026 →

SECURITY INTEREST Recorded Jan 10, 2018

From: AVAYA INC.; AVAYA INTEGRATED CABINET SOLUTIONS LLC; OCTEL COMMUNICATIONS LLC; VPNET TECHNOLOGIES, INC.; ZANG, INC.

To: GOLDMAN SACHS BANK USA, AS COLLATERAL AGENT

Reel/Frame 045034/0001 →

BANKRUPTCY COURT ORDER RELEASING ALL LIENS INCLUDING THE SECURITY INTEREST RECORDED AT REEL/FRAME 030083/0639 Recorded Dec 15, 2017

From: THE BANK OF NEW YORK MELLON TRUST COMPANY, N.A.

To: AVAYA INC.

Reel/Frame 045012/0666 →

BANKRUPTCY COURT ORDER RELEASING ALL LIENS INCLUDING THE SECURITY INTEREST RECORDED AT REEL/FRAME 041576/0001 Recorded Dec 15, 2017

From: CITIBANK, N.A.

To: AVAYA INC.; AVAYA INTEGRATED CABINET SOLUTIONS INC.; OCTEL COMMUNICATIONS LLC (FORMERLY KNOWN AS OCTEL COMMUNICATIONS CORPORATION); VPNET TECHNOLOGIES, INC.

Reel/Frame 044893/0531 →

BANKRUPTCY COURT ORDER RELEASING ALL LIENS INCLUDING THE SECURITY INTEREST RECORDED AT REEL/FRAME 025863/0535 Recorded Dec 15, 2017

From: THE BANK OF NEW YORK MELLON TRUST, NA

To: AVAYA INC.

Reel/Frame 044892/0001 →

SECURITY INTEREST Recorded Jan 27, 2017

From: AVAYA INC.; AVAYA INTEGRATED CABINET SOLUTIONS INC.; OCTEL COMMUNICATIONS CORPORATION; VPNET TECHNOLOGIES, INC.

To: CITIBANK, N.A., AS ADMINISTRATIVE AGENT

Reel/Frame 041576/0001 →

SECURITY AGREEMENT Recorded Mar 13, 2013

From: AVAYA, INC.

To: BANK OF NEW YORK MELLON TRUST COMPANY, N.A., THE