Improved fast search processor

Claim 3

A method as defined in claim 1, and further including the steps of: storing a first match result associated with a first search term on an additional line connecting the cells; generating a second match result relating to a second search term; and logicaly combining the first and second match results for output from the serially connected cells.

Claim 4

A method as defined in claim 2, and further including the steps of: generating additional match results associated with additional search terms, which may be logically combined with the first and second search terms in a nested arrangement.

Claim 5

A method as defined in claim 2, and further including the steps of: counting the number of occurrences of selected search terms, to provide for the searching of enumerated conditions within the text stream.

Claim 6

A method as defined in claim 3, and further including the steps of: counting the number of occurrences of selected search terms, to provide for the searching of enumerated conditions within the text stream.

Claim 7

A method as defined in claim 2, and further including the steps of: detecting boundaries of predefined text segments within the text stream; and enabling the search functions to be performed only within a fixed window of one text segment.

Claim 8

A method as defined in claim 3, and further including the steps of: detecting boundaries of predefined text segments within the text stream; and enabling the search functions to be performed only within a fixed window of one text segment.

Claim 9

A method as defined in claim 4, and further including the steps of: detecting boundaries of predefined text segments within the text stream; and enabling the search functions to be performed only within a fixed window of one text segment.

Claim 10

A method as defined in claim 5, and further including the steps of: detecting boundaries of predefined text segments within the text stream; and enabling the search functions to be performed only within a fixed window of one text segment.

Claim 11

A method as defined in claim 2, and further including the steps of: detecting the boundaries of predefined text segments within the text stream; counting the number of segments to determine whether a search term has appeared within a specified number of text segments; generating a match signal only when the specified search terms have appeared in combination within the specified number of text segments.

Claim 12

A method as defined in claim 10, and further including the steps of: reducing the number of match signals generated by ANDing the match signals with a signal derived from the boundaries of the segments.

Claim 13

A special-purpose search processor for searching a stream of text for specified search patterns, the processor comprising: means for storing a search pattern in a serially connected plurality of comparison cells; means for passing the text stream through the comparison cells; means for detecting exact matches between the text stream and the search pattern; means for selectively detecting inexact matches between the text stream and the search pattern, including, to a limited and preselected extent, the presence of incorrect and extra characters in the text stream and the absence of characters from the text stream; and means for generating match signals indicative of the exact and inexact matches, for output from the serially connected cells in synchronism with the text stream.

Claim 14

A special-purpose search processor for searching a stream of text for specified search patterns, the processor comprising: means for storing a search pattern in a serially connected plurality of comparison cells; means for passing the text stream through the comparison cells; means for detecting exact matches between the text stream and the search pattern; means for selectively detecting inexact matches between the text stream and the search pattern, including, to a limited and preselected extent, the presence of incorrect and extra characters in the text stream and the absence of characters from the text stream; and means for generating match signals indicative of the exact and inexact matches, for output from the serially connected cells in synchronism with the text stream.

Claim 15

A special-purpose processor as defined in claim 12, and further including: means for storing a first match result associated with a first search term on an additional line connecting the cells; means for generating a second match result relating to a second search term; and means for logically combining the first and second match results for output from the serially con­nected cells.

Claim 16

A special-purpose processor as defined in claim 13, and further including: means for generating additional match results associated with additional search terms, which may be logically combined with the first and second search terms in a nested arrangement.

Claim 17

A special-purpose processor as defined in claim 13, and further including: means for counting the number of occurrences of selected search terms, to provide for the searching of enumerated conditions within the text stream.

Claim 18

A special-purpose processor as defined in claim 14, and further including: means for counting the number of occurrences of selected search terms, to provide for the searching of enumerated conditions within the text stream.

Claim 19

A special-purpose processor as defined in claim 13, and further including: means for detecting boundaries of predefined text segments within the text stream; and means for enabling the search functions to be performed only within a fixed window of one text segment.

Claim 20

A special-purpose processor as defined in claim 14, and further including: means for detecting boundaries of predefined text segments within the text stream; and means for enabling the search functions to be performed only within a fixed window of one text segment.

Claim 21

