High-speed single-pass textual search processor for locating exact and inexact matches of a search pattern in a textual stream

• US 5,051,947 A
• Filed: 12/10/1985
• Issued: 09/24/1991
• Est. Priority Date: 12/10/1985
• Status: Expired due to Term

• Current Assignee: Northrop Grumman Corporation
• Original Assignee: TRW Inc. (Northrop Grumman Corporation)
• Inventors: Messenger, Charles H., Heiss, Robert E. Jr.
• Primary Examiner(s): Shaw, Gareth D.
• Assistant Examiner(s): VON BUHR, MARIA N
• Application Number:
  US06/807,903
• Time in Patent Office: 2,114 Days
• Field of Search: 364/900 MS File, 364/200 MS File, 364/300, 364/418, 364/419, 364/728, 364/769, 382/39, 382/40, 382/57
• US Class Current: 1/1
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

A high speed search processor capable of performing a wide variety of search functions, including simple and complex searches, either within an entire text stream or within predefined fixed or sliding windows in the text stream. The processor is made up of multiple interconnected cells, each of which has a pattern register for storing part of a pattern to be searched for, a character register for storing a character of the data stream to be searched, a match register for storing a match value indicative of a match between the search pattern and the text stream, and match logic for modifying an incoming match value in accordance with conditions within the cell. The data stream and the search pattern are oppositely oriented, such that a first character of the search pattern is first encountered by a first character in the data stream, and the pattern is successively compared with an equal number of characters in the data stream as it is moved through the search pattern. The match logic includes means for detecting missing and extra characters in the data stream. The processor can therefore tolerate incorrect, missing or extra characters in the text stream, and can handle multiple levels of nesting and arbitrary boolean expressions within the search pattern. Another novel aspect of the processor is its ability to locate an enumerated subset of search terms or patterns within fixed or sliding windows.

Claims

1. A special-purpose search processor, comprising:

a plurality of serially-connected cells, each cell including

a pattern register for storing a character of a pattern to be searched for,

a character register for storing a character of a data stream to be searched,

match logic, including a comparator for generating a cell match signal by comparing the character stored in the character register with the character stored in the pattern register, and

a match register for storing a match value indicative of a match between a search pattern and the data stream, and for registering any mismatch indicated by the cell match signal;

means for connecting the character registers of the plurality of cells serially together to form a character line;

means for connecting the match registers of the plurality of cells serially together to form a match line;

means for initializing the cells to contain the search pattern; and

clock means for gating the data stream from cell to cell through the character line such that the search pattern and the data stream are oppositely oriented, and a first character of the search pattern is first encountered by a first character in the data stream;

and wherein characters in the search pattern are compared with characters in the data stream in a sequential manner, and match values are propagated along the match line in synchronism with movement of the data stream along the character line, to indicate exact and inexact matches between the search pattern and strings of characters in the data stream, and wherein inexact matches involve incorrect, missing or extra characters;

and wherein the match logic includes

means for loading a tolerance value onto the match line, at a selected cell position in the search pattern, for transmission onto the match line as an initial match value,

a delay match register connected to receive input from the match register and to provide output on the match line to a next cell in series, wherein the presence of the delay match register synchronizes movement of match values from cell to cell with movement of the data stream through successive potentially matching positions with respect to the search pattern,

means interposed between the match register and the delay match register, for selectively decrementing the match value as it is transmitted to the delay match register, whenever a non-match is detected in a cell, wherein presence of a non-zero match value on the match line is indicative of a match,

means for detecting missing characters in the data stream and adjusting the match value to record a degree of mismatch with the search pattern, wherein the means for detecting missing characters generates a first alternate match value based on an assumption that a character is missing from the data stream, and discards the first alternate match if the original match value is greater, and

means for detecting extra characters in the data stream and adjusting the match value to record a degree of mismatch with the search pattern, wherein the means for detecting extra characters generates a second alternate match value based on an assumption that there is an extra character in the data stream, and discards the second alternate match if the original match value is greater.

