Hierarchical string matching using multi-path dynamic programming

• US 6,556,984 B1
• Filed: 01/19/1999
• Issued: 04/29/2003
• Est. Priority Date: 01/19/1999
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Zien, Jason Yeong
• Primary Examiner(s): Feild; Joseph H.
• Assistant Examiner(s): DESAI, RACHNA SINGH
• Application Number:
  US09/233,995
• Time in Patent Office: 1,561 Days
• Field of Search: 707/501.1,3,6,10,2
• US Class Current: 1/1
• CPC Class Codes: G06F 16/955 using information identifiers, e.g. uniform resource locators [URL]
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

A method, system, and article of manufacture for generating a list of candidate objects for a requested object. An identifier for the requested object is accepted, wherein the identifier comprises a target string. A list of candidate objects is generated when the requested object cannot be found by performing a hierarchical string match for the target string against a set of source strings using multi-path dynamic programming, wherein the set of source strings represent a set of objects from which the list of candidate objects is generated.

Claims

1. A method of generating a test of candidate objects for a requested object, comprising:

(a) accepting an identifier for the requested object, wherein the identifier comprises a target string;

(b) generating a list of candidate objects based on a cost function by performing a hierarchical stag match for the target string against a set of source strings using multi-path dynamic programming, wherein;

(i) the set of source strings represent a set of objects from which the list of candidate objects is generated; and

(ii) a hierarchy is utilized to minimize computation of the cost function by reusing a previous partially-computed cost computation solution as a starting point of another cost computation solution.

2. The method of claim 1, wherein the generating step is performed when the requested object cannot be found.

3. The method of claim 1, wherein the target string and the source strings each represents a Uniform Resource Locator.

4. The method of claim 1, further comprising limiting the list of candidate objects.

5. The method of claim 1, wherein the list of candidate objects comprises a list of most likely matches.

6. The method of claim 1, wherein the cost function uses a minimum-cost string edit-distance to generate the list of candidate objects for the target string from the set of source strings.

7. The method of claim 6, wherein the minimum-cost string edit-distance finds one or more strings from the set of strings that are closer matches to the target string.

8. The method of claim 6, wherein the minimum-cost string edit-distance comprises a cost of transforming the target string into one of the source strings.

9. The method of claim 6, wherein the source strings are represented in a hierarchical tree structure.

10. The method of claim 9, further comprising re-using previous partially-computed solutions due to an overlap among source strings in the set of source strings represented in the hierarchical tree structure.

11. The method of claim 9, wherein each of the source strings comprise a path in the hierarchical tree structure.

12. The method of claim 11, wherein the path in the hierarchical tree structure comprises a plurality of concatenated nodes that are visited in a traversal from a top-level node to a target node.

13. The method of claim 9, further comprising performing a depth first search traversal of the hierarchical tree structure to generate an ordering of the source strings.

14. The method of claim 13, wherein the depth first search traversal reuses partial computations of the hierarchical tree structure to generate the ordering of the source strings.

15. The method of claim 13, wherein the depth first search traversal reuses partial computations of the edit-distance cost for a shared portion of the path traversed in the hierarchical tree structure.

16. The method of claim 13, further comprising iterating through all the source strings being compared to the target string by performing a depth first search traversal of the hierarchical tree structure using pre-order node visitation.

17. The method of claim 9, wherein the list of candidate objects list is generated using the cost function based on the differences between the target string and the set of source strings.

18. The method of claim 17, further comprising computing cost comparisons using a partial result from a first comparison of the target string to a first one of the source strings as a starting point of a second comparison of the target string to a second one of the source strings.

19. A system for generating a list of candidate objects for a requested object comprising:

(a) a computer;

(b) means, performed by the computer, for accepting an identifier for the requested object, wherein the identifier comprises a target string;

(c) means, performed by the computer, for generating a list of candidate objects based on a cost function when the requested object cannot be found by performing a hierarchical string match for the target string against a set of source strings using multi-path dynamic programming, wherein;

(i) the set of source strings represent a set of objects from which the list of candidate objects is generated; and

(ii) a hierarchy is utilized to minimize computation of the cost function by reusing a previous partially-computed cost computation solution as a staring point of another cost computation solution.

20. The system of claim 19, wherein the means for generating is performed when the requested object cannot be found.

21. The system of claim 19, wherein the target string and the source strings each represents a Uniform Resource Locator.

22. The system of claim 19, further comprising means for limiting the list of candidate objects.

