JPH03131969A - Method and device for retrieving code string - Google Patents

Abstract

(57) [Summary] This bulletin contains application data before electronic filing, so abstract data is not recorded.

Description

DETAILED DESCRIPTION OF THE INVENTION [Field of Industrial Application] The present invention is applicable to high-speed data retrieval processing, particularly document data search through character string retrieval, in information processing systems including non-numeric data processing such as databases and document filing systems. The present invention relates to a symbol string search method suitable for full text search, a device for implementing the method, and a semiconductor integrated circuit as the device.

[Conventional technology]

As the storage capacity of information processing systems increases year by year, the proportion of processing that handles non-numeric data such as document data is increasing. Against this background, the importance of processing to quickly and thoroughly search for desired documents and data from large-capacity databases is increasing.

Conventionally, when searching for single document data, many methods have been used to use additional information such as keywords and classification codes.

However, it is difficult to precisely express detailed search conditions using only keywords and classification codes, making it difficult to narrow down the search sufficiently. Therefore, with this method, documents that were not intended by the searcher are also included as search noise. Therefore, in the end, the searcher must directly read the text and select the document data, which poses a problem in that the efficiency of the search process cannot be improved. Furthermore, as the amount of document data increases, the amount of work required for indexing to add keywords and classification codes increases, causing delays in document data registration. Furthermore, the meanings of keywords and classification codes may change over time and become obsolete, making it difficult to keep databases up-to-date.

To overcome these problems, a method (hereinafter referred to as full-text search) has been proposed in which the main text of a document is scanned and the content is compared with keywords arbitrarily set by the user. .

FIG. 34 shows an example of a character string search system using this full text search. (R, L.

Haskin & El, Ni, Holler: “Operational Characteristics of Hardware Paste Patterns Matscher, Ni, C.
M Transactions on Database Systems, Volume 8, No. 1, 1983 (R,L, Has
kin and L, A.

)1o11aar: ”0perimental C
haracteristics of a Hardware
re-Based Pattern Match
r”, ACM Trans.

on Database Systems, Vol. 8
．． No. 1, 1983)) The string search system 300 is connected to a host computer and exchanges search requests 320 and search results 324 through communication. When a search request 320 is sent from the host computer, the search control means 3
10 receives this, analyzes it, and 1 character string matching means 313
and sends the search control information 321 to the compound condition determination means 314. The search control means 310 also includes a storage device control means 311.
is controlled to transfer the character string data 322 stored in the character string storage means 312 to the character string collation means 313.

The character string matching means 313 uses the input character string data 322
is compared with a character string set in advance as search control information 321, and when a corresponding character string is detected, the detected information 323 is output to the compound condition determining means 314. The compound condition determining means 314 checks whether the detection information 323 matches a compound condition regarding the positional relationship between character strings in the search request, etc., which is set in advance as the search control information 321. If there is a match, the identification information and document contents of the corresponding document data are output as a search result 324, which is sent to the host computer.

One of the full text searches performed by the character string matching means 313 is a method using a finite automaton. With this method, a search can be performed with one text scan regardless of the number of keywords.

(Nee, Bui, 21 Ho and M, Jay.

Kolatszczyk: “Efficient String Matching”, Communications Knee Gem, Volume 18, No. 6, 1975 (A, V.

Aho and M, J, Corasick:
”Efficient String Matchin
g”, Comra, ACM, Vol. 18.N.
o, 5.1975)) This method doesn't ca
It is also possible to perform various ambiguous searches, such as searches that include re characters and searches that include incorrect characters.

This is an effective method for full-text searches. Regarding the algorithm and its implementation means for processing full text search at high speed using this finite automaton, please refer to
No. 311530.

By the way, as described in Japanese Patent Application Laid-Open No. 63-311530, in a full text search using a conventional finite automaton, state transitions in each cycle are always performed with reference to a state transition table. Since the capacity of this state transition table is generally large, it is usually stored in a memory on a separate chip from the semiconductor integrated circuit that controls the execution of the finite automaton. For this reason, external memory access from the automaton execution control means is required for each cycle, which impedes improvement in processing speed.

Therefore, the inventors of the present invention first proposed a method (high-speed head matching method) that improves the total processing speed of a single string search by speeding up the frequently executed part of the search string matching process. The application has been filed. (Patent application Hei 1-1
50401, filed on June 15, 1999) In Figure 35,
A block diagram of this method is shown.

This is the frequently referenced part of the state transition table.

In other words, this is a method in which frequently accessed data in the memory that stores tables is placed on the same chip as the finite automaton execution means. In other words, the state transition table is hierarchized and divided into internal and external parts of the finite automaton execution means. In a sense, this seems to be an analogy to the concept of conventional cache memory, but
It differs essentially from cache memory in that data is not moved between different storage hierarchies during the matching process. Therefore, in the matching process, by setting the frequently accessed content of the state transition table in the parallel comparator so that it is equivalent to this content, during the search process, the substring and text data set in the parallel comparator are Most of the processing can be done just by comparing. In other words, most of the processing can be performed without memory access, resulting in a significant improvement in processing speed.

By the way, in the method we proposed earlier.

The things that can be set in the parallel comparator are the substring itself and the don't ca
It was only the one that set re. However, in actual matching processing, "matching that targets all characters other than specific characters" (negative condition) may be performed. An example of this is shown below.

For example, for the specified search string "大过凰′",
A case will be described in which a search is performed that allows one character error in addition to a normal search string. That is, this is a case where one character is allowed to be replaced, one character is inserted, and one character is omitted.

here, "All letters except (large)" are i (large).

“All characters other than (quantity)” are − (yō), “all characters other than (quantity)” are 5 (quantity), and “any one character (do
"Don't care settings)"? , in order to perform a one-character error-tolerant search for the set character string ``large capacity'', K: large capacity, 2: large capacity, 1 (quantity), K3: large - (volume), Number 5 for quantity (large) 5 for capacity: capacity? 6 for quantity: large? You have to search for 9 character strings: 7 for capacity: δ for large quantity: 9 for large quantity: 9 character strings for capacity. When a finite automaton that searches these character strings by full text search is generated (as shown in FIG. 4, which will be described later), input of characters including negative conditions will appear as state transition conditions. (
This is called an exclusive transition. ) Therefore, the parallel comparator must be able to detect such conditions. In this way, in order to implement an ambiguous search that allows erroneous characters, it is necessary to provide the parallel comparator with a function of setting a negative condition.

Furthermore, by making it possible to set a negative condition, it becomes possible to suppress unnecessary search results, that is, so-called search noise.

For example, consider a search for text containing the words "metal atom" and "conductor."

If the first two characters are set as a partial string to the parallel comparator, "metal""conductor" will be set and matched against the text. However, during this matching, the part "metal" Text containing "nonmetal" is detected for a character string, or text containing "semiconductor" for a partial string "conductor" is detected.These "nonmetal" and "semiconductor" are respectively set parts. Even though it contains the string ``metal''``conductor'', it is a different string with a different meaning.Depending on the purpose of the search, these may be unnecessary search results during a full-text search. This appears as so-called search noise.

Therefore, in order to remove such search noise, a negative condition may be used to set a strongly limited substring as described below.

``Metal 2 → 1 (non-)metal'' ``Pacific conductor'' → - (semiconductor)'' This can prevent ``non-metal I+, 14 semiconductor'' from appearing as search noise. There are many other examples like this. Therefore, negation “numerical processing” →
1 (Non) Numerical processing “゛′Defined word” → “− (Non)
By being able to set "definition word" conditions, search noise can be suppressed.

However, in the past, there was no function to set this negative condition, so 1
There was a problem in that it was not possible to perform character error-tolerant searches or limited searches to suppress noise.

[Problem to be solved by the invention]

In document retrieval by full text search using an automaton, there is a method of speeding up the processing by reducing the frequency of data input/output between the memory in which the state transition table is stored and the automaton execution means compared to the conventional method. When executing this method, a semiconductor integrated circuit that enables ambiguous searches such as a search in which the don't care character is set in the search string or an error-tolerant search in which a negative condition is set in the search string is used. The purpose is to provide.

[Means to solve the problem]

In order to achieve the above purpose, a partial character string is obtained by extracting a part of multiple character strings (hereinafter referred to as search character strings) to be searched from among the 5 document data, and a character string in which document data is arranged in order from the first character (hereinafter referred to as search character string) In a semiconductor integrated circuit in which a parallel comparator that performs high-speed processing of matching with a string (called a string to be searched) in parallel is provided at the front stage of the automaton execution means, don 't
By providing a means for setting care and a means for setting a negative condition, a fast and highly flexible ambiguous search has been realized.

[Effect]

FIG. 1 shows a block diagram explaining the present invention in detail and an automaton of the processing executed here.The present invention will be explained in detail using these figures.

The present invention has an input buffer 10 as shown in FIG. 1(a).
The searched character string 101 taken in via 2 is input to the parallel comparison section 10 and the finite automaton execution section 11 at the same time. Then, in the parallel comparison unit 10, the first matching automaton 1
Perform the head matching process corresponding to step 3 (matching process of the first substring of the divided search string), and perform the backward matching process corresponding to the backward matching automaton 14 (matching process of the remaining substrings of the split search string). ) is executed by the finite automaton execution unit 11. After each process is performed, the search results 111 (corresponding search string and position information indicating where it is located in the document data) are sent to the output buffer 10.
5 to the outside. In addition, the conceptual diagram of the automaton executed during this process is shown in Figure 1(b).
Shown below. The numbered circles represent each state, the numbers inside represent the state number, and the size of the circle relatively indicates the rate of state transition frequency to each state. Arrows represent state transitions, and the initial state is O.

