Technique for comparing a string to large sets of strings

摘要

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.