2. A special-purpose search processor as defined in claim 1, in which the means for detecting missing characters includes:

means for providing a parallel match value path bypassing the delay match register, after decrementing the match value in the means for selectively decrementing, to yield an alternative match value that would be obtained if a character were missing from the data stream; and

means for selecting between the parallel match value path bypassing the delay match register and a normal match value path through the delay match register, by comparing (a) the match value obtained from the means for providing a path bypassing the delay match register and (b) the match value obtained as an output of the delay match register, and choosing the greater of the two values (a) and (b) for output on the match line, selection of the value (a) being indicative of a missing-character condition.

3. A special-purpose search processor as defined in claim 1, in which the means for detecting extra characters includes:

means for providing a path feeding a match value back from output to input of the delay match register, and for decrementing the match value, to yield a match value that would be obtained if a current character were an extra character in the data stream; and

means for selecting between the feedback path and a normal input path from the means for selectively decrementing the match value, by comparing (a) the match value fed back from the output of the delay match register and (b) the match value that would normally be input to the delay match register, and choosing the greater of the two values (a) and (b) for input to the delay match register, selection of the value (a) being indicative of an extra-character condition.

4. A special-purpose search processor as defined in claim 1, in which the match logic further includes:

means responsive to a must-be-there flag, for clearing the tolerance value on the match line if there is no match in a cell in which the flag is set.

5. A special-purpose search processor as defined in claim 1, in which the match logic further includes:

means responsive to an invert-character flag in the cell, for inverting the match signal obtained by comparing the pattern register and the character register.

6. A special-purpose search processor, comprising:

a plurality of serially-connected cells, each cell including

a pattern register for storing a character of a pattern to be search for,

a character register for storing a character of a data stream to be searched,

match logic, including a comparator for generating a cell match signal by comparing the character stored in the character register with the character stored in the pattern register,

a match register for storing a match value indicative of a match between a search pattern and the data stream, and for registering any mismatch indicated by the cell match signal;

an accumulator register for storing a binary value derived from an accumulator register of an adjacent cell, and

accumulator logic for modifying a value contained in the accumulator register for output to a next cell, by combining the accumulator register with a selected condition of the cell, in accordance with a preselected logical function;

means for connecting the character registers of the plurality of cells serially together to form a character line;

means for connecting the match registers of the plurality of cells serially together to form a match line;

means for connecting the accumulator registers of the plurality of cells serially together to form a serial accumulator line;

means for initializing the cells to contain the search pattern; and

clock means for gating the data stream from cell to cell through the character line;

and wherein characters in the search pattern are compared with characters in the data stress in a sequential manner, and match values are propagated along the match line in synchronism with movement of the data stream along the character line, to indicate exact and inexact matches between the search pattern and strings of characters in the data stream, and wherein inexact matches involve incorrect, missing or extra characters;

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 for the storage and propagation of intermediate match signals;

and wherein 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 predefined segments of text.

7. A special-purpose search processor as defined in claim 6, in which:

the processor further includes a counter in each cell, and counter control logic for loading, incrementing and decrementing the counter; and

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 stored in the counter.

8. A special-purpose search processor as defined in claim 7, in which:

the means for loading the counter is responsive to detection of segment boundaries, whereby the counter is reset at the start of each new segment of text, to indicate the number of times that a search pattern string is to be located within the segment, and a desired search is thereby reinitiated at each new segment of text.

9. A special-purpose search processor as defined in claim 7, wherein:

the search processor is used to locate a desired subset of at least n terms of a set of m search terms within a specified text segment;

each cell includes an increment register and a decrement register, the increment register of each of the cells being serially connected to from an increment line and the decrement register of each of the cells being serially connected to form a decrement line;

the pattern registers are configured to define the m search terms and to provide a match value on a selected line indicative of the start of a text segment;

the match value indicative of the start of a text segment is employed to load the counter with a count of one in a counter cell immediately following each sequence of cells of which the pattern registers define a search term;