A special-purpose processor as defined in claim 15, and further including: means for detecting boundaries of predefined text segments within the text stream; and means for enabling the search functions to be performed only within a fixed window of one text segment.

Claim 22

A special-purpose processor as defined in claim 16, and further including: means for detecting boundaries of predefined text segments within the text stream; and means for enabling the search functions to be performed only within a fixed window of one text segment.

Claim 23

A special-purpose processor as defined in claim 13, and further including: means for detecting the boundaries of predefined text segments within the text stream; means for counting the number of segments to determine whether a search term has appeared within a specified number of text segments; means for generating a match signal only when the specified search terms have appeared in com­bination within the specified number of text segments.

Claim 24

A special-purpose processor as defined in claim 21, and further including: means for reducing the number of match signals generated by ANDing the match signals with a signal derived from the boundaries of the segments.

Claim 25

A special-purpose search processor, comprising: a plurality of serially-connected cells, each cell including a pattern register for storing part of a pattern to be searched for, a character register for storing a character of a data stream to be searched, the character registers of the cells being serially connected to form a character line, a match register for storing a match value indicative of a match between the search pattern and the data stream, the match registers of the cells being serially connected to form a match line, and match logic for modifying an incoming match value in accordance with the conditions of other registers and programmable flags in the cell; means for initializing the cells to contain the search pattern; and clock means for gating the data stream from cell to cell in the character line; and wherein the match logic includes means for generating match signals to indicate exact and inexact matches between the search pattern and charac­ters in the text, and wherein inexact matches involve incorrect, missing or extra characters.

Claim 26

A special-purpose search processor, comprising: a plurality of serially-connected cells, each cell including a pattern register for storing part of a pattern to be searched for, a character register for storing a character of a data stream to be searched, the character registers of the cells being serially connected to form a character line, a match register for storing a match value indicative of a match between the search pattern and the data stream, the match registers of the cells being serially connected to form a match line, and match logic for modifying an incoming match value in accordance with the conditions of other registers and programmable flags in the cell; means for initializing the cells to contain the search pattern; and clock means for gating the data stream from cell to cell in the character line; and wherein the match logic includes means for generating match signals to indicate exact and inexact matches between the search pattern and charac­ters in the text, and wherein inexact matches involve incorrect, missing or extra characters.

Claim 27

A special-purpose search processor as defined in claim 23, in which the means for generating exact and inexact matches includes: means for loading a tolerance count into the match line; a delay match register in each cell, connected to receive input from the match register and to provide output on the match line to the next cell in series; means for selectively decrementing the tolerance count as it is transmitted to the delay match register, whenever a non-match is detected in a cell, whereby the presence of a non-zero tolerance count on the match line is indicative of a match.

Claim 28

A special-purpose search processor as defined in claim 24, in which the means for generating exact and inexact matches further includes: means for allowing for missing characters in the text stream; and means for allowing for extra characters in the text stream.

Claim 29

A special-purpose search processor as defined in claim 25, in which the means for allowing for missing characters includes: means responsive to a missing-extra control flag in the cell, for providing a path bypassing the delay match register, but still decrementing the tolerance value, to yield a tolerance value that would be obtained if a character were missing from the text stream; and means for comparing the tolerance value obtained from the means for providing a path bypassing the delay match register with the tolerance value obtained as an output of the delay match register, and choosing the greater of the two for output on the match line.

Claim 30

A special-purpose search processor as defined in claim 25, in which the means for allowing for extra characters includes: means responsive to the missing-extra con­trol flag, for providing a path feeding a tolerance value back from the output of the delay register to its input, but still decrementing the tolerance value, to yield a tolerance value that would be obtained if the current character were an extra character in the text stream; and means for comparing the tolerance value fed back from the output of the delay match register with the tolerance value that would normally be input to the delay match register, and choosing the greater of the two for input to the delay match register.

Claim 31

A special-purpose search processor as defined in claim 23, in which the means for loading a tolerance count into the match line includes: a tolerance register; means responsive to a load-tolerance flag in the cell and to the condition of a selected other register in the cell, for substituting a value stored in the tolerance register for the value stored in the match register.

Claim 32

A special-purpose search processor as defined in claim 23, in which the match logic further includes: means responsive to a must-be-there flag, for clearing the tolerance value on the match if there is no match in a cell in which the flag is set.

