Hierarchical string matching using multi-path dynamic programming

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.

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.