23. The system of claim 19, wherein the list of candidate objects comprises a list of most likely matches.

24. The system of claim 19, wherein the cost function uses a minimum-cost string edit-distance to generate the list of candidate objects for the target string from the set of source strings.

25. The system of claim 24, wherein the minimum-cost string edit-distance finds one or more strings from the set of strings that are closest matches to the target string.

26. The system of claim 24, wherein the minimum-cost string edit-distance comprises a cost of transforming the target string into one of the source strings.

27. The system of claim 24, wherein the source strings are represented in a hierarchical tree structure.

28. The system of claim 27, further comprising means for re-using precious partially-computed solutions due to an overlap among source strings in the set of source strings represented in the hierarchical tree structure.

29. The system of claim 27, wherein each of the source strings comprise a path in the hierarchical tree structure.

30. The system of claim 29, wherein the path in the hierarchical tree structure comprises a plurality of concatenated nodes that are visited in a traversal from a top-level node to a target node.

31. The system of claim 27, further comprising means for performing a depth first search traversal of the hierarchical tree structure to generate an ordering of the source strings.

32. The system of claim 31, wherein the depth first search traversal reuses partial computations of the hierarchical tree structure to generate the ordering of the source strings.

33. The system of claim 31, wherein the depth first search traversal reuses partial computations of the edit-distance cost for a shared portion of the path traversed in the hierarchical tree structure.

34. The system of claim 31, further comprising means for iterating through all the source strings being compared to the target string by performing a depth first search traversal of the hierarchical tree structure using pre-order node visitation.

35. The system of claim 27, wherein the list of candidate objects list is generated using the cost function based on the differences between the target string and the set of source strings.

36. The system of claim 35, further comprising means for computing cost comparisons using a partial result from a first comparison of the target string to a first one of the source strings as a starting point of a second comparison of the target string to a second one of the source strings.

37. An article of manufacture embodying logic for performing a method of generating a list of candidate objects for a requested object, the method comprising:

(a) accepting an identifier for the requested object, wherein the identifier comprises a target string;

(b) generating a list of candidate objects based on a cost function when the requested object cannot be found by performing a hierarchical string match for the target string against a set of source strings using multi-path dynamic programing, wherein;

(i) the set of source strings represent a set of objects from which the list of candidate objects is generated; and

(ii) a hierarchy is utilized to minimize computation of the cost function by reusing a previous partially-computed cost computation solution as a starting point of another cost computation solution.

38. The system of claim 37, wherein the generating step is performed when the requested object cannot be found.

39. The system of claim 37, wherein the target string and the source strings each represents a Uniform Resource Locator.

40. The system of claim 37, further comprising limiting the list of candidate objects.

41. The system of claim 37, wherein the list of candidate objects comprises a list of most likely matches.

42. The system of claim 37, wherein the cost function uses a minimum-cost string edit-distance to generate the list of candidate objects for the target string from the set of source strings.

43. The system of claim 42, wherein the minimum-cost string edit-distance finds one or more strings from the set of strings that are closest matches to the target string.

44. The system of claim 42, wherein the minimum-cost string edit-distance comprises a cost of transforming the target string into one of the source strings.

45. The system of claim 42, wherein the source strings are represented in a hierarchical tree structure.

46. The system of claim 45, further comprising re-using previous partially-computed solutions due to an overlap among source strings in the sec of source strings represented in the hierarchical tree structure.

47. The system of claim 45, wherein each of the source strings comprise a path in the hierarchical tree structure.

48. The system of claim 47, wherein the path in the hierarchical tree structure comprises a plurality of concatenated nodes that are visited in a traversal from a top-level node to a target node.

49. The system of claim 45, further comprising performing a depth first search traversal of the hierarchical tree structure to generate an ordering of the source strings.

50. The system of claim 49, wherein the depth first search traversal reuses partial computations of the hierarchical tree structure to generate the ordering of the source strings.

51. The system of claim 49, wherein the depth first search traversal reuses partial computations of the edit-distance cost for a shared portion of the path traversed in the hierarchical tree structure.

52. The system of claim 49, further comprising iterating through all the source strings being compared to the target string by performing a depth first search traversal of the hierarchical tree structure using pre-order node visitation.

53. The system of claim 45, wherein the list of candidate objects list is generated using the cost function based on the differences between the target so and the set of source strings.

54. The system of claim 53, further comprising computing cost comparisons using a partial result from a first comparison of the target string to a first one of the source strings as a starting point of a second comparison of the target string to a second one of the source strings.