System for parallel string search with a function-directed parallel collation of a first partition of each string followed by matching of second partitions
First Claim
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.
0 Assignments
0 Petitions
Accused Products
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.
-
Citations
29 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. - View Dependent Claims (2, 3, 4)
-
-
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, andcondition 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. - View Dependent Claims (6, 7)
-
-
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. - View Dependent Claims (9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26)
-
-
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. - View Dependent Claims (28, 29)
-
Specification