System for parallel string search with a function-directed parallel collation of a first partition of each string followed by matching of second partitions

• US 5,497,488 A
• Filed: 03/13/1995
• Issued: 03/05/1996
• Est. Priority Date: 06/12/1990
• Status: Expired due to Fees

• Current Assignee: Hitachi, Ltd., Hitachi Maxell Limited (Hitachi, Ltd.)
• Original Assignee: Hitachi, Ltd., Hitachi Maxell Limited (Hitachi, Ltd.)
• Inventors: Matsushima, Hitoshi, Noguchi, Kouki, Kato, Kanji, Hayashi, Takehisa, Akizawa, Mitsuru
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): AMSBURY, WAYNE P
• Application Number:
  US08/402,560
• Time in Patent Office: 358 Days
• Field of Search: 395/600, 364/419.13
• US Class Current: 1/1
• CPC Class Codes: G06F 16/90335 Query processing
• CPC Class Codes: G06F 16/90339 by using parallel associative memories or content-addressable memories
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: G06F 2207/025 String search, i.e. pattern matching, e.g. find identical word or best match in a string
• CPC Class Codes: G06F 7/02 Comparing digital values G06F7/06, G06F7/22, G06F7/38 take precedence
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

A character string search arithmetic operation is performed at high speed with a small hardware scale processing module, such as a symbol string search module. The search module is connected to a CPU through address and data buses and includes a function definition section for defining a function of the apparatus in accordance with a command from the CPU, a data input/output section for receiving a symbol string to be searched through the data bus and for outputting the result of a search. A search processing section performs the search based on a function defined by the function definition section. A symbol string to be searched for, which is internally stored, is compared with the symbol string data input to the module'"'"'s data input/output means. A condition holding section holds data indicative of an internal condition corresponding to the result of the search processing. Thereby, the CPU and the symbol string search module can perform the search at high speed.

Claims

1. A symbol string search apparatus for making a decision of whether or not a symbol string to be searched for exists in a symbol string to be searched, which is composed of symbols represented by codes, in a leading collation processing of a search to be combined with a posterior collation processing of the search, the symbol string search apparatus being connected to a CPU through an address bus and a data bus and comprising:

function definition means connected to said data bus, for receiving from said CPU a command defining a function to be performed by the symbol string search apparatus, said function definition means holding said command until it receives a next command from said CPU;

data input/output means for receiving a symbol string to be searched through said data bus and for providing a search result output;

search processing means for performing said leading collation processing based on a function defined by said function definition means by matching the symbol string to be searched for, which is already stored in said search processing means, with the symbol string to be searched which is input to said data input/output means, said leading collation processing being performed plural times for a plurality of symbol strings to be searched while said function definition means is holding said command; and

condition holding means for holding data indicative of an internal condition corresponding to the result of the search, the data held in said condition holding means being accessible by said CPU.

2. A symbol string search apparatus according to claim 1, wherein the symbol string search apparatus is formed on a single semiconductor chip.

3. A symbol string search apparatus according to claim 1, wherein at least said CPU, said symbol string search apparatus, and said address bus and said data bus for connecting said CPU and said symbol string search apparatus are formed as a microcomputer on a single semiconductor chip.

4. A symbol string search apparatus according to claim 3, further comprising a RAM and a ROM which are also formed on said single semiconductor chip, whereby a single-chip microcomputer is provided.

5. A symbol string search system for making a decision of whether or not a symbol string to be searched for exists in a symbol string to be searched, which is composed of symbols represented by codes, in a leading collation processing of a search to be combined with a posterior collation processing of the search, comprising:

a host CPU system; and

a secondary storage system for storing said symbol string to be searched in a storage medium, said secondary storage system including;

a search processor which has function definition means for receiving from said host CPU system a command defining a function to be performed by the symbol string search system, said function definition means holding said command until a next command is received from said host CPU system,

data input/output means for receiving the symbol string to be searched which is stored in said storage medium and for providing a search result output to said host CPU system,