a matching search term causes decrementing of the counter in the next immediately following counter 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" output on the increment line whenever the accumulator becomes a "1", and a "1" output on the decrement line whenever the accumulator line becomes a "0";

a final cell following the m search terms functions as an integrator, having a counter initially set to a 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.

10. A special-purpose search processor as defined in claim 9, and further including:

logic means associated with the increment and decrement lines, for avoiding possible collision between "1" values placed on the increment and decrement lines by cells associated with different search terms.

11. A special-purpose search processor as defined in claim 7, wherein:

the search processor is used to locate a combination of search terms within a sliding window of n text segments;

a sequence of cells corresponding to each search term generates a non-zero match value on the match line when a match is found for the search term, and this match value is employed to load the counter with n in the cell immediately following a sequence of cells of which the pattern registers define the search term;

cells immediately preceding sequences of cells of which the pattern registers define the search terms are employed to detect segment boundaries and to generate match values 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 n successive text segments.

12. A special-purpose search processor as defined in claim 11, and further including:

means for reducing in number the match signals obtained from the processor.

13. A special-purpose search processor as defined in claim 12, in which:

the means for reducing the number of match signals includes means for ANDing the match values with selected ones of the segment boundary match values saved on one of the additional lines.

14. A special-purpose search processor as defined in claim 11, and further including:

means for counting the number of occurrences of each of the search terms, to permit detection of enumerated search terms within a sliding window of n text segments.

15. A method of searching for selected patterns in a text stream, using a plurality of serially-connected comparison cells, the method comprising:

initializing each cell to contain a pattern character in a pattern register and various control flags, the pattern characters of the cells together forming a serial string of characters defining a search pattern;

applying a clocking signal to the cells to cause propagation of the text stream from cell to cell along a character line formed by a serial connection of character registers in the respective cells, wherein the search pattern and the text stream are oppositely oriented, and a first character of the search pattern is first encountered by a first character in the text stream;

comparing the character register and the pattern register in each cell, on each application of the clocking signal, to generate cell match signals indicative of matching character and pattern registers;

loading an initial match value, referred to as a tolerance value, onto a match line connecting the cells, at a selected cell location, the tolerance value being indicative of the degree of mismatch that will be tolerated between the text stream and the search pattern;

propagating match values from cell to cell along the match line;

selectively modifying the match value in each cell in response to the result of the comparing step; and

outputting a match result indicative of the location of matching data in the text stream;

wherein the step of modifying the match value includes decrementing the value on detection of incorrect, missing or extra characters in the text stream;

storing a first match result associated with a first search term of the search pattern on an additional line connecting the cells, wherein the storing step is performed in a cell corresponding to an end of the first search term;

generating a second match result relating to a second search term of the search pattern, wherein the generating step produces the second match result from a cell corresponding to an end of the second search term;

logically combining the first and second match results in a cell corresponding to a position downstream of the first and second search terms, for output from the serially connected cells;

detecting boundaries of predefined text segments within the text stream, using cells of which the pattern registers contain selected text boundary characters;

generating enabling signals in the cells in the step of detecting boundaries; and

applying the enabling signals to other cells, thereby enabling search functions to be performed only within a fixed window of one text segment defined by the detected boundaries.

16. A method for searching a stream of text for a search pattern, comprising:

first storing a search pattern of textual characters in a serially connected plurality of comparison cells;

shifting the text stream character-by-character through the comparison cells in synchronism with a clocking cycle, wherein the search pattern and the text stream are oppositely oriented, and a first character of the search pattern is first encountered by a first character in the text stream;

comparing characters in the search pattern with characters in the text stream at each position of the text stream as it is shifted through the comparison cells;

producing cell match signals in the comparison cells as a result of the comparing step;

setting a match value initially to a selected tolerance value in a selected one of the cells;

receiving a match value from a neighboring cell at the same time as a text stream character;

decrementing the received match value if there is not cell match signal in the cell;

storing the received and possibly decremented match value for one clocking cycle;

then transmitting the stored match value to the next neighboring cell in sequence, wherein the match values are propagated through the comparison cells at half the rate of shifting the text stream through the comparison cells;

