Edit distance string search
US7584173B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Feb 9, 2004 |
| Grant date | Sep 1, 2009 |
| Priority date | — |
| Expiry date | Jan 21, 2026 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F2207/025
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A process determines for a search string which, if any, of the strings in a text list have edit distance from the search string less than a threshold. The process uses dynamic programming on a grid with search string characters corresponding to rows and text characters corresponding to columns. For each text string, computation proceeds by columns. If successive text strings share a prefix, then the columns corresponding to the prefix are re-used. If the minimum value in a column is at least the threshold, then the prefix corresponding to that and previous columns causes edit distance to be at least the threshold. So the computation for the present text is abandoned, and computations for any other texts that share the prefix are avoided.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.