Claim 33

A special-purpose search processor as defined in claim 23, in which the match logic further includes: means responsive to an invert-character flag in the cell, for inverting the sense of the match signal obtained by comparing the pattern register and the character register.

Claim 34

A special-purpose search processor, comprising: a plurality of serially-connected cells, each cell including a pattern register for storing part of a pattern to be searched for, a character register for storing a character of a data stream to be searched, the character registers of the cells being serially connected to form a character line, a match register for storing a match value indicative of a match between the search pattern and the data stream, the match registers of the cells being serially connected to form a match line, match logic for modifying an incoming match value in accordance with the conditions of other registers and programmable flags in the cell; an accumulator register for storing a binary value derived from the accumulator register of an adjacent cell, the accumulator registers being connected to form a serial accumulator line through the cells, and accumulator logic for modifying the accumulator register contents for output to the next cell, by combining the accumulator register with a selected condition of the cell, in accord­ance with a preselected logical function; means for initializing the cells to contain the search pattern; and clock means for gating the data stream from cell to cell in the character line; and wherein the match logic includes means for generating match signals to indicate exact and inexact matches between the search pattern and charac­ters in the text, and wherein inexact matches involve incorrect, missing or extra characters.

Claim 35

A special-purpose search processor, comprising: a plurality of serially-connected cells, each cell including a pattern register for storing part of a pattern to be searched for, a character register for storing a character of a data stream to be searched, the character registers of the cells being serially connected to form a character line, a match register for storing a match value indicative of a match between the search pattern and the data stream, the match registers of the cells being serially connected to form a match line, match logic for modifying an incoming match value in accordance with the conditions of other registers and programmable flags in the cell; an accumulator register for storing a binary value derived from the accumulator register of an adjacent cell, the accumulator registers being connected to form a serial accumulator line through the cells, and accumulator logic for modifying the accumulator register contents for output to the next cell, by combining the accumulator register with a selected condition of the cell, in accord­ance with a preselected logical function; means for initializing the cells to contain the search pattern; and clock means for gating the data stream from cell to cell in the character line; and wherein the match logic includes means for generating match signals to indicate exact and inexact matches between the search pattern and charac­ters in the text, and wherein inexact matches involve incorrect, missing or extra characters.

Claim 36

A special-purpose search processor as defined in claim 31, and further comprising: a plurality of additional registers in each cell, corresponding registers being serially connected to form a plurality of additional lines through the cells.

Claim 37

A special-purpose search processor as defined in claim 32, in which: the match logic and accumulator logic cooperate to provide means for saving a match indica­tor associated with a first string of a search pattern on the accumulator line, and means for logically ORing the saved match indicator with a match indicator associated with a second string of a search pattern.

Claim 38

A special-purpose search processor as defined in claim 33, in which: the match logic and accumulator logic cooperate to provide means for saving a match indica­tor associated with a third string of a search pattern on one of the additional lines, and to subsequently OR all of the match indicators on the accumulator line.

Claim 39

A special-purpose search processor as defined in claim 32, in which: the match logic is configured to detect boundaries between predefined segments of text; and the match logic and accumulator logic cooperate to provide means for locating selected search patterns in combination within one of the segments of text.

Claim 40

A special-purpose search processor as defined in claim 32, in which: the processor further includes a counter in each cell, and counter control logic for loading, in­crementing and decrementing the counter; the match logic and counter control logic include means for loading a selected counter to indicate a number of times that a search pattern string is to be located, and means for decrementing the counter each time the search pattern string is located, and means for transferring a zero counter value to the accumulator line to indicate a desired match of at least the number initially stored in the counter.

Claim 41

A special-purpose search processor as defined in claim 35, in which: the processor further includes a counter in each cell, and counter control logic for loading, in­crementing and decrementing the counter; the match logic and counter control logic include means for loading a selected counter to indicate a number of times that a search pattern string is to be located within a segment of text, and means for decrementing the counter each time the search pattern string is located, and means for transferring a zero counter value to the accumulator line to indicate a desired match of at least the number initially stored in the counter.

Claim 42

