Technique for comparing a string to large sets of strings
AssigneeIntuit Inc.
InventorWilliam T. Laaser
Life of this patent
Estimating the term…
Loading patent…
AssigneeIntuit Inc.
InventorWilliam T. Laaser
Estimating the term…
A comparison technique for efficiently comparing an input string to a set of strings is described. This set of strings may be represented in a tree structure 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. During the comparison technique, labels may be assigned to a given node in the tree structure based at least in part on comparisons between a given character in the input string and a character associated with the given node. These labels may include a position of the given character in the input string, and a cumulative error between the characters in a string that are associated with a branch in the tree structure and the characters in the input string that have been processed. Based at least in part on these labels, an actual string, which corresponds to the input string, may be identified.
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:
A computer-program product for use in conjunction with a computer system, the computer-program product comprising a non-transitory computer-readable storage medium and a computer-program mechanism embedded therein for 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 computer-program mechanism including:
A computer system, comprising:
Dependencies are inferred from the claim text.