In the present invention, a valid flag register 400, which is a means for making it possible to set "don't care" at any position of a partial string set in the parallel comparator 106, and a negative condition, which is a means for making it possible to set a negative condition, are provided. Flag register 4
10 was newly installed in the parallel comparison unit 10 that performs the head verification process.

When the parallel comparator 106 performs head matching processing, these are referred to for processing. This increases the flexibility in the head matching process, so the parallel comparison unit 1o
Even in the finite automaton execution unit 11, it is possible to realize more advanced ambiguous searches such as single character error searches and limited searches. In addition, without erasing or rewriting a partial string, it is possible to discard or restore a search string by operating only the don't care setting means or negative condition setting means, and to make the word length of a partial string variable. [Examples] Examples of the present invention will be described below.

A block diagram of the first embodiment of the present invention is shown in FIG.

In this embodiment, input buffers 1o2. Parallel comparator 106. Valid flag register 400. Negative condition flag register 410 (hereinafter referred to collectively as collation control register 40), code converter 107. Status code queue 109. Input selector 108. Automaton execution means 1042 Character code buffer 103° State transition table 110. It consists of an output buffer 105°.

The document data in the database is input to the input buffer 1 in single character or multiple character units as the searched character string 101.
02. The character string to be searched 101 has its data width converted by an input buffer 102, and is simultaneously input to a parallel comparator 106 and an input character code buffer 103.

In the parallel comparator 106, the data width of the input character code 130 does not necessarily match the data width of the searched character string.

The first part of the search string is stored in advance as a partial string, one character from the input buffer 102.

Alternatively, each time multiple characters are sent, all substrings of the search string are matched at the same time.

At this time, the conditions set in the valid flag register 400 and the negative condition flag register 410 are referred to as matching conditions for the partial character string. When a match with a substring of the search string is detected, a match signal 131 is asserted. This match signal is converted by the code converter 107 into a status code 132 indicating that each partial character string has been detected. Status code 132 output from code converter 107
is selected by the selector 108 and stored in the status code queue 109 (hereinafter referred to as the current status).

On the other hand, the character code data in the character code buffer 103 is processed by the finite automaton execution means 104 at the same time as the parallel comparison described above. The character code buffer 103 is for eliminating the gap between the character code transfer speed of the input buffer 102 and the processing speed of the finite automaton execution means 104. Inputs to the finite automaton execution means 104 are the character code data inside the character code buffer 103 and the current state code 134 stored in the state code queue 109. The finite automaton execution means 104 takes out the current state code 134 from the state code queue 109 and generates the access address 137 of the state transition table 110 from this and the character code data 135 in the character code buffer 103. The content of the corresponding address is the transition destination 1 of the current state of the finite automaton.
38 (hereinafter referred to as the next state), which is selector 1.
08 and stored in the status code queue 109. When the current status code is processed in this manner, the next character code data is taken in from the character code buffer 103.

In the process of repeating such a series of processes, when the state transition result 138 of the automaton becomes a state indicating that a search character string has been detected, it means that a matching character string has been detected. Then, search results 111 corresponding to these are written to the output buffer 105. Note that when a specific code is inserted as an end code into the character string to be searched, the parallel comparator detects the end code and forcibly ends the search process.

Any desired end code can be set in the parallel comparator.

The above series of processing is controlled by a control logic block. Therefore, the control logic block controls data transfer on the data bus between modules and forced termination of processing by detection of an end code.

Partial string and searched string 1 in parallel comparator 106
The collation control register 4o, which is referred to when collating with 01, functions as follows.

The valid flag register 400 is a don't-care function that, when set, makes the result of matching between the set character at the corresponding position and the input character valid, and when reset, the result of matching between the set character at the corresponding position and the input character always matches, regardless of the input character. As specified.

When set, the negative condition flag register 410 performs an enable output when the set character at the corresponding position and the input character match, and outputs a disable when the two do not match. Then, the logic of the comparison result is inverted, and when the two match, a disable output is performed, and when the two do not match, an enable output is performed.

By providing these collation control registers 40 in addition to the head collation method, it is possible to realize high-speed collation processing that enables highly flexible ambiguous search.

Next, a fuzzy search realized in the present invention will be explained based on an embodiment.

FIG. 3 shows an example of the development of a search string in the case where the search string is given as: abc and an ambiguous search is performed for this string that allows various single-character errors. Here, the negative condition setting is expressed as i'', and the don't care setting is expressed as 1'?''.

The expanded search string is 1 for exact match, K2 to 4 for K2 to 4.
replaces one character, inserts one character of 6 into 5~, K7~
9 is one character deleted. All of these need to be included in the search.

Figure 4 is a search symmetry, 1 to 9 in Figure 3.

This is an example of an automaton for searching from a searched character string.

Here, the numbered circles represent each state, and the numbers inside indicate the state number. The initial state is state O, and 2
A double circle indicates that a search string has been detected. The symbol below the double circle is a search string identifier corresponding to the search string to be detected. Further, arrows represent state transitions, and the state changes when the characters written above the arrows are input. When characters other than these are input, or when no transition destination is described, such as in a double circle state except for some, all transitions are made to the initial state 0.

(This is called a fail.) In the present invention, a partial string of the search string is set in the parallel comparator 106 prior to the search process.

Further, control information for controlling the state transition of the automaton expanded from the search string is also set in the state transition table 110.

Here, an example will be described in which the first two characters of an automaton are set as a partial string of a search string.

In Figure 4, the dotted line 81 divides the automaton into two.
0 indicates the division position of the automaton when the first two characters are set in the parallel comparator.

Therefore, transitions up to states 2, 9, 13, and 18 are executed by the parallel comparator 106, and subsequent transitions are executed by the finite automaton execution means 104 and the state transition table 110.

The latter half of the divided automaton is in state 2,9°13.
It can be seen as a set of four automata, each with 18 as its initial state. Parallel comparator 106 has state 0
A partial character string expanded to two characters is set, representing the transition conditions from to each of states 2, 9, 13, and 18. therefore.

