Parallel text matching methods and apparatus

• US 4,550,436 A
• Filed: 07/26/1983
• Issued: 10/29/1985
• Est. Priority Date: 07/26/1983
• Status: Expired due to Term

• Current Assignee: Bell Telephone Laboratories, Inc. (Nokia Corporation)
• Original Assignee: AT&T, Inc.
• Inventors: Freeman, Martin, Levy, Leon S.
• Primary Examiner(s): Boudreau, Leo H.
• Application Number:
  US06/517,330
• Time in Patent Office: 826 Days
• Field of Search: 382/10, 382/34, 382/30, 340/146.2
• US Class Current: 382/218
• CPC Class Codes: G06F 16/90344 by using string matching techniques

Abstract

Pattern-matching circuitry is shown which permits the simultaneous or near simultaneous matching of entire lines of text to a regular expression test pattern. A synchronous or clocked embodiment is disclosed, as well as an asynchronous embodiment.

Claims

1. Apparatus for matching signals representing a line of printed alphanumeric characters with a given pattern of test signals representing a canonical string of printed characters comprising

means for storing said line of character representing signals,

means for storing said pattern of test signals,

a plurality of alphanumeric character recognition cells equal in number to the number of said characters in said line,

means for applying each one of said character signals from said line to a respective one of said cells,

means for sequentially applying each of said pattern test signals to all of said cells, and

means for detecting the sequential matching to said pattern test signals in successive ones of said cells.

2. Apparatus according to claim 1 wherein each of said cells comprises

means for sequentially comparing each of said character representing signals to all of said pattern test signals, and

means responsive to a match of said entire pattern for enabling said line signal storage means.

3. Apparatus according to claim 1 wherein each of said cells comprises

plurality of subcells,

means for generating identifying signals for numerically identifying the successive states of the process of matching said character representing signals to said pattern test signals,

means for incrementing said identifying signals for each match in said process,

means for substituting fallback identifying signals for said state identifying signals for each failure to match in said process, and

means for indicating the attainment of a predetermined final state identification signal.

4. Apparatus according to claim 1 wherein said pattern test signals comprise a representation of a regular expression including alphabet signals and operator signals.

5. Apparatus according to claim 2 further comprising

shift register means for storing said pattern test signals, and

means for sequentially shifting each of said pattern test signals out of said shift register means and into all of said cells.

6. Apparatus according to claim 4 wherein said operator signals include a start-of-line anchoring signal.

7. Apparatus according to claim 4 wherein said operator signals include an end-of-line anchoring signal.

8. Apparatus according to claim 4 wherein said operator signals include a "wild card" signal which stands for any sequence of any number of other symbols.

9. The method matching an entire line of input alphanumeric text signals with a given pattern of alphanumeric test signals comprising the steps of

(1) storing said given pattern of test signals,

(2) comparing each of said test signals simultaneously with all of said input text signals,

(3) generating a pattern-matching signal in response to a sequence of test signal matches in successive input text signal comparisons, and

(4) initiating a new line-matching cycle by obtaining another line of input text signals in response to said pattern-matching signal.

10. The method according to claim 9 further comprising the steps of

(a) storing a given pattern of fallback state identification signals,

(b) incrementing a matching state identification signal each time one of said test signals matches one of said text signals, and

(c) substituting a corresponding fallback state identification signal for said matching state identification signal each time one of said test signals fails to match one of said text signals.

11. The method according to claim 9 further comprising the step of generating a pattern of test signals comprising a regular expression including alphabet signals and operator signals.