High-speed term searcher

• US 4,314,356 A
• Filed: 10/24/1979
• Issued: 02/02/1982
• Est. Priority Date: 10/24/1979
• Status: Expired due to Term

• Current Assignee: Contel Federal Systems Incorporated (Verizon Communications Inc.)
• Original Assignee: Bunker Ramo Corporation (Honeywell International Inc.)
• Inventors: Scarbrough, Alfred D.
• Primary Examiner(s): Thesz, Joseph M.
• Assistant Examiner(s): Heckler, Thomas M.
• Application Number:
  US06/088,048
• Time in Patent Office: 832 Days
• Field of Search: 364/200 MS File, 364/900 MS File, 365/49, 365/50
• US Class Current: 1/1
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

A method and apparatus for high-speed searching of a byte stream for predetermined words or terms. More particularly, the present invention is directed to a method and apparatus for use in combination with a data source supplying a stream of binary signals defining both the identities of alphanumeric characters occurring in an ordered sequence and the position of each such character within a character group for detecting the occurrence of a particularly ordered group of R characters. The apparatus preferably includes a search memory means comprised of multiple (N) sets of R storage locations each of which includes S bit stages, each bit stage being capable of storing a "1" or "0" state. R represents the number of characters within a character group and S represents the number of different characters that can be identified. Each of the R storage locations may store one or more "0" bits, the position of each "0" bit identifying a particular character. A first decoding means is provided responsive to the position within a character group of each character defined by the binary signals for addressing a corresponding one of the R locations. A second decoding means is provided responsive to the identity of each character defined by the binary signals for addressing a particular one of the S bit stages within the addressed location. The addressing of a stage storing a "1" generates a word mismatch signal.

Claims

1. In combination with a data source supplying a stream of binary signals defining both the identities of alphanumeric characters occurring in an ordered sequence and the position of each such character within a character group, an apparatus for detecting the occurrence of a particularly ordered group of R characters, said apparatus comprising:

search memory means comprised of a first group of R sets of S bit storage devices wherein R represents the number of entries in a character position field and S represents the number of entries in a character identification field, each of said bit storage devices defining a first or second state;

first means responsive to the position within a character group of each character defined by said binary signals for addressing the corresponding one of said R sets;

second means responsive to the identity of each character defined by said binary signals for addressing the corresponding one of said S bit storage devices within said addressed one of said R sets; and

third means responsive to said first and second means addressing a bit storage device defining a first state for generating a mismatch signal.

2. The apparatus of claim 1 in which said search memory means comprises a plurality of groups of R sets of S bit storage devices wherein R represents the number of entries in a character position field and S represents the number of entries in a character identification field, each of said bit storage devices defining a first or second state;

said first means responsive to the position within a character group of each character defined by said binary signals comprises means for addressing the corresponding one of said R sets in each of said plurality of groups of R sets; and

said second means responsive to the identity of each character defined by said binary signals comprises means for addressing the corresponding one of said S bit storage devices within said addressed R set in each of said plurality of groups of R sets.

3. The apparatus of claim 2 further comprising:

a word match register containing a plurality of bit storage stages each of which corresponds to one of said group of R sets;

means for placing each of said word match register storage stages in a first stage at the beginning of each of said character groups; and

means for interconnecting each of said word match register storage stages to its corresponding group of R sets of S bit storage devices whereby a mismatch signal from one of said corresponding bit storage devices will cause its corresponding word match register storage stage to change from said first state to a second state.

4. The apparatus of claim 3 further comprising:

a document match register having a plurality of bit storage stages each of which corresponds to a storage stage in said word match register;

means for placing each of said document match register storage stages in a first state at the beginning of said sequence; and

means for transferring at the end of each of said character groups information contained in said word match register storage stages to their corresponding document match register storage stages whereby said second state in one of said word match register storage stages will cause the corresponding document match register storage stage to change from said first state to a second state.

5. In combination with a data source supplying a stream of incoming binary signals representing a document formed of words formed of characters formed of a plurality of said binary signals, an apparatus for detecting the occurrence of a predetermined character pattern comprising;

first means for identifying the order of occurrence of a predetermined number of incoming characters in an incoming word;

a second means for identifying each incoming character; and