For example, when “ab” is input, the state transition is O → 1 →
It becomes 2. In addition, the state transition when "PaC" is input is 0 → 1 → 9, and the state transition 0 → 1 due to 1'a" is the same as when 11 al, ++ is input.
11 The transition by C11 causes a branch transition to state 9. This state transition O → 1 → 9 can be regarded as a state transition of 0 → 11 → 9 due to the consecutive appearance of two characters as shown by the dotted line in the figure, so it is independent of "ab". All you have to do is set the substring `` to the parallel comparator.

FIG. 5 is a conceptual diagram in which the automaton shown in FIG. 4 is constructed by a parallel comparator 106 and an automaton generated for backward comparison. A match signal from parallel comparator 106 transitions the automaton from its initial state. After that, the state transitions according to the state transition table, and the searched character string 101 is
Note that state 13 is fired only when the matching results of both 11 a, btt 14 a, and Cjl and the searched string match (represented by & in the figure). It will be done.

In this way, the entire process is equivalent to executing the automaton shown in FIG. 4.

FIG. 6 shows an example of the setting of the partial character string and the collation control register 40 for realizing head collation in the parallel comparator shown in FIG. 5. In this embodiment, 10
Partial string to be set to 6 and valid flag register 4
0o indicates data to be set in the negative condition flag register 410, respectively.

The two characters shown in FIG. 5 are set as the partial character string.

In the valid flag register 400, set "1" to the flag for each character so that it corresponds to the location where the two characters are set, and reset the flag corresponding to the other unused locations (set "O"). set. In the negative condition flag register 410, It I ++ indicating that no negative condition is set is set as an initial value, and the corresponding flag is set only for characters that should be set with a negative condition as a partial character string. Reset (1 (set O11)).

Therefore, the substring 11a shown in FIG.
l, jj # ac# a, b"a-Ic"11
1. To set c# in the parallel comparator, each item may be set as shown in FIG. FIG. 6 shows an example of settings; for example, as long as each item has the same combination, any address can be set. However, if multiple substrings are searched at the same time,
The processing order is determined by a later-stage priority encoder, which will be described later.

Figure 7 shows a memory with an associative function, namely CAM (Co
addressable memory)
An example of a parallel comparator using

In this embodiment, one word is made up of a 4-byte CAM register, and the entire word is made up of 16 words (CAMRO-R15). This embodiment has a setting mode and a comparison mode. In the setting mode, character strings taken into the input buffer 102 are selectively transferred to arbitrary CAM registers in order to be set as partial character strings. In the comparison mode, the retrieved character string 101 is simultaneously distributed to all CAM registers in order to compare it with a plurality of partial character strings in parallel. Since the configurations of the individual partial character string comparison circuits are the same, the description will be given using the subscript O as an example.

In this embodiment, the CAM register (RO) 201-0 stores the first partial character string set to the parallel comparator 106, and the validity of each byte of the setting data of the CAM register (RO) 201-0. Valid flag register (VFO) 400-
0, negative condition flag register 9 that allows setting of negative conditions
(EFO) 410-0, if the negative condition flag register (VFO) 410-O is set (“1”), the byte-by-byte comparison result in the CAM register (RO) 201-0 is It is output as valid as it is, and if it is reset (10”), the byte-by-byte comparison result in the CAM register (RO) 201-0 is logically inverted and the comparison result against the set negative condition is output. logic circuit section 4
11-0.

