US5060143A
Expired / Lapsed
US
⏱️ 0.0 years remaining
System for string searching including parallel comparison of candidate data block-by-block
Assignee: Nytell Software LLC
•
Filing: 1988-08-10
•
Granted: 1991-10-22
•
Expires: 2008-08-10
Abstract
Abstract A highly efficient string search algorithm and circuit are disclosed. The string search algorithm utilizes candidate-data-parallel, target data serial comparisons along with an early mismatch detection mechanism to locate a target in a candidate data base in a highly efficient manner.
Inventors
- 👤 Kuo-Chu Lee
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 10:09
CPC Classifications
G; G06; G06F; G06F7/00; G06F7/02; G06F16/00; G06F16/90; G06F16/903; G06F16/90335; G06F16/90344; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933; Y10S707/99936
Claims Analysis
Total Claims: 7
Claim 1
Independent Claim
244 words
An electronic string search processor circuit for identifying a target pattern in a data base in the form of a string of characters, said circuit comprising: a comparator array for comparing in parallel a current block of characters from said data base with a character from said target, match trace processor means responsive to said comparator array for determining if said target character forms part of a match trace, said match trace processor means comprising a register for storing information identifying match traces including the last character of an immediately previous block from said data base, in order to determine when a match trace crosses the boundary between the previous block and the current block of said data base, means for loading a new target character into said comparator array if said target character forms part of a match trace and it is not the last character of said target, means for loading a new block from said data base into said comparator array if said target character does not form part of a match trace and there are no match traces including the last character of the previous block of said data base which can possibly be extended across said boundary into the current block by a subsequent character from said target, and means for generating a hit signal for indicating the presence of said target in said data base when the last character of said target forms part of a match trace.
Claim 2
Dependent Claim
244 words
An electronic string search processor circuit for identifying a target pattern in a data base in the form of a string of characters, said circuit comprising: a comparator array for comparing in parallel a current block of characters from said data base with a character from said target, match trace processor means responsive to said comparator array for determining if said target character forms part of a match trace, said match trace processor means comprising a register for storing information identifying match traces including the last character of an immediately previous block from said data base, in order to determine when a match trace crosses the boundary between the previous block and the current block of said data base, means for loading a new target character into said comparator array if said target character forms part of a match trace and it is not the last character of said target, means for loading a new block from said data base into said comparator array if said target character does not form part of a match trace and there are no match traces including the last character of the previous block of said data base which can possibly be extended across said boundary into the current block by a subsequent character from said target, and means for generating a hit signal for indicating the presence of said target in said data base when the last character of said target forms part of a match trace.
Claim 3
Dependent Claim
28 words
The circuit of claim 1 wherein said comparator array simultaneously compares in parallel two or more characters from said target with said current block of said data base.
Claim 4
Independent Claim
258 words
A method for operating an electronic string search processor to identify a target pattern in a data base in the form of a string of characters, said method comprising the steps of utilizing a comparator array forming part of said processor for comparing in parallel a current block of data base characters with a character from said target, electronically providing information identifying match traces including the last character of an immediately previous block of characters from said data base, electronically determining in response to said comparing step and in response to said providing step if said character from said target belongs to a match trace, said determining step including the step of determining whether said target character belongs to a match trace which crosses the boundary between said previous block and said current block of said data base, loading a new target character into said comparator array if said target character forms part of a match trace and said target character is not the last target character, loading a new block of said data base into said comparator array if said target character does not form part of a match trace and there are no match traces including the last character of the previous block of said data base which can possibly be extended across said boundary into the current block by a subsequent character from said target, and electronically generating a hit signal for indicating the presence of said target in said data base when the last character of said target forms part of a match trace.
Claim 5
Independent Claim
258 words
A method for operating an electronic string search processor to identify a target pattern in a data base in the form of a string of characters, said method comprising the steps of utilizing a comparator array forming part of said processor for comparing in parallel a current block of data base characters with a character from said target, electronically providing information identifying match traces including the last character of an immediately previous block of characters from said data base, electronically determining in response to said comparing step and in response to said providing step if said character from said target belongs to a match trace, said determining step including the step of determining whether said target character belongs to a match trace which crosses the boundary between said previous block and said current block of said data base, loading a new target character into said comparator array if said target character forms part of a match trace and said target character is not the last target character, loading a new block of said data base into said comparator array if said target character does not form part of a match trace and there are no match traces including the last character of the previous block of said data base which can possibly be extended across said boundary into the current block by a subsequent character from said target, and electronically generating a hit signal for indicating the presence of said target in said data base when the last character of said target forms part of a match trace.
Claim 6
Dependent Claim
31 words
The method of claim 3 wherein said providing step comprises storing in a register said information identifying match traces including the last character of said previous block from said data base.
Claim 7
Dependent Claim
31 words
The method of claim 3 wherein said comparing step comprises comparing in parallel two or more characters from said target with the characters of the current block of said data base.
References Cited (Backward Citations)
US3970993A
Cited
US4490811A
Cited
US4450520A
Cited
US4625295A
Cited
US4550436A
Cited
US4760523A
Cited
US4899128A
Cited
US4876643A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1994-10-21 | 1995-04-22 | 1995-10-22 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1998-10-21 | 1999-04-22 | 1999-10-22 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2002-10-21 | 2003-04-22 | 2003-10-22 | $7700.00 | Window Closed / Lapsed |