Technique for comparing a string to large sets of strings
US8280723B1 · kind B1 · utility
Assignee
Inventor
Key dates
| Filing date | Jan 29, 2009 |
| Grant date | Oct 2, 2012 |
| Priority date | — |
| Expiry date | Aug 5, 2031 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F40/205
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
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.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.