High-speed term searcher
First Claim
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 Assignments
0 Petitions
Accused Products
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.
-
Citations
12 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. - View Dependent Claims (2, 3, 4)
-
-
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. - View Dependent Claims (7)
-
-
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. - View Dependent Claims (10)
-
-
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. - View Dependent Claims (12)
-
Specification