A special-purpose search processor as defined in claim 37, in which: the means for loading the counter is responsive to the detection of segment boundaries, whereby the desired search is reinitiated at each new segment of text.

Claim 43

A special-purpose search processor as defined in claim 32, for use in locating a subset of at least n terms of a set of m search terms within a specified text segment, wherein: each cell includes an increment line and a decrement register connected to form and increment line and a decrement line; the pattern registers are configured to define the m search terms and to provide a match signal on a selected line indicative of the start of a text segment; the signal indicative of the start of a text segment is employed to load the counter with a count of one in a counter cell following each search term; a matching search term causes decrementing of the counter in the following cell and generation of a "1" signal on the accumulator line; each cell following a counter cell is configured as a differentiator, to provide a "1" out­put on the increment line whenever the accumulator becomes a "1", and a "1" output output on the decrement line whenever the accumulator line becomes a "0"; a final cell following the search pattern segments functions as an integrator, having a counter initially set to the value -n, incremented by a "1" on the increment line, and decremented by a "1" on the decrement line, whereby location of the desired subset of terms is indicated by the counter in the final cell becoming zero.

Claim 44

A special-purpose search processor as defined in claim 39, and further including: means included in logic associated with the increment and decrement lines, for avoiding possible collision between "1" values placed on the lines by cells associated with different search terms.

Claim 45

A special-purpose search processor as defined in claim 32, for locating a combination of search terms within a sliding window of n text segments, wherein: each search term generates a match signal on the match line, which signal is employed to load the counter with n in the cell following the search segment; cells preceding the search term cells are employed to detect segment boundaries and to generate match signals that are saved on one of the additional lines in the processor, and are employed to decrement the counters, whereby each counter will be counted down to zero after n segments of text have passed; and non-zero count indications from all of the counters are ANDed together in the accumulator line to provide an indication of the presence of all search terms in the last n text segments.

Claim 46

A special-purpose search processor as defined in claim 41, and further including: means for reducing the number of match signals obtained from the processor.

Claim 47

A special-purpose search processor as defined in claim 42, in which: the means for reducing the number of match signals includes means for ANDing the match signals with selected ones of the sentence boundary match signals saved on the additional line.

Claim 48

A special-purpose search processor as defined in claim 41, and further including: means for counting the number of occurrences of each of the search terms, to permit the location of enumerated search terms within a sliding window of n text segments.

Claim 51

A method as defined in claim 45, and further including the steps of: storing a first match result associated with a first search term on an additional line connecting the cells; generating a second match result relating to a second search term; and logically combining the first and second match results for output from the serially connected cells.

Claim 52

A method as defined in claim 46, and further including the steps of: generating additional match results associated with additional search terms, which may be logically combined with the first and second search terms in a nested arrangement.

Claim 53

A method as defined in claim 46, and further including the steps of: counting the number of occurrences of selected search terms, to provide for the searching of enumerated conditions within the text stream.

Claim 54

A method as defined in claim 47, and further including the steps of: counting the number of occurrences of selected search terms, to provide for the searching of enumerated conditions within the text stream.

Claim 55

A method as defined in claim 46, and further including the steps of: detecting boundaries of predefined text segments within the text stream; and enabling the search functions to be performed only within a fixed window of one text segment.

Claim 56

A method as defined in claim 47, and further including the steps of: detecting boundaries of predefined text segments within the text stream; and enabling the search functions to be performed only within a fixed window of one text segment.

Claim 57

A method as defined in claim 48, and further including the steps of: detecting boundaries of predefined text segments within the text stream; and enabling the search functions to be performed only within a fixed window of one text segment.

Claim 58

A method as defined in claim 49, and further including the steps of: detecting boundaries of predefined text segments within the text stream; and enabling the search functions to be performed only within a fixed window of one text segment.

Claim 59

A method as defined in claim 47, and further including the steps of: detecting the boundaries of predefined text segments within the text stream; counting the number of segments to determine whether a search term has appeared within a specified number of text segments; generating a match signal only when the specified search terms have appeared in combination within the specified number of text segments.

Claim 60

A method as defined in claim 54, and further including the steps of: reducing the number of match signals generated by ANDing the match signals with a signal derived from the boundaries of the segments.