Patent ID: 7689588
Filing Date: 2010-03-30
Classification: G06F,Y10S

Abstract:
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: (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.