VLSI circuit structure for determining the edit distance between strings
US5553272A · kind A · utility
Assignee
Inventors
Key dates
| Filing date | Sep 30, 1994 |
| Grant date | Sep 3, 1996 |
| Priority date | — |
| Expiry date | Sep 30, 2014 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06V10/94
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
The edit distance between two strings a.sub.1, . . . , a.sub.m and b.sub.1, . . . , b.sub.n is the minimum cost s of a sequence of editing operations (insertions, deletions and substitutions) that convert one string into the other. This invention provides VLSI circuit structure for computing the edit distance between two strings over a given alphabet. The circuit structure can perform approximate string matching for variable edit costs. More importantly, the circuit structure does not place any constraint on the lengths of the strings that can be compared. It makes use of simple basic cells and requires regular nearest-neighbor communication, which makes it suitable for VLSI implementation.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.