When the valid flag register (VFO) 400-0 is set (“l”), a logic circuit outputs a comparison result for the negation condition setting for each byte in the CAM register (RO) 201-0. Part 411-
The output of 0 is valid, and when it is reset ('O''), the byte-by-byte comparison result in the logic circuit section 411-0 is invalidated and 1'' is always output, and the byte-by-byte results are A logic circuit section 203-0 to be integrated,
All bytes of the substring are stored in the valid flag register (VF
O) A logic circuit unit 204-0 that detects when invalidation is specified in 400-0, and the logic circuit unit 203-0.2.
A logic circuit unit 205-0 that integrates the results 214-0 and 215-0 of 04-0 to obtain the final comparison result of the partial character string, and a match signal line (ho) 2 that is the output thereof.
16-0°, and the entire parallel comparator 106 is composed of 16 sets of hardware for one word. In addition,
The byte and word configurations of the CAM register and the configurations of the valid flag register and negative condition flag register of this embodiment can be easily extended and can be arbitrarily selected.

CAM register (RO-R15) 201. Valid flag registers (VFO to VF15) 400° and negative condition flag registers (EFO to EF15) 410 can be accessed arbitrarily through the input buffer 102. In addition, a configuration in which individual dedicated data buses are provided is also available.

Partial strings and valid flag registers 400 and negative condition flag registers 410 necessary for searching specified strings
After setting the contents of , the associated valid flag register 400 is reset and invalidated for unnecessary CAM registers 201 for which no partial character string has been set.

As a result, the unnecessary comparison and verification process in the CAM register always results in a mismatch by the logic circuit section 204, and the match signal is fixed to the disabled state.

After the above initial settings, the searched character string 101 is simultaneously distributed to all CAM registers 201 via the input buffer 102. Since each CAM register 201 is in the comparison mode, the distributed input character code and 6. Comparison with preset partial character strings 6. Comparison of both is performed bitwise, and the results are logically ANDed for each byte. That is, if it is an 8-bit code, a complete match is detected for each alphanumeric character.

These comparison results are determined by first referring to the contents of the negative condition flag register 410 to determine whether they match or not.
Next, the byte comparison result is inputted to the logic circuit section 203 which integrates the result of the byte comparison with the corresponding bit of the valid flag register 400. For bytes in which a don't care character is set in a partial string by the valid flag register 400, a value indicating a match is always output. These outputs are then logically ANDed together. In other words, a comparison result 215 for one word of the partial character string is obtained.

On the other hand, if all 4 bytes are specified as invalid using only the logic circuit described above, a match will be indicated for any input character code. Therefore, if all valid flag registers 400 in the same word are reset The match signal must always be disabled. 204 and 2 in FIG. 7 constitute the logic circuit for this purpose.
It is 05.

As described above, according to this embodiment, not only can comparison and matching processing be performed in parallel on multiple substrings at high speed, but also a negation condition character and a do
8 characters can be set. Also,
If the word length of the parallel comparator 106 is one word or less, by setting a don't care character in the unnecessary part, that is, by resetting the valid flag 400 of the unnecessary part, a partial string of any length can be created in bytes. It is also possible to set , which has the effect of realizing flexible parallel comparison and matching processing. In addition, the valid flag register 40
There is also an effect that the partial character string set to - degree can be discarded and recovered at high speed by only the 0 operation.

FIG. 8 shows a conventional example of setting partial character strings to the CAM register and valid flag register.

When setting the search string "my", "my
” to byte 3 and byte 2, and set the valid flag v to invalidate the blanks in byte 1 and byte O.
3. v2. vl and vO are each “1n1111111
Set to 0"110". By doing this, the matching result of byte 1 and byte 0, for which no search string is set, will always be "1", so the match signal line will be checked only by the matching result of "my" in byte 3 and byte 2. The output will be determined.

However, in this conventional example, it is only possible to detect a match between a partial character string and a searched character string, and therefore it is impossible to match partial character strings that include negative conditions such as "It a, b".

FIG. 9 shows an example in which partial character strings similar to those in FIG. 8 are set in the present invention. Search string “m y I
t and valid flag register setting data” 110
Furthermore, since there is no negation condition setting in this case, '1111' is set in the negation condition setting flag register EFO, so that the logic of the collation result in the CAM register is not inverted.

FIG. 10 is an example of setting a partial character string including a negative condition according to the present invention. In FIG. 5, a partial string 11 a, b! is set in the parallel comparator. 1 is actually set as a partial character string as an example.

First, the substring #abIt from which the negative condition has been removed is set in bytes 3 and 2 of the CAM register. Part-time job 1. In order to invalidate the blank in byte 0, "110o" is set in the valid flag register. Furthermore, in order to add a negative condition to It b 11 of byte 2, set "1011" to the negative condition flag register.0 In the present invention, by setting these, the comparison between the partial string and the searched string Since the logic of the result can be arbitrarily inverted on a byte basis, it becomes possible to realize matching of partial character strings ua, bn that include negative conditions, which was not possible in the past.

FIG. 11 shows an embodiment in which a function is added to detect that a negative condition is set in a searched partial character string.

In this embodiment, a partial string is searched and the match signal line 216
-0 becomes ho=1, if at least one LL OII exists in the contents of the negative condition setting flag register, that is, if a negative condition is set somewhere in the substring, the negative condition is set. Output 413-0 of logic circuit unit 412-0 that detects that a partial character string containing
is enabled. FIG. 11 shows an example in which a search character string "m y " is set similarly to FIG. 9. In this case, since there is no negative condition set, "1111" is set in the negative condition flag register, and the logic of the collation result in the CAM register is not inverted.

Therefore, the output 413-0 of the logic circuit unit 412-0, which detects that a partial character string including a negative condition setting has been retrieved, is always disabled.

FIG. 12 is an example of setting a partial character string including a negative condition in the embodiment in which the function of detecting the negative condition setting of FIG. 11 is added. As in FIG. 10, a case where 11 a, bI+ are actually set as partial character strings will be shown as an example. Since "1011" is set in the negative condition flag register, when a partial character string is searched, the output 413-0 of the logic circuit unit 412-0 that detects the negative condition setting is enabled.

FIG. 13 shows a parallel comparator using CAM.

This is an example of an end code detection means. Except for the lack of a negative condition flag register, the configuration, method of setting an exit code, and operation are similar to those of a parallel comparator. However, the coincidence signal in the parallel comparator.

The end code detection means detects the end signal (trζsig
, ) 216-16 to the control logic block.

The exit code shown in Figure 13 is "F F
This is an example in which "E O" is set. If you want to change the number of valid characters of this end code, or if you do not use the end code at all, use the valid flag register register 400.
This can be dealt with by changing the -16 settings.

In FIG. 14, register 207 is used instead of the CAM register.
This is a second embodiment using a comparator circuit 208 and a comparator circuit 208.

In this embodiment, the partial character string taken into the input buffer 102 is once stored in the register 207 in the setting mode.
After storing data in register 207, switch to comparison mode and store in register 207.
Data is sent from the input buffer 102 to the comparison circuit 208 for comparison and verification.

Comparison operations in each comparison circuit are performed simultaneously.

The result is sent as 212 to the logic circuit section 203 which integrates the verification results. a logic circuit unit 203 that integrates the results of byte-by-byte matching based on the operations of the valid flag register 400 and the negative condition flag register 410 and output signals reflecting these; a logic circuit unit 204 that detects invalid designation of all bytes of a partial character string; The operation of the logic circuit unit 205 that obtains the final comparison result of the partial character strings is the same as that in the embodiment shown in FIG. In other words, in this embodiment as well, a partial character string of arbitrary length can be set, and a character that includes a negative condition or a variable-length don't car character string can be set as a partial character string.
It is also possible to set the e character, which has the effect of realizing flexible parallel comparison and collation processing.

FIG. 15 shows a conventional example of setting partial character strings to registers and valid flag registers. Similarly to Fig. 8, when setting the search string "my", set "my" to byte 3 and byte 2, and set byte 1 and byte O.
In order to invalidate the blank of v3.
v2. vl and v○ are each 1"''11+# O
Set to IT 1101+. By doing this, the matching result of byte 1 and byte 0, for which no search string is set, will always be ii 1 u, so the match signal line will be determined only by the matching result of "m y" of byte 3 and byte 2. The output of ho will be determined.

FIG. 16 shows a second embodiment of the parallel comparator of FIG.
This shows an embodiment using a register and a comparator circuit instead of a CAM register. This shows a case where a partial character string similar to that shown in FIG. 15 is set. Search string”
m y ” and valid flag register setting data “1100”.Furthermore, since there is no negative condition setting in this case, the negative condition setting flag register (
EFO) 410-0 is set to "1111" so that the logic of the comparison result in the comparison circuit is not inverted.

FIG. 17 is an explanatory diagram when a partial character string including a negative condition is set in the second embodiment of the parallel comparator shown in FIG. 14. An example is shown in which the partial character string #a=l, )1 set in the parallel comparator in FIG. 5 is actually set as one partial character string.

First, the substring II abI+ with the negative condition removed
are set in bytes 3 and 2 of the register. Part-time job 1
, to invalidate the blank in byte O, "1100" is sent to the valid flag register (VFO) 400-0.
”. Furthermore, in order to add a negative condition to “bI+” in byte 2, set the negative condition flag register (EFO) 4.
10-O is set to "1011" 0 In the present invention, by setting these, it is possible to realize matching of substrings II a, t, r'' including negative conditions, which could not be realized conventionally. It becomes possible.

FIG. 18 is an embodiment in which a function for detecting that a negative condition is set in a searched partial string is added to the second embodiment of the parallel comparator.

In this embodiment, a partial string is searched and the match signal line 216
-0 becomes hO=1, if at least one “0” exists in the contents of the negative condition setting flag register (EFO) 410-0, that is, a negative condition is set somewhere in the substring. If it is, the output 413-0 of the logic circuit section 412-0, which detects that a substring containing a negative condition setting has been searched, is enabled. y'' is set. In this case, there is no negative condition setting, so the negative condition flag register (EFO) 410-0 is set as "11".
11'' so that the comparison circuit does not invert the logic of the matching result.Therefore, the logic circuit section 41 detects that a partial string including a negative condition setting has been retrieved.
The output 413-0 of 2-0 is always disabled.

Figure 19 shows the 18th version with a negative condition setting detection function added.
This is an example of setting a partial character string including a negative condition in the illustrated embodiment. 118 as in FIG. 17. b
An example in which ll is actually set as a substring will be shown. Since "1011" is set in the negative condition flag register, when a partial character string is searched, the output 413-0 of the logic circuit section 412-0 that detects the negative condition setting is enabled.

FIG. 20 shows a parallel comparator using registers and comparison circuits. This is an example of an end code detection means. Except for the absence of a negative condition flag register, the configuration, method of setting an exit code, and operation are similar to a parallel comparator using registers and comparison circuits. However, the match signal in the parallel comparator is the end signal (
trn+sig, ) 216-16 to the control logic block.

This figure shows an example in which "FFEO"' is set as the end code. When changing the number of valid characters of this end code, or when not using an end code at all, this can be done by changing the setting of the valid flag register 400-16.

Figure 21 shows an input port for setting partial strings.

This is a first example of a configuration in which a valid flag register, an input port for setting a negative condition flag register, and an input port for a searched character string are shared.

The access mode is the CAM register 201, the valid flag register 400, or the negative condition flag register 41.
There are three types: reading data from 0 (read mode), writing data to them (write mode or setting mode), and matching the searched character string with a partial character string (conveyor mode or comparison mode). data boat 15
0 functions as a data output port in read mode and as a data input port in write mode and conveyor mode. Also, CAM register 201-〇～201-
15 and valid flag registers 400-0 to 400-1
5. Negative condition flag registers 410-0 to 410-15
are assigned an address, and any one can be selected via the decoder 161 with an address input from the address board 160 in read mode or write mode.

Next, the data flow in each mode will be explained.

In read mode, any CAM register 201-0~
201-15 or valid flag register 400-0
~400-15, negative condition flag register 410-0~
410-15 is specified by the address, its contents are placed on the output data path, the gate of the output buffer 142 is opened, and the data 140 is read out.

In the write mode, the gate of the input buffer 102 is opened and data is placed on the input data bus, and any CAM register 201-0 to 201-15, valid flag register 400-0 to 400-15, or negative condition flag register 410- 0 to 410-15 are specified by the address, and data 130 on the input data bus is latched into the address.

In the conveyor mode, the gate of the input buffer 102 is opened to input the data 130, and the data 130 is placed on the data path. The addresses are set so that registers 41o-O to 410-15 are not selected, and the data on the bus is distributed to all CAM registers 201-0 to 201-15, and the latched partial character string is Verify with.

By sharing ports in each of the above modes, the number of pads on the semiconductor integrated circuit can be reduced. Therefore, it is effective as a countermeasure for increasing the chip area and increasing the number of pins.

Similar to FIG. 21, FIG. 22 shows a configuration in which an input port for setting a partial character string, a valid flag register, an input port for setting a negative condition flag register, and an input port for a searched character string are shared. This is Example 2. This is constructed using a register and a comparator circuit instead of the CAM register shown in Figure 21.The operation and effect are the same as the embodiment shown in Figure 21, and it is effective as a countermeasure for increasing the chip area and the number of pins. It is.

An example of the code converter 107 is shown in the 235th example.

In this embodiment, the coincidence signal (ho to h15) 23 from the parallel comparator 106
A priority encoder 220 that takes 0 as an input signal and converts it into a status code 231, also a match signal 2.
30 as an input signal, a logic 221 detects that all of the matching signals are disabled, that is, that no substring is found in the searched string; It consists of a logic 222° that detects that any substring is found in the search string.

The priority encoder 220 generates a coincidence signal (ho-
h15) An encoder that encodes 230 with priority, and when a plurality of coincidence signals are enabled, encodes one by one from the one with the highest priority and converts it to the status code 231.

The status code 231 is temporarily stored in the status code queue 109 and sent to the finite automaton execution means 104. Here, comparison processing with the latter half of the search string is performed. Further, the outputs 232 and 233 of the logic for monitoring the match detection status 230 in the parallel comparator 106 are the status code 231.
It is used to determine the conditions for transferring the data to the selector 108.

In other words, when the hit signal 233 indicating that at least one partial character string has been found is 1'', the status code 231 is transferred to the selector 108. 232
Since the logical sum of is ``11'' every cycle (it is reset at the end of every cycle).

This is used as a timing signal to perform synchronous control of data transfer.

A block diagram of a second embodiment of the present invention is shown in FIG.

This embodiment removes the status code queue 109 from the first embodiment (FIG. 2), and the searched character string 101
Input cover sofa 102 to take in, input character code 130
A parallel comparator 106 that collectively compares a plurality of partial character strings set in advance, and a valid flag register 400 in the parallel comparator. Negative condition flag register 410, code converter 107 that converts a match signal 131 indicating that a match with a substring of a search string has been detected as a result of comparison in a parallel comparator into a status code 132, and a finite automaton. An input selector 108 for selecting a status code 134 to be input to the execution means 104. An automaton execution means 104 that realizes automaton operation, a character code buffer 103 that stores character codes 135 to be input to the automaton execution means 104. It consists of a state transition table 110 that stores control information for state transitions of the automaton, and an output buffer 105 that holds search results 111 to be output.

The operation of this embodiment is almost the same as that of the first embodiment. Therefore, as in the first embodiment, processing can be performed only by the parallel comparator until a match between substrings of the search string is detected, and a large portion of the string search processing can be performed only by comparison processing without table access. It can be done with Therefore, it is possible to improve the speed of the entire search process. Furthermore, the collation control register in the parallel comparator allows flexible collation processing even in head collation processing.

In this embodiment, first, the parallel comparator 106 detects a match with a substring of a search string. - When a match is detected, the match signal 131 is converted into a status code 132, passed through the selector 108, and sent to the finite automaton execution means 104.
will be forwarded to. And for the searched strings entered after this point.

The automaton is executed by the finite automaton execution means 104 and the state transition table 110 without referring to the comparison result of the parallel comparator 106.The selector 108 selects the next state code 138 from the state transition table 110,
It is transferred to the finite automaton execution means 104. The above operations are repeated one after another for input character codes, and backward verification is performed. On the other hand, if the search string is searched,
If a failure that causes a transition to the initial state occurs, the parallel comparator 106 performs the head verification process again.

The execution of these series of processes is inferior to the first embodiment in terms of parallelism, since the processes of the parallel comparison unit 10 and the finite automaton execution unit 11 are executed sequentially.

However, if the processing ratio of head matching to the whole is high, this embodiment has the effect of sufficiently speeding up the process, and also has the effect of reducing the amount of the status code queue 109 and the hardware that controls it, and the control method. This simplification has the effect of improving processing speed. Furthermore, since the control method is simple, it is easy to cut out the parallel comparator 106, state transition table 110, and various buffers as independent chips to create a multi-chip configuration as a whole to create a larger system configuration.

A block diagram of a third embodiment of the present invention is shown in FIG.

This embodiment utilizes a CPU as the finite automaton execution means 104 in the first embodiment.

The configuration of this embodiment includes an input buffer 1022, a character code buffer 1o3. Parallel comparator 106. Code converter 107
．． Input selector 108. Status code queue 109. Valid flag register 400° Negative condition flag register 4
The steps up to 10 are the same as in the first embodiment. However, since the CPU 112 is used as the finite automaton execution means, the character code buffer 103 and status code queue 109
is mapped to the memory space of the CPU 12. These outputs are connected to an internal bus 113, and via this to a data bus of the CPU 112. C.P.
The state transition table 114 that stores control information for the automaton executed in U112 is accessed by specifying an address. As a result.

The next status, which is the contents of the table, is returned to the internal bus 113 and transferred to the status code queue 109 via the selector 108. At this time, if a state indicating a match with the search string is obtained, the corresponding search result 111 will be sent to the CPU.
112 to output buffer 105 via internal bus 113
is written to. In the above processing, the CPU 112 controls the entire system, controls the internal bus 113, and sets data to the parallel comparator 106 and state transition table 114.
will do it.

In this embodiment, as in the first embodiment, the parallel comparator 1
Since the partial character string comparison process in step 06 can be performed without table access, the overall speed of the search process can be improved. Furthermore, the collation control register in the parallel comparator enables flexible collation processing even in head collation processing.

A block diagram of a fourth embodiment of the present invention is shown in FIG.

This embodiment is similar to the character code buffer 103 (Fig. 25) and status code queue 109 (Fig. 25) in the third embodiment.
) and the state transition table 114 (Fig. 25) on the CPU 1.
The configuration is such that the memory space is allocated to memory spaces under the control of 12 computers.

