Patent ID: 8280723
Filing Date: 2012-10-02
Classification: G06F

Abstract:
1. A method comparing an input string against a set of strings in a dictionary, wherein the dictionary is arranged in a tree structure in which the set of strings are represented as paths from a root of the tree structure to leaves of the tree structure, and strings in the set of strings that share common substrings share nodes in the tree structure, the method comprising: comparing a first input character in the input string to a null character associated with a first node in a first level in the tree structure; generating one or more first labels associated with the first node, wherein a given first label includes a first position in the input string, and a first cumulative error metric between the first input character and the null character; for a given character associated with a second node in a second level in the tree structure, which is in a given branch of the tree structure that depends from the first level, performing the operations of: repeating the operations of comparing, generating and pruning for the remaining nodes in the second level in one or more branches; and continuing to repeat the operations of comparing, generating and pruning for additional nodes in the one or more branches that depend from the nodes in the second level until a termination condition occurs.