search processing means for performing said leading collation processing based on a function defined by said function definition means by matching a symbol string to be searched for, which is received from said host CPU system, with the symbol string to be searched, which is input to said data input/output means;

said leading collation processing being performed plural times for a plurality of symbol strings to be searched while said function definition means is holding said command, and

condition holding means for holding data indicative of an internal condition corresponding to the result of the search, the data held in said condition holding means being accessible by said host CPU system.

6. A symbol string search system according to claim 5, wherein an extended command of said host CPU system includes a symbol string search command.

7. A symbol string search system according to claim 5, wherein said host CPU system includes a generalized bus for control of said secondary storage system and an extended bus for performing a symbol string search function in combination with said generalized bus, said host CPU system and said secondary storage system being connected by said generalized bus and said extended bus.

8. A symbol string search apparatus for making a decision of whether or not a symbol string to be searched for exists in a symbol string to be searched, which is composed of symbols represented by codes, in a leading collation processing of a search to be combined with a posterior collation processing of the search, the symbol string search apparatus being connected to a CPU through an address bus and a data bus and comprising:

function definition means connected to said data bus, for receiving from said CPU a command defining a comparison function to be performed by the symbol string search apparatus, said function definition means holding said command until a next command is received from said CPU;

input means for receiving a symbol string to be searched through said data bus;

means for masking data in said input means on a bit basis;

means for making a positional interchange of the data in said input means on a byte basis;

a content addressable memory for storing a symbol string to be searched for and comparing the stored symbol string to be searched for with the symbol string to be searched which has been subjected to the positional interchange by said data path interchange means to perform a comparison function therebetween as defined by said command, said comparison being performed plural times for a plurality of symbol strings to be searched while said function definition means is holding said command;

a comparison condition memory for designating a condition for the comparison in said content addressable memory that defines when a relationship between the symbol string to be searched and the symbol string to be searched for is determined to be matching;

comparison result analyzing means for analyzing words matched from the result of the comparison in said content addressable memory;

matching signal separating means for providing an output of matching signals of the words matched one by one;

an output data memory having an access address designated by said matching signal;

search result output means for providing an output of the content of said output data memory through said data bus;

non-hit data holding means for holding data which is to be output to said search result output means when said output data memory is not accessed; and

condition holding means for holding an internal condition of the symbol string search apparatus, the internal condition held in said condition holding means being accessible by said CPU.

9. A symbol string search apparatus according to claim 8, wherein said input means includes a first group of input means having a data path to said content addressable memory and a second group of input means having no data path to said content addressable memory, and said input means successively shifts data input from said second group of input means to said first group of input means while being passed through each input means so that the symbol string to be searched which is stored in said first group of input means is transferred to said content addressable memory.

10. A symbol string search apparatus according to claim 9, wherein the amount of shift of the symbol string to be searched in said input means is made in units having a size selected from one bit, one byte and two bytes.

11. A symbol string search apparatus according to claim 9, wherein the amount of shift is designated by a command set into said function definition means.

12. A symbol string search apparatus according to claim 9, wherein when the symbol string to be searched which is stored in said first group of input means is transferred to said content addressable memory, the arrangement of data is changed in units of one byte.

13. A symbol string search apparatus according to claim 12, wherein a manner of the change of the arrangement of the data of the symbol string to be searched which is stored in said first group of input means, is designated by a command set into said function definition means.

14. A symbol string search apparatus according to claim 8, wherein when the symbol string to be searched is written into said input means, a search processing sequence is activated in accordance with the setting by said function definition means and either data stored in said output data memory or data stored in said non-hit data holding means is outputted to said search result output means.

15. A symbol string search apparatus according to claim 14, wherein when the symbol string to be searched is written, input means for activating the search processing sequence set in said function definition means is designated by a command set into said function definition means.

