VLSI circuit structure for determining the edit distance between

Boots – shoes – and leggings

Patent

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

364488, 364489, 364490, 364491, 395375, 395800, 395600, 341 51, 341 67, 371 371, 371 376, G06F 300, G06F 1500

Patent

active

055532721

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.

REFERENCES:
patent: 4450520 (1984-05-01), Hollaar et al.
patent: 4698751 (1987-10-01), Parvin
patent: 4760523 (1988-07-01), Yu et al.
patent: 4835775 (1989-05-01), Seroussi
patent: 4845610 (1989-07-01), Parvin
patent: 4958348 (1990-09-01), Berlekamp et al.
patent: 4958377 (1990-09-01), Takahashi
patent: 4979101 (1990-12-01), Takahashi
patent: 4992933 (1991-02-01), Taylor
patent: 5008818 (1991-04-01), Bocast
patent: 5051947 (1991-09-01), Messenger et al.
patent: 5157671 (1992-10-01), Karplus
patent: 5179378 (1993-01-01), Ranganathan et al.
patent: 5276741 (1994-01-01), Aragon
patent: 5329405 (1994-07-01), Hou et al.
patent: 5377349 (1994-12-01), Motomura
patent: 5440753 (1995-08-01), Hou et al.

LandOfFree

Say what you really think

Search LandOfFree.com for the USA inventors and patents. Rate them and share your experience with other people.

Rating

VLSI circuit structure for determining the edit distance between does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with VLSI circuit structure for determining the edit distance between, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and VLSI circuit structure for determining the edit distance between will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFUS-PAI-O-1959522

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.