The configuration of this embodiment includes an input buffer 102, a parallel comparator 1
06. Code converter 107. Valid flag register 4
00. The steps up to the negative condition flag register 410 are the same as in the third embodiment. However, the internal bus 113 via the character code buffer 103 (FIG. 25) in the third embodiment
(FIG. 25), connection to internal bus 113 (FIG. 25) via input selector 108 (FIG. 25) and status code queue 109 (FIG. 25), respectively, directly to internal bus 113. It is in a connected form.

and character code buffer 116 and status code queue 1
17 is located as part of the memory space that includes the state transition table 115. These can be accessed by addressing from the CPUI 12 via the internal bus 113.

A series of comparison and matching processes for the search string from the search string 101 are performed in the same manner as in the third embodiment. At this time, the internal bus 113 is controlled by the CPU 112.

In this embodiment as well, the first. Second. Similar to the third embodiment,
Since the parallel comparator 106 can perform the comparison process of partial strings without table access, the effect of improving the speed of the entire search process can be obtained. Furthermore, the collation control register in the parallel comparator enables flexible collation processing even in head collation processing.

A block diagram of the fifth embodiment of the present invention is shown in FIG.
This embodiment uses the search result reference table 118 in the fourth embodiment.
It has a configuration with the addition of .

The search result reference table 118 is the state transition table 11
5.Character code buffer 116. Status code queue 11
7, it is located in the memory space under the control of the CPUI 12, and can be accessed from the CPUI 12 by addressing.

In this embodiment, when a state indicating that a match is detected between the searched character string 101 and the searched character string is obtained through the comparison and matching process, the CPU 112 retrieves part of the search result 111 from the corresponding address in the search result reference table 118. The search result reference table 118, which obtains information to be added as a search result and writes it to the output buffer 105, also contains a terminator that indicates the end of a series of search processes, and five types of control information to be passed to the hardware connected to the next stage. These data are also written to the output buffer 105 as necessary.

