Hierarchical string matching using multi-path dynamic programming
First Claim
Patent Images
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.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
54 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18)
-
-
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. - View Dependent Claims (20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36)
-
-
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. - View Dependent Claims (38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54)
-
Specification