Patent US4450520A successfully refreshed from Google Patents.
US4450520A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and system for matching encoded characters
Assignee: University of Illinois Foundation
•
Filing: 1981-03-11
•
Granted: 1984-05-22
•
Expires: 2001-03-11
Abstract
Abstract A means and method for comparing an incoming sequential string of digitally encoded characters from a database stored in a conventional memory against a pattern with an arbitrary number of elements, comprising specified characters or character types (alphabetic, numeric, delimiter, etc.) or tokens to indicate the matching of a specified or arbitrary number of input characters, is disclosed. The system comprises a number of digital machines, sequenced by control words fetched from their memories. The control words may indicate the current input character or character type of interest for each machine, the address of the potential next control word of the machine, a flag indicating the successful completion of a match, and other control fields. If the input character matches the character or type of interest, the machine's next control word will be that specified by the current control word, and optionally the next control word of one or more of the other machines will be forced to an address specified in the current control word. By properly specifying the control words in each machine the input character string can be compared against an arbitrary number of pattern elements, limited only by the ability to map the elements into the control word memories of the available machines.
Inventors
- 👤 Lee A. Hollaar
- 👤 Roger L. Haskin
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-23 22:14
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/90; G06F16/903; G06F16/90335; G06F16/90344
Claims Analysis
Total Claims: 27
Claim 1
Independent Claim
346 words
A method, for detecting matches between strings of input characters and one or more patterns, each pattern comprising elements consisting of tokens, employing a finite state automaton, responsive to said strings of input characters, comprising a plurality of character matchers acting in concert; each character matcher being characterized as capable of existing in one of a plurality of states, each such state having (a) one token from a pattern, to be compared against a current input character, (b) first instructions, which govern transitions to the next state of said character matcher, and (c) second instructions, which force other character matchers into specified states; each character matcher being further characterized as having at least an initial state, to be occupied by said character matcher at the start of the matching procedure, and an idle state, to be occupied by said character matcher after an unsuccessful comparison between the token specified in the current state of said character matcher and the current input character; the respective states being partitioned among said character matchers to avoid any sequence of input characters requiring any character matcher to be simultaneously in more than one state; said method, for each string of input characters to be matched and for each character matcher, comprising: (a) comparing, with the character matcher in its initial state, a first input character against the token specified in the initial state of the character matcher, whereby said comparison is either successful or unsuccessful; (b) transitioning, in consequence of an unsuccessful comparison, to the idle state of the character matcher; (c) transitioning, in consequence of a successful comparison, to a succeeding state, in accordance with instructions contained in the current state of the character matcher; (d) forcing other character matchers into new states specified in the instructions of the current state of the character matcher of step (c); (e) comparing a succeeding input character against the token specified in the succeeding state and transitioning to a further succeeding state in accordance with steps (b), (c), and (d); and (f) repeating step (e) until all input characters have been compared.
Claim 2
Independent Claim
346 words
A method, for detecting matches between strings of input characters and one or more patterns, each pattern comprising elements consisting of tokens, employing a finite state automaton, responsive to said strings of input characters, comprising a plurality of character matchers acting in concert; each character matcher being characterized as capable of existing in one of a plurality of states, each such state having (a) one token from a pattern, to be compared against a current input character, (b) first instructions, which govern transitions to the next state of said character matcher, and (c) second instructions, which force other character matchers into specified states; each character matcher being further characterized as having at least an initial state, to be occupied by said character matcher at the start of the matching procedure, and an idle state, to be occupied by said character matcher after an unsuccessful comparison between the token specified in the current state of said character matcher and the current input character; the respective states being partitioned among said character matchers to avoid any sequence of input characters requiring any character matcher to be simultaneously in more than one state; said method, for each string of input characters to be matched and for each character matcher, comprising: (a) comparing, with the character matcher in its initial state, a first input character against the token specified in the initial state of the character matcher, whereby said comparison is either successful or unsuccessful; (b) transitioning, in consequence of an unsuccessful comparison, to the idle state of the character matcher; (c) transitioning, in consequence of a successful comparison, to a succeeding state, in accordance with instructions contained in the current state of the character matcher; (d) forcing other character matchers into new states specified in the instructions of the current state of the character matcher of step (c); (e) comparing a succeeding input character against the token specified in the succeeding state and transitioning to a further succeeding state in accordance with steps (b), (c), and (d); and (f) repeating step (e) until all input characters have been compared.
Claim 3
Dependent Claim
17 words
The method of claim 1 wherein the initial state and the idle state comprise a single state.
Claim 4
Dependent Claim
35 words
The method of claim 1 wherein the plurality of character matchers are disposed in a ring configuration wherein each character matcher is capable of forcing only the two neighboring character matchers into a specified state.
Claim 5
Dependent Claim
25 words
The method of claim 1 wherein the input characters are stored in and delivered to the finite state automaton from a serial access memory device.
Claim 6
Dependent Claim
28 words
The method of claim 4 wherein the comparison and transitioning steps for each character matcher are synchronized to the character delivery rate of the serial access memory device.
Claim 7
Dependent Claim
22 words
The method of claim 1 wherein each state additionally has instructions which indicate a successful match of an element of the pattern.
Claim 8
Dependent Claim
27 words
The method of claim 6 wherein the indication of a successful match additionally includes an identifier for the specific element of the pattern that has been matched.
Claim 9
Dependent Claim
38 words
The method of claim 7 wherein the elements of the pattern correspond to words and phrases, whereby the indication of a successful match signifies that a particular word or phrase occurs in a particular string of input characters.
Claim 10
Independent Claim
405 words
A method, for detecting matches between strings of input characters and one or more patterns, each pattern comprising elements consisting of tokens, employing a finite state automaton, responsive to said strings of input characters, comprising a plurality of character matchers acting in concert; each character matcher being characterized as capable of existing in one of a plurality of states, each such state having (a) one token from a pattern, to be compared against a current input character, (b) first instructions, which govern transitions to the next state of said character matcher, (c) second instructions, which force other character matchers into specified states, and (d) a start-up table, responsive to said input character, which causes said character matcher to transition to a specified state upon recognition of a portion of one or more elements of said pattern; each character matcher being further characterized as having at least an initial state, to be occupied by said character matcher at the start of the matching procedure, and an idle state, to be occupied by said character matcher after an unsuccessful comparison between the token specified in the current state of said character matcher and the current input character; the respective states being partitioned among said character matchers to avoid any sequence of input characters requiring any character matcher to be simultaneously in more than one state; said method, for each string of input characters to be matched and a corresponding character matcher, comprising: (a) comparing, with the character matcher in its initial state, a first input character against the token specified in the initial state of the character matcher, whereby said comparison is either successful or unsuccessful; (b) transitioning, in consequence of an unsuccessful comparison, to the idle state of the character matcher; (c) transitioning, in consequence of a successful comparison, to a succeeding state, in accordance with instructions contained in the current state of the character matcher; (d) transitioning to the specified state in response to instructions from the start-up table of said character matcher whenever such a transition is so indicated; (e) forcing other character matchers into new states specified in the instructions of the current state of the character matcher of step (c); (f) comparing a succeeding input character against the token specified in the succeeding state and transitioning to a further succeeding state in accordance with steps (b), (c), (d), and (e); and (g) repeating step (e) until all input characters have been compared.
Claim 11
Independent Claim
405 words
A method, for detecting matches between strings of input characters and one or more patterns, each pattern comprising elements consisting of tokens, employing a finite state automaton, responsive to said strings of input characters, comprising a plurality of character matchers acting in concert; each character matcher being characterized as capable of existing in one of a plurality of states, each such state having (a) one token from a pattern, to be compared against a current input character, (b) first instructions, which govern transitions to the next state of said character matcher, (c) second instructions, which force other character matchers into specified states, and (d) a start-up table, responsive to said input character, which causes said character matcher to transition to a specified state upon recognition of a portion of one or more elements of said pattern; each character matcher being further characterized as having at least an initial state, to be occupied by said character matcher at the start of the matching procedure, and an idle state, to be occupied by said character matcher after an unsuccessful comparison between the token specified in the current state of said character matcher and the current input character; the respective states being partitioned among said character matchers to avoid any sequence of input characters requiring any character matcher to be simultaneously in more than one state; said method, for each string of input characters to be matched and a corresponding character matcher, comprising: (a) comparing, with the character matcher in its initial state, a first input character against the token specified in the initial state of the character matcher, whereby said comparison is either successful or unsuccessful; (b) transitioning, in consequence of an unsuccessful comparison, to the idle state of the character matcher; (c) transitioning, in consequence of a successful comparison, to a succeeding state, in accordance with instructions contained in the current state of the character matcher; (d) transitioning to the specified state in response to instructions from the start-up table of said character matcher whenever such a transition is so indicated; (e) forcing other character matchers into new states specified in the instructions of the current state of the character matcher of step (c); (f) comparing a succeeding input character against the token specified in the succeeding state and transitioning to a further succeeding state in accordance with steps (b), (c), (d), and (e); and (g) repeating step (e) until all input characters have been compared.
Claim 12
Dependent Claim
17 words
The method of claim 9 wherein the initial state and the idle state comprise a single state.
Claim 13
Dependent Claim
35 words
The method of claim 9 wherein the plurality of character matchers are disposed in a ring configuration wherein each character matcher is capable of forcing only the two neighboring character matchers into a specified state.
Claim 14
Dependent Claim
25 words
The method of claim 9 wherein the input characters are stored in and delivered to the finite state automaton from a serial access memory device.
Claim 15
Dependent Claim
28 words
The method of claim 12 wherein the comparison and transitioning steps for each character matcher are synchronized to the character delivery rate of the serial access memory device.
Claim 16
Dependent Claim
22 words
The method of claim 9 wherein each state additionally has instructions which indicate a successful match of an element of the pattern.
Claim 17
Dependent Claim
27 words
The method of claim 14 wherein the indication of a successful match additionally includes an identifier for the specific element of the pattern that has been matched.
Claim 18
Dependent Claim
38 words
The method of claim 15 wherein the elements of the pattern correspond to words and phrases, whereby the indication of a successful match signifies that a particular word or phrase occurs in a particular string of input characters.
Claim 19
Independent Claim
313 words
A system for detecting matches between strings of input characters from a database and one or more patterns, each pattern comprising elements consisting of tokens, employing a finite state automaton, responsive to said strings of input characters, comprising a plurality of character matchers acting in concert; each character matcher being characterized as capable of existing in one of a plurality of states, each such state having (a) one token from a pattern, to be compared against a current input character, (b) first instructions, which govern transitions to the next state of said character matcher, and (c) second instructions, which force other character matchers into specified states, each character matcher being responsive to one or more memories, comprising control words and storing tokens and instructions for a particular state; each character matcher being further characterized as having at least an initial state, to be occupied by said character matcher at the start of the matching procedure, and an idle state, to be occupied by said character matcher after an unsuccessful comparison between the token specified in the current state of said character matcher and the current input character; the respective states being partitioned among said character matchers to avoid any sequence of input characters requiring any character matcher to be simultaneously in more than one state; said system, for each string of input characters to be matched and a corresponding character matcher, comprising: (a) reading means, for reading said input characters from said database; (b) comparison means, for sequentially comparing each input character against the token associated with the current state of said character matcher; (c) determinant means, for determining a succeeding state of said character matcher based on a successful comparison of the current input character against the token specified in said character matcher's current state; and (d) forcing means, operative for said character matcher to force other character matchers into specified states.
Claim 20
Independent Claim
313 words
A system for detecting matches between strings of input characters from a database and one or more patterns, each pattern comprising elements consisting of tokens, employing a finite state automaton, responsive to said strings of input characters, comprising a plurality of character matchers acting in concert; each character matcher being characterized as capable of existing in one of a plurality of states, each such state having (a) one token from a pattern, to be compared against a current input character, (b) first instructions, which govern transitions to the next state of said character matcher, and (c) second instructions, which force other character matchers into specified states, each character matcher being responsive to one or more memories, comprising control words and storing tokens and instructions for a particular state; each character matcher being further characterized as having at least an initial state, to be occupied by said character matcher at the start of the matching procedure, and an idle state, to be occupied by said character matcher after an unsuccessful comparison between the token specified in the current state of said character matcher and the current input character; the respective states being partitioned among said character matchers to avoid any sequence of input characters requiring any character matcher to be simultaneously in more than one state; said system, for each string of input characters to be matched and a corresponding character matcher, comprising: (a) reading means, for reading said input characters from said database; (b) comparison means, for sequentially comparing each input character against the token associated with the current state of said character matcher; (c) determinant means, for determining a succeeding state of said character matcher based on a successful comparison of the current input character against the token specified in said character matcher's current state; and (d) forcing means, operative for said character matcher to force other character matchers into specified states.
Claim 21
Dependent Claim
17 words
The system of claim 17 wherein the initial state and the idle state comprise a single state.
Claim 22
Dependent Claim
34 words
The system of claim 17 wherein the character matchers are disposed in a ring configuration such that said character matcher is capable of forcing only the two neighboring character matchers into a specified state.
Claim 23
Dependent Claim
16 words
The system of claim 17 wherein said database is stored in a serial access memory device.
Claim 24
Dependent Claim
24 words
The system of claim 20 wherein comparison means and determinant means are synchronized to the character delivery rate of the serial access memory device.
Claim 25
Dependent Claim
21 words
The system of claim 17 wherein determinant means comprises instructions to indicate a successful match of an element of said pattern.
Claim 26
Dependent Claim
23 words
The system of claim 22 wherein said indication of a successful match additionally includes an identifier of the specified element of said pattern.
Claim 27
Dependent Claim
38 words
The system of claim 23 wherein the elements of the pattern correspond to words and phrases, whereby the indication of a successful match signifies that a particular word or phrase occurs in a particular string of input characters.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1987-05-22 | 1987-11-21 | 1988-05-22 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1991-05-22 | 1991-11-21 | 1992-05-22 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1995-05-22 | 1995-11-21 | 1996-05-22 | $7700.00 | Window Closed / Lapsed |