By making the contents of the search result reference table 118 rewritable, it can be made programmable by the user. Therefore, the contents can be arbitrarily set for each different process or for each chip.

Therefore, in this embodiment, since the data format and contents of the search results 111 can be arbitrarily set, it is possible to flexibly support various system configurations and interfaces. Furthermore, in this embodiment as well, the first, second, . Third. Similar to the fourth embodiment, since the parallel comparator 106 can perform the partial string comparison process without table access, the overall speed of the search process can be improved. Furthermore, the collation control register in the parallel comparator enables flexible collation processing even in head collation processing.

FIG. 28 is a diagram showing the configuration of an embodiment in which the verification flag register is set by a command. This embodiment includes a command register 421 that takes in the verification flag register setting command 420, and an analysis of the verification flag register setting command 420. A command decoder 422 that outputs data to be set in the collation flag register and a control signal 424 for data setting from the output of the command decoder 422.
and a control circuit 423 that generates.

A verification flag register setting command 420 is input from the outside to a command register 421, and further sent to a command decoder 422 for analysis.

According to the analysis result, the control circuit 423 generates data to be set in the collation flag register and control signals necessary for the setting. The control signal performs data latch timing control for the collation flag register to which setting data is to be set.

By setting data to the collation flag register using a command method, it is possible to set data to a plurality of registers at the same time or to invalidate a plurality of registers at the same time.

FIG. 29 shows a sixth embodiment in which a verification flag register setting circuit using the command method shown in FIG. 28 is added to the first embodiment of the present invention.
This is a block diagram of an embodiment of 0. In this embodiment, in addition to the effects of the first embodiment, it is possible to set data to multiple registers at the same time, and to disable multiple registers at the same time. Effects can be obtained.

Hereinafter, FIGS. 30 to 33 show seventh to tenth embodiments in which a verification flag register setting circuit using the command method shown in FIG. 28 is added to the second to fifth embodiments of the present invention, respectively. It is a block diagram. In addition to the effects of the second to fifth embodiments, these embodiments have the advantage that it is possible to set data to a plurality of registers at the same time and to invalidate a plurality of registers at the same time.

〔Effect of the invention〕

According to the present invention, a search method improves the search processing speed by placing a parallel comparator in the front stage of the finite automaton execution means to speed up the head matching process when searching documents by full text search using an automaton. By providing a negative condition flag register in addition to the valid flag register in the parallel comparator, it is possible to set substrings with different lengths of one word, and partial strings that include don't care characters and negative condition characters. Become. This improves the degree of freedom in setting partial strings in high-speed searches using automata, and has the effect of realizing more flexible ambiguous searches such as single character error tolerance searches and limited searches.

[Brief explanation of the drawing]

FIGS. 1(a) and (b) are explanatory diagrams of the principle of character string search using a finite automaton in the present invention, FIG. 2 is a block diagram showing the configuration of the first embodiment of the present invention, and FIG. is an explanatory diagram of an expansion example that allows for a single-character error in the search string, Figure 4 is an explanatory diagram of an automaton for searching the expanded search string in Figure 3, and Figure 5 is an illustration of the search in Figure 3. An explanatory diagram of a parallel comparator and backward collation automaton for searching character strings. Figure 6 is an example of setting the collation flag register and partial string to realize partial string search with the parallel comparator shown in Figure 5. FIG. 7 is an explanatory diagram of an embodiment of a parallel comparator using CAM. FIG. 8 is an explanatory diagram of how to set a search partial string to a parallel comparator using conventional CAM. FIG. 9 is an explanatory diagram of how to set a search partial string to a parallel comparator using CAM in the present invention, and FIG. 10 is a search partial string including a negative condition to a parallel comparator using CAM in the present invention. Fig. 11 is an explanatory diagram of how to set columns, and Fig. 11 is an explanatory diagram of how to set a search partial string to a parallel comparator using a CAM that has a function of detecting a search string including a negative condition.
The figure shows a CAM with a function to detect search strings that include negative conditions.
Fig. 13 is an explanatory diagram of how to set a search partial string including a negative condition to a parallel comparator using CAM, Fig. 14 is an explanatory diagram of how to set an end code to a parallel comparator using CAM. 15 is an explanatory diagram of an embodiment of a parallel comparator using registers and comparators, FIG. 15 is an explanatory diagram of how to set a search partial string to a parallel comparator using conventional registers and comparators, and FIG.
The figure is an explanatory diagram of how to set a search partial string to a parallel comparator using registers and comparators in the present invention, and Figure 17 is a negative condition for a parallel comparator using registers and comparators in the present invention. Fig. 18 is an explanatory diagram of how to set a search substring containing a negative condition. Fig. 19 is an explanatory diagram of how to set a search partial string including a negation condition to a parallel comparator using a register and a comparator that have a function of detecting a search string including a negation condition. The figure is an explanatory diagram of how to set the end code to the parallel comparator using registers and comparators.
Figure 1 shows a partial string in a parallel comparator using CAM.
An explanatory diagram of an embodiment in which the setting port of the valid flag register and the negative condition flag register and the input port of the searched character string are shared. FIG. 22 shows the partial string and valid flag in a parallel comparator using registers and comparators. register,
An explanatory diagram of an embodiment in which the setting port of the negative condition flag register and the input port of the searched character string are shared, FIG. 23 is an explanatory diagram of the embodiment of the code converter, and FIG. 24 is the second embodiment of the present invention.
FIG. 25 is a block diagram showing the configuration of the third embodiment of the present invention. FIG. 26 is a block diagram showing the configuration of the fourth embodiment of the present invention. The figure is a block diagram showing the configuration of the fifth embodiment of the present invention.
FIG. 29 is a block diagram showing the configuration of a sixth embodiment of the present invention, and FIG. 30 is a diagram showing the configuration of a seventh embodiment of the present invention. 31 is a block diagram showing the configuration of the eighth embodiment of the present invention, FIG. 32 is a block diagram showing the configuration of the ninth embodiment of the present invention, and FIG. 33 is a block diagram showing the configuration of the ninth embodiment of the present invention. FIG. 34 is an explanatory diagram of the character string search system, and FIGS. 35(a) and (b) are explanatory diagrams of the principle of the system previously proposed by the inventors of the present application. . DESCRIPTION OF SYMBOLS 10... Parallel comparison part, 11... Finite automaton execution part, 12... Finite automaton, 13... Leading verification automaton, 14... Back matching automaton, 4
0...Verification flag register, 101...Character string to be searched, 102...Input buffer, 103, 116...
Character code buffer, 104... Finite automaton execution means, 105... Output buffer, 106... Parallel comparator. 107... Code converter, 108... Selector, 1
09°117...Status code queue 110,114
゜115...State transition table, 111,136...
・Search result, 112...CPU, 113...Internal bus. 118... Search result reference table, 130, 135.
... Input character code, 131 ... Match signal, 132゜133.134 ... State code, 137 ... State transition table access address, 138 ... Transition destination state, 140 ... Verification flag register Stored data, 14
2... Output buffer, 150... Delta port 16
0...Address port, 161...Address decoder, 162...Verification flag register write control signal, 400...Valid flag register, 410...
Negation condition flag register, 420...Verification flag register setting command, 421...Command register, 4
22... Command decoder, 423... Control circuit for setting data to the collation flag register, 424... Setting data and setting control signal to the collation flag register, 10... Automaton dividing line. 1 ￥ Figure ((L) Figure <b) 1j Figure z Figure #3-0 遁15 Figure byte3bfez bget bYf:et>F16 Figure Zρ4-ρ byte3 bytez bytel byte. Toge 1'7 Figure byte3byta blta byt$■ 8 Figure byte3bytex byter byteθ 9th Figure byte3byteZ bltel blka Toge Zρ Time Z/i -76 Convergence pass No. B Figure nrv-S engineering r'1~-g L nN,' ＋：□ Mouth・＼! Fig. 35 (Illusion 5 Fig. (b)) →Terase Address Central Research θ Minutes ago 280-1 Hitachi Co., Ltd. Hitachi Co., Ltd. Hitachi Co., Ltd.

