Patent Document ID: 7689588
Application ID: 11916605

Base Claim:
1. A method executed in a computer system for comparing the similarity of a target string to at least one string in a set of strings, the target string and each string in the set of strings being a sequence of symbols from an alphabet of symbols, the method comprising the steps of: (a) Generating a multi-level Trie associated with the set of strings, the Trie having a null level and a null node thereon, and a plurality of data levels having a plurality of data nodes thereon, each data node having a symbol of the alphabet associated therewith; (b) From the null node, traversing a plurality of levels of the Trie commencing with the first data level adjacent the null node, and thereafter descending level by level within the Trie; (c) For each data level of the Trie traversed, making a first selection of a set of data nodes from that level, which first selection step includes the steps of: i. In the case of the first data level of the Trie, selecting all of the data nodes in that level of the Trie; and ii. In the case of at least one other data levels of the Trie, for each such level A. Making a second selection of all of the children of the nodes of the first selection of the level immediately previously traversed; B. For each of the data nodes selected in step A, calculating a heuristic measurement between the sequence of symbols in the target string and the sequence formed by the symbols on the path from the null node to that selected data node; and C. For at least a first symbol represented, selecting a first cluster of nodes representing that first symbol that have the most optimal calculated heuristic measurement associated therewith, up to a bounded number of nodes and identifying the terminal nodes in the first cluster of nodes; (d) Continuing to traverse the Trie, level by level, repeating step (c) in respect of each level traversed, until step (c) has been completed on that level of the Trie for which there are no children of the selected nodes; and (e) In respect of each terminal node identified during the traversal of the plurality of levels of the Trie, comparing the calculated heuristic measurement associated therewith and reporting at least one string from the set of strings associated with the optimal calculated heuristic measurement.

---

Claim 8:
8. A method according to claim 1 wherein for at least a second symbol, selecting a second cluster of nodes presenting that second symbol that has the most optimal calculated heuristic measurement associated therein, up to a bounded number of nodes, the bound for that number being different from the bound for the number for the first cluster.