detecting exact matches between the search pattern and strings of characters in the text stream, by detecting match values that are propagated out of the cells with a value not diminished from the tolerance value; and

detecting inexact matches in the form of incorrect, extra or missing characters in each character string compared with the search pattern, wherein the detection of incorrect, extra and missing characters is performed simultaneously and in each cell, and further includes the steps of selectively decrementing a match value in each of three alternate paths corresponding to the detection of incorrect, extra and missing characters, and selecting the greatest match value of three for transmission to the next neighboring cell in sequence.

17. A method as defined in claim 16, and further including the steps of:

storing a first match result associated with a first search term of the search pattern, and generated in a cell corresponding to the end of the first search term, on a match line connecting the cells;

generating a second match result relating to a second search term of the search pattern, in a cell corresponding to the end of the second search term; and

logically combining the first and second match results for output from the serially connected cells.

18. A method as defined in claim 17, and further including the step of:

generating additional match results associated with additional search terms of the search pattern, which may be logically combined with the first and second search terms in a nested arrangement.

19. A method as defined in claim 17, and further including the step of:

counting occurrences of selected search terms, in counter cells associated with the selected search terms, to provide for the searching of enumerated conditions within the text stream.

20. A method as defined in claim 18, and further including the step of:

counting occurrences of selected search terms, in counter cells associated with the selected search terms, to provide for the searching of enumerated conditions within the text stream.

21. A method as defined in claim 17, and further including the steps of:

detecting boundaries of predefined text segments within the text stream, using cells in which the boundaries are stored as part of a search pattern; and

generating enabling signals in the cells in the step of detecting boundaries;

applying the enabling signals to other cells, thereby enabling search functions to be performed only within a fixed window of one text segment defined by the detected boundaries.

22. A method as defined in claim 18, and further including the steps of:

detecting boundaries of predefined text segments within the text stream, using cells in which the boundaries are stored as part of a search pattern; and

generating enabling signals in the cells in the step of detecting boundaries;

applying the enabling signals to other cells, thereby enabling search functions to be performed only within a fixed window of one text segment defined by the detected boundaries.

23. A method as defined in claim 19, and further including the steps of:

detecting boundaries of predefined text segments within the text stream, using cells in which the boundaries are stored as part of a search pattern; and

generating enabling signals in the cells in the step of detecting boundaries;

applying the enabling signals to other cells, thereby enabling search functions to be performed only within a fixed window of one text segment defined by the detected boundaries.

24. A method as defined in claim 20, and further including the steps of:

detecting boundaries of predefined text segments within the text stream, using cells in which the boundaries are stored as part of a search pattern; and

generating enabling signals in the cells in the step of detecting boundaries;

applying the enabling signals in the cells in the step of detecting boundaries;

applying the enabling signals to other cells, thereby enabling search functions to be performed only within a fixed window of one text segment defined by the detected boundaries.

25. A method as defined in claim 17, and further including the steps of:

detecting boundaries between predefined text segments within the text stream, using cells of which the pattern registers contain selected text boundary characters;

counting text segments in cells set up as counting cells, to determine whether a search term has appeared within a specified number of text segments;

counting occurrences of selected search terms within text segments, using further cells set up as counting cells; and

generating a match signal only when specified search terms have appeared in combination within the specified number of text segments.

26. A method as defined in claim 25, and further including the step of:

reducing in number the match signals generated, by ANDing the match signals with a signal derived from the boundaries of the predefined text segments.

27. A special purpose search processor for searching a stream of text for specified search patterns, the processor comprising:

means for first storing a search pattern of textual characters in a serially connected plurality of comparison cells;

means for shifting the text stream character-by-character through the comparison cells in synchronism with a clocking cycle, wherein the search pattern and the text stream are oppositely oriented, and a first character of the search pattern is first encountered by a first character in the text stream;

means for comparing characters in the search pattern with characters in the text stream at each position of the text stream as it is shifted through the comparison cells, and producing cell match signals in the comparison cells;