Claims (1)

[Claims] 1. A symbol string search method using an automaton that collectively determines whether or not a plurality of search target symbol strings exist in a search target symbol string composed of code-expressed symbols. When searching a plurality of search symbol strings at once from a searched symbol string, the search symbol string is divided into at least two partial symbol strings at an arbitrary position, and one partial symbol string of the divided symbol strings is divided into two partial symbol strings. As a result of the matching, that is, the head matching process, only for the search symbol string that satisfies the search conditions for the partial symbol string, the remaining partial symbol strings are matched, that is, the backward matching process is performed, and here the remaining partial symbol strings are A symbol string search method that determines that a search symbol string has been searched when a search condition for a string is satisfied, and the search condition for the substring in the head matching process is to include all symbols other than a specific symbol. A symbol string search method characterized in that a condition, that is, a negative condition can be set at an arbitrary position in a partial symbol string, and head matching processing is performed. 2. A symbol string search device for performing a symbol string search using the symbol string search method according to claim 1, comprising at least: (a) first external information access means for inputting the symbol string to be searched; (b) head matching processing means for performing a head collation process between the searched symbol string input by the first external information access means (a) and a partial symbol string of the search symbol string; (c) (d) performing a backward matching process between the searched symbol string input by the first external information access means (a) and a partial symbol string of the search symbol string; (e) a second external information access means for inputting backward verification processing control data from the data storage means; A symbol string search device. 3. Component (a) of the symbol string search device according to claim 2
A semiconductor integrated circuit, characterized in that at least two of (e) are integrated on the same chip. 4. In the symbol string search device according to claim 2, components (a) to
(e) at least (a) a first external information access means; and (e) a second external information access means; A symbol string search device characterized in that the symbol string search device is configured such that access by the second external information access means (e) can be performed independently. 5. In the semiconductor integrated circuit according to claim 3, the constituent elements (a) to
Of (e), at least (a) the first external information access means and (e) the second external information access means are integrated on the same integrated circuit, and the first external information access means (a) 1. A semiconductor integrated circuit characterized in that the semiconductor integrated circuit is configured such that access by and access by the second external information access means (e) can be performed independently. 6. The symbol string search device according to claim 4, wherein the first
A symbol string search device characterized in that the external information access by the external information access means (a) is performed more frequently than the external information access by the second external information access means (e). . 7. The semiconductor integrated circuit according to claim 5, wherein among the components (a) to (e), at least the first external information access means (a) and the second external information access means (e) are integrated on the same integrated circuit, and the external information access by the first external information access means (a) is performed more frequently than the external information access by the second external information access means (e). What is claimed is: 1. A semiconductor integrated circuit characterized in that the semiconductor integrated circuit is configured such that 8. The symbol string search device according to claim 4, wherein the first
A symbol string search device characterized in that the external information access by the external information access means (a) is performed before the external information access by the second external information access means (e). 9. The semiconductor integrated circuit according to claim 5, wherein at least the first external information access means (a) and the second external information access means (e) of the components (a) to (e) are integrated on the same integrated circuit, and the external information access by the first external information access means (a) is performed before the external information access by the second external information access means (e). A semiconductor integrated circuit characterized by being configured as follows. 10. In the semiconductor integrated circuit according to claim 3, a head verification processing means (b) among the components (a) to (e).
integrated on the same integrated circuit, and having means for storing a plurality of the search symbol strings or partial symbol strings thereof inside the semiconductor integrated circuit. Semiconductor integrated circuit. 11. The symbol string search device according to claim 2, at least: (f) an input buffering means for buffering the input symbol string to be searched; (g) a plurality of preset searches for performing head matching processing; (h) a state transition table that stores control data to be referenced during backward matching processing; , (i) finite automaton execution means for executing a finite automaton according to the state transition table (h) and the searched symbol string sent from the input buffering means (f) in order to perform backward matching processing; (j) During backward matching processing, the state transition table (h
) state transition table access means for referencing (k) the first collation result by the parallel collation means (g);
code conversion means for converting into a code to be transferred to the finite automaton execution means (i); (l) a code generated by the code conversion means (k) and a code obtained from the state transition table (h); (m) output buffering means for holding the search results from the finite automaton execution means (i); and when performing search processing for multiple search symbol strings for the input symbol string to be searched, at least two search symbol strings are searched at any position.
The parallel matching means performs head matching processing on one of the divided symbol strings, and executes the finite automaton only for the search symbol string that satisfies the search conditions for the partial symbol string. The means performs backward checking processing on the remaining partial symbol strings, and when the search condition regarding the remaining partial symbol strings is satisfied, a symbol string search processing is performed in which it is determined that the search symbol string has been retrieved. A symbol string search device. 12. The semiconductor integrated circuit according to claim 3, at least: (f) input buffering means for buffering the input symbol string to be searched; (g) a plurality of search symbols set in advance for performing header matching processing; parallel matching means for performing parallel matching between the string and the searched symbol string sent from the input buffering means (f); (h) a state transition table that stores control data to be referenced during backward matching processing; (i) Finite automaton execution means for executing the finite automaton according to the state transition table (h) and the searched symbol string sent from the input buffering means (f) in order to perform the backward matching process; ( j) During backward matching processing, the state transition table (h
) state transition table access means for referencing (k) the first collation result by the parallel collation means (g);
Code conversion means for converting into a code to be transferred to the finite automaton execution means (i). (l) Data for selecting which of the code generated by the code conversion means (k) and the state obtained from the state transition table (h) is to be transferred to the finite automaton execution means (i). selection means; (m) output buffering means for retaining the search results from the finite automaton execution means (i);
Alternatively, a semiconductor integrated circuit characterized in that at least two or more of the constituent elements other than the above (h) are integrated on the same integrated circuit. 13. The symbol string search device according to claim 11, further comprising: end code setting means for setting an arbitrary end code into the symbol string search device; and end code detecting means for detecting the end code; A symbol string search device characterized in that the symbol string search process is terminated by detecting the end code in the symbol string. 14. The semiconductor integrated circuit according to claim 12, further comprising: an end code setting means for setting an arbitrary end code into the semiconductor integrated circuit; and an end code detecting means for detecting the end code; A semiconductor integrated circuit characterized in that the symbol string search process is terminated by detecting the end code in the semiconductor integrated circuit. 15. In the symbol string search device according to claim 13, when the termination code composed of a plurality of symbols set in the termination code setting means is compared with the symbol string to be searched, validity or invalidation of the termination code is determined. At least a valid flag register is provided for each symbol, and means is provided for setting or resetting arbitrary constituent bits of the valid flag register, and the constituent bits of the valid flag register are referred to during verification. The symbol in the end code corresponding to the part in the set state is made valid when matching with the symbol string to be searched, and the symbol in the end code corresponding to the part in the reset state is used as the symbol string to be searched. By invalidating the end code when checking the
A symbol string search device characterized in that it is possible to set re). 16. In the semiconductor integrated circuit according to claim 14, when the termination code composed of a plurality of symbols set in the termination code setting means is compared with the symbol string to be searched, at least whether the termination code is valid or invalid is determined. A valid flag register is provided for each symbol, and means is provided to set or reset arbitrary constituent bits of the valid flag register, and the valid flag register is referred to during verification, and the constituent bits of the valid flag register are , the symbol in the end code corresponding to the part in the set state is made valid when matching with the symbol string to be searched, and the symbol in the end code corresponding to the part in the reset state is made valid when matching with the symbol string to be searched. A semiconductor integrated circuit characterized in that a don't care can be set at any position of the end code by invalidating it during verification. 17. The symbol string search device according to claim 11, wherein the parallel matching means and the finite automaton execution means operate and process the same input symbol in parallel. 18. The semiconductor integrated circuit according to claim 12, wherein the parallel verification means and the finite automaton execution means operate in parallel to process the same input symbol. 19. The symbol string search device according to claim 11, wherein the finite automaton execution means is configured using a CPU. 20. The semiconductor integrated circuit according to claim 12, wherein the finite automaton execution means is configured using a CPU, and the CPU is integrated on the same integrated circuit. 21. The symbol string search device according to claim 11, wherein the parallel matching means is constructed using an associative memory. 22. The semiconductor integrated circuit according to claim 12, wherein the parallel matching means is constructed using an associative memory, and the CPU is integrated on the same integrated circuit. 23. The symbol string search device according to claim 11, wherein the parallel matching means is constructed using a plurality of combinations of registers and comparison circuits. 24. The semiconductor integrated circuit according to claim 12, wherein the parallel comparison means is configured using a plurality of combinations of registers and comparison circuits, and these are integrated on the same integrated circuit. circuit. 25. The symbol string search device according to claim 11, wherein a partial symbol string of each search symbol string set in the parallel matching means is provided with a valid flag register that indicates whether it is valid or invalid at least for each symbol at the time of matching. , further comprising means for setting or resetting arbitrary configuration bits of the valid flag register, which refers to the valid flag register during verification, and corresponds to the portion where the configuration bits of the valid flag register are in the set state. Make the symbols in the subsymbol string valid when matching with the searched symbol string, and make the symbols in the subsymbol string corresponding to the part in the reset state invalid when matching with the searched symbol string. A symbol string search device characterized in that it is possible to set a don't care at any position of the partial symbol string. 26. The semiconductor integrated circuit according to claim 12, wherein a partial symbol string of each search symbol string set in the parallel matching means is provided with a valid flag register that indicates whether the symbol is valid or invalid at least for each symbol during matching; Furthermore, it has a means for setting or resetting arbitrary constituent bits of the valid flag register, and refers to the valid flag register during verification, and sets the constituent bits of the valid flag register to the part corresponding to the set state. Make the symbols in the symbol string valid when matching with the searched symbol string, and make the symbols in the partial symbol string corresponding to the part in the reset state invalid when matching with the searched symbol string. A semiconductor integrated circuit characterized in that it is possible to set a don't care at any position of the partial symbol string. 27. In the symbol string search device according to claim 11, in the partial symbol string of each search symbol string set in the parallel matching means, is the set symbol string valid as it is, or is a symbol string other than the set symbol string A negation condition flag register is provided to indicate at least for each symbol whether all symbol strings of The negative condition flag register is referred to, and the symbols in the partial symbol string corresponding to the part where the constituent bits of the negative condition flag register are in the set state are kept valid when matching with the searched symbol string, and are set in the reset state. By assuming that all symbols other than the symbol in the substring that corresponds to the part to be searched are valid when matching with the searched symbol string, a negation condition can be placed at any position in the substring. A symbol string search device characterized in that it is possible to set. 28. In the semiconductor integrated circuit according to claim 12, in the partial symbol string of each search symbol string set in the parallel matching means, is the set symbol string valid as it is, or is a symbol string other than the set symbol string valid? A negation condition flag register is provided that indicates whether all symbol strings are valid at least for each symbol, and further includes means for setting or resetting arbitrary constituent bits of the negation condition flag register, and the negation is performed at the time of verification. By referring to the condition flag register, the symbols in the partial symbol string corresponding to the part where the constituent bits of the negative condition flag register are in the set state are kept valid when matching with the searched symbol string, and are in the reset state. By assuming that all symbols in a subsymbol string corresponding to a certain part are valid when matching with the searched symbol string, a negation condition can be placed at any position in the subsymbol string. A semiconductor integrated circuit characterized by being able to be configured. 29. The symbol string search device according to claim 25 or 27, comprising means for receiving an external command for setting data in any valid flag register or negative condition flag register, and converting the received command into a control signal and setting data. What is claimed is: 1. A symbol string search device, characterized in that it has means for converting into a symbol string, and is capable of setting a valid flag register and a negative condition flag register in a parallel comparator by inputting a command from the outside. 30. The semiconductor integrated circuit according to claim 26 or 28, comprising means for receiving an external command for setting data in any valid flag register or negative condition flag register, and converting the received command into a control signal and setting data. 1. A semiconductor integrated circuit, comprising means for converting, and a valid flag register and a negative condition flag register in a parallel comparator can be set by inputting an external command. 31. The symbol string search device according to claim 25 or 29, wherein when the parallel matching means is set to be don't care for all the symbols in the partial symbol string of the search symbol string, the parallel matching means 1. A symbol string search device characterized in that a symbol string search device is provided with a means for determining whether or not the symbols do not match. 32. The semiconductor integrated circuit according to claim 26 or 30, wherein when the parallel matching means is set to be don't care for all the symbols in the partial symbol string of the search symbol string, the parallel matching means A semiconductor integrated circuit characterized in that means for determining a mismatch is integrated on the same integrated circuit. 33. In the symbol string search device according to claim 11, as a result of matching a plurality of search symbol strings set in the parallel matching means with the searched symbol string, all of the set search symbol strings meet the search condition. 1. A symbol string retrieval device characterized in that the symbol string search device is provided with a means for detecting this when the condition is not satisfied. 34. The semiconductor integrated circuit according to claim 12, as a result of matching the plurality of search symbol strings set in the parallel matching means with the searched symbol string, all of the set search symbol strings meet the search condition. A semiconductor integrated circuit characterized in that means for detecting the unsatisfied condition is integrated on the same integrated circuit. 35. In the symbol string search device according to claim 11, as a result of matching a plurality of search symbol strings set in the parallel matching means with the searched symbol string, at least one of the set search symbol strings is searched. 1. A symbol string search device characterized by comprising means for detecting when a condition is satisfied. 36. The semiconductor integrated circuit according to claim 12, as a result of matching a plurality of search symbol strings set in the parallel matching means with a searched symbol string, at least one of the set search symbol strings meets the search condition. 1. A semiconductor integrated circuit characterized in that a means for detecting this is integrated on the same integrated circuit. 37. The symbol string search device according to claim 27 or 29, wherein as a result of matching a plurality of search symbol strings set in the parallel matching means with a searched symbol string, at least one of the set search symbol strings is 1. A symbol string search device, comprising means for detecting when the search condition satisfies a search condition and the search condition includes a negative condition setting. 38. The semiconductor integrated circuit according to claim 28 or 30, wherein as a result of matching a plurality of search symbol strings set in the parallel matching means with a searched symbol string, at least one of the set search symbol strings is 1. A semiconductor integrated circuit characterized in that means for detecting when a search condition is satisfied and the search condition includes a negative condition setting is integrated on the same integrated circuit. 39. The symbol string search device according to claim 11, further comprising: (n) storing information to be added to the search result as part of the search result when the search result is output from the finite automaton execution means (i). (o) means for setting the contents of the additional information storage means (n); and the output buffering means (m) for holding the search results.
) A symbol string search device characterized in that it is configured to be able to add information that can be arbitrarily set in advance to the search results outputted to the search results. 40. The semiconductor integrated circuit according to claim 12, further comprising: (n) an addition for storing information to be added to the search result as part of the search result when the search result is output from the finite automaton execution means (i). information storage means (o) means for setting the contents of the additional information storage means (n), integrated on the same integrated circuit, and the output buffering means (m) for holding the search results;
) A semiconductor integrated circuit characterized in that the semiconductor integrated circuit is configured such that information that can be arbitrarily set in advance can be added to the search results outputted in the search results. 41. The semiconductor integrated circuit according to claim 12, wherein the parallel matching means integrated on the integrated circuit has a partial symbol string storage means, a valid flag register, and a negative condition flag register, and a partial symbol string setting A semiconductor characterized in that at least two of the following input ports are shared: an input port for setting a valid flag register, an input port for setting a negative condition flag register, and an input port for a symbol string to be searched. integrated circuit.