a search memory means responsive to said first and second means for determining if each identified incoming character and its order of occurrence in an incoming word corresponds to a character and its order of occurrence in said predetermined character pattern, said search memory means comprising a first set of bit stages, each bit stage corresponding to a specific character and an order of occurrence with respect to an incoming word;

each of said first set of bit stages defining a first stage if that bit stage does not correspond to a character and its order of occurrence within said predetermined character pattern;

means for addressing each bit stage corresponding to each incoming character and its order of occurrence within an incoming word; and

means for generating a mismatch signal whenever said addressed bit stage is identified with said first state.

6. In combination with a data source supplying a stream of incoming binary signals representing a document formed of words formed of characters formed of a plurality of said binary signals, an apparatus for detecting the occurrence of a predetermined character pattern comprising;

first means for identifying the order of occurrence of a predetermined number of incoming character in an incoming word;

second means for identifying each incoming character; and

a search memory means responsive to said first and second means for determining if each identified incoming character and its order of occurrence in an incoming word corresponds to a character and its order of occurrence in said predetermined character pattern, said search memory means comprising N sets of bit stages, each bit stage in a set corresponding to a specific character and an order of occurrence with respect to an incoming word;

each bit stage defining a first state if that stage does not correspond to a character and its order of occurrence within said predetermined character pattern;

means for addressing each bit stage within each of N sets of bit stages corresponding to each incoming character and its order of occurrence within an incoming word; and

means for generating a mismatch signal whenever said addressed bit stage is identified with said first state.

7. The system of claim 6 further comprising:

a word match register having N bit storage stages, each of which corresponds to one of said N sets of bit stages;

means for placing each of said word match register storage states in a first state at the beginning of each incoming word; and

means for changing the state of each of said word match register storage stages to a second state whenever a mismatch signal is generated as a result of addressing a bit stage in its corresponding N set of bit stages.

8. A method for detecting the occurrence of a particularly ordered group or R characters from a stream of binary signals defining both the identities of alphanumeric characters occurring in an ordered sequence and the position of each such character within a character group, the steps comprising:

defining a memory plane including R storage locations, each of said locations including S bit stages each capable of storing a first state or a second state where S represents the number of different characters that can be identified, said locations storing one or more first states each identifying a particular character;

addressing one of said R locations corresponding to the position within a character group of each character defined by said binary signals;

addressing one of said S bit stages within said addressed R location corresponding to the identity of each character defined by said binary signals; and

generating a mismatch signal whenever a bit stage storing a second state is addressed.

9. A method for detecting the occurrence of a particularly ordered group of R characters in an incoming stream of binary signals defining both the identities of alphanumeric characters occurring in an ordered sequence and the position of each such character within a character group, the steps comprising:

storing R sets of S bits each, where S represents the number of different characters capable of being identified;

selectively identifying a particular character in each set by establishing a unique state in one bit of the S bits thereof;

comparing each character in said incoming stream with the character identified by the particular set of S bits corresponding to the position of said character within a character group; and

generating a mismatch signal whenever said comparing step indicates that the character in said incoming stream differs from the character identified by the corresponding set of S bits.

10. The method of claim 9 wherein said comparing step comprises examining the state of a particular bit within said particular set of S bits which particular bit is dependent upon the identity of the incoming stream character being compared.

11. In combination with a data source supplying a stream of binary signals representing a stream of characters arranged in character groups wherein said character stream includes S different characters, an apparatus for detecting the occurrence of a character group containing a sequence of R particular characters, said apparatus comprising:

character register means;

means for loading said character register means with successive characters in said character stream;

character counter means for counting characters in a character group successively loaded into said character register means;

a search memory means comprised of R sets of S bit storage devices, each device capable of selectively defining either a first or second state;

first addressing means responsive to each different count defined by said character counter means for addressing a different set of storage devices;

second addressing means responsive to each different character loaded into said character register means for addressing a different one of said S bit storage devices; and

means responsive to said first and second addressing means addressing a bit storage device defining a first state for generating a mismatch signal.

12. The combination of claim 11 further including a word match register capable of defining either a match or mismatch state;

means for establishing a match state in said word match register prior to generating a mismatch signal attributable to addressing said search memory with respect to the first character in each character group; and

means responsive to each generated mismatch signal for switching said word match register to a mismatch state.