means for setting a match value initially to a selected tolerance value in a selected one of the cells;

means for receiving a match value from a neighboring cell at the same time as a text stream character;

means for decrementing the received match value if there is no cell match signal in the cell;

means for storing the received and possibly decremented match value for one clocking cycle;

means for transmitting the stored match value to the next neighboring cell in sequence, wherein the match values are propagated through the comparison cells at half the rate of shifting the text stream through the comparison cells wherein exact matches between the search pattern and strings of characters in the text stream are indicated by match values that are propagated out of the cells with a value not diminished from the tolerance value, and inexact matches are indicated by diminished match values; and

means for detecting inexact matches in the form of extra or missing characters in each character string compared with the search pattern, wherein the detection of extra and missing characters is performed simultaneously with the detection of incorrect characters, and in each cell, and further includes means for computing two additional match values in each cell, based on the detection of an extra or missing character in the text stream, and means for selecting the greatest match value from the stored match value and the two additional match values, for transmission to the next neighboring cell in sequence.

28. A special-purpose processor as defined in claim 27, 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 connected cells.

29. A special-purpose processor as defined in claim 28, 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.

30. A special-purpose processor as defined in claim 28, and further including:

means for counting occurrences of selected search terms, to provide for the searching of enumerated conditions within the text stream.

31. A special-purpose processor as defined in claim 29, and further including:

means for counting occurrences of selected search terms, to provide for the searching of enumerated conditions within the text stream.

32. A special-purpose processor as defined in claim 28, and further including:

means for detecting boundaries of predefined text segments within the text stream; and

means for enabling search functions to be performed only within a fixed window of one text segment.

33. A special-purpose processor as defined in claim 29, and further including:

means for detecting boundaries of predefined text segments within the text stream; and

means for enabling search functions to be performed only within a fixed window of one text segment.

34. A special-purpose processor as defined in claim 30, and further including:

means for detecting boundaries of predefined text segments within the text stream; and

means for enabling search functions to be performed only within a fixed window of one text segment.

35. A special-purpose processor as defined in claim 31, and further including:

means for detecting boundaries of predefined text segments within the text stream; and

means for enabling search functions to be performed only within a fixed window of one text segment.

36. A special-purpose processor as defined in claim 28, and further including:

means for detecting boundaries between predefined text segments within the text stream;

means for counting text segments to determine whether a search term has appeared within a specified number of text segments;

means for generating a match signal only when specified search terms have appeared in combination within the specified number of text segments.

37. A special-purpose processor as defined in claim 36, and further including:

means for reducing in number the match signals generated, by ANDing the match signals with a signal derived from the boundaries of the predefined text segments.

38. A special-purpose search processor, comprising:

a plurality (n) of serially connected pattern registers for storing a search pattern;

an equal plurality (n) of serially connected character registers, each for storing a character of a data stream to be searched;

means for shifting the data stream being searched, character-by-character through the serially connected plurality of character registers;

an equal plurality (n) of serially connected match registers, for storing match value input at a first of the match registers;

means for shifting match values along the serially connected match registers, at half the rate at which the data stream characters are shifted through the character registers, whereby a match detected between a character in the data stream and a character in the search pattern is preserved in the form of a match value that is positioned for use in a subsequent comparison between the next following character in the data stream and the next following character in the search pattern; and

match logic, including a plurality of comparators for comparing the contents of the character registers with the contents of the corresponding pattern registers, and modifying the contents of the corresponding match registers upon detection of a mismatch, whereby the match values passed through the plurality of match registers are indicative of exact and inexact matches between the search pattern and strings of characters in the data stream;

and wherein the match logic includes means for detecting inexact matches in the form of extra or missing characters in each character string compared with the search pattern, wherein the detection of extra and missing characters is performed simultaneously with the detection of incorrect characters, and in each cell, and further includes means for computing two additional match values in each cell, based on the detection of an extra or missing character in the text stream, and means for selecting the greatest match value from the stored match value and the two additional match values, for transmission to the next neighboring cell in sequence.