16. A symbol string search apparatus according to claim 8, wherein the condition of comparison between the symbol string to be searched and the symbol string to be searched for is set in units of one word for the symbol string to be searched which is stored in said content addressable memory, and said condition of comparison includes a condition under which the matching is determined in the case where the symbol string to be searched and the symbol string to be searched for are equal to each other, a condition under which the matching is determined in the case where they are not equal to each other, a condition under which the matching is always determined irrespective of a relationship therebetween, and a condition under which a mismatching is always determined irrespective of a relationship therebetween.

17. A symbol string search apparatus according to claim 8, further comprising an output terminal or interface means for transferring the content of said condition holding means to said CPU directly.

18. A symbol string search apparatus according to claim 8, wherein in the case where the matching between the symbol string to be searched and the symbol string to be searched for is detected, an interruption request signal is outputted.

19. A symbol string search apparatus according to claim 18, wherein whether or not the interruption request signal should be output in the case where the matching between the symbol string to be searched and the symbol string to be searched for is detected, is designated by a command set into said function definition means.

20. A symbol string search apparatus according to claim 18, wherein when the content of said output data memory is output to said search result output means in accordance with a signal indicative of the matching, whether or not a part of said content should be substituted by internal information of the symbol string search apparatus is designated by a command set into said function definition means.

21. A symbol string search apparatus according to claim 8, wherein a mask is set to the same bit position with respect to units of one byte or two bytes for each symbol string to be searched for, which position is stored in said content addressable memory.

22. A symbol string search apparatus according to claim 21, wherein the same bit position to which the mask is set is designated by a command set into said function definition means.

23. A symbol string search apparatus according to claim 8, wherein the contents of said content addresable memory, said comparison condition memory and said output data memory are accessed from said CPU.

24. A symbol string search apparatus according to claim 8, wherein the symbol string search apparatus is formed on a single semiconductor chip.

25. A symbol string search apparatus according to claim 8, wherein at least said CPU, said symbol string search apparatus, and said address bus and said data bus for connecting said CPU and said symbol string search apparatus are formed as a microcomputer on a single semiconductor chip.

26. A symbol string search apparatus according to claim 25, further comprising a RAM and a ROM which are also formed on said single semiconductor chip, whereby a single-chip microcomputer is provided.

27. A symbol string search system for making a decision of whether or not a symbol string to be searched for exists in a symbol string to be searched, which is composed of symbols represented by codes in a leading collation processing of a search to be combined with a posterior collation processing of the search, comprising:

a host CPU system; and

a secondary storage system for storing said symbol string to be searched in a storage medium, said secondary storage system including a search processor which has input means for receiving a symbol string to be searched which is stored in said storage medium, means for masking data in said input means in units of one bit, data path interchange means for making a positional interchange of the data in said input means in units of a byte, a content addressable memory for storing a symbol string to be searched for which is received from said host CPU system and for performing said leading collation processing by comparing the stored symbol string to be searched for with the symbol string to be searched, which has been subjected to the positional interchange by said data path interchange means, a comparison condition memory for designating a condition for the comparison in said content addressable memory that defines when a relationship between the symbol string to be searched and the symbol string to be searched for is determined to be matching, comparison result analyzing means for analyzing words matched from the result of the comparison in said content addressable memory, matching signal separating means for providing an output of matching signals of the words matched one by one, an output data memory having an access address designated by said matching signal, search result output means for providing an output of the content of said output data memory to said host CPU system, non-hit data holding means for holding data which is to be output to said search result output means when said output data memory is not accessed, comparison condition definition means for defining a condition of the comparison performed by the symbol string search system, and condition holding means for holding an internal condition corresponding to the result of the search.

28. A symbol string search system according to claim 27, wherein an expanded command of said host CPU system includes a symbol string search command.

29. A symbol string search system according to claim 27, wherein said host CPU system includes a generalized bus for control of said secondary storage system and an extended bus for performing the leading collation processing in combination with said generalized bus, said host CPU system and said secondary storage system being connected by said generalized bus and said extended bus.