TWI509441B - Can flexibly set the data width of the multi-character string alignment device - Google Patents

Description

Multi-character string comparison device capable of flexibly setting data width

The present invention relates to a string comparison device, and more particularly to a multi-word string alignment device that can flexibly set a data width.

The string alignment algorithm proposed by Alfred V. Aho and Margaret J. Corasick, commonly referred to as the AC algorithm, is an efficient method of exact string matching, as long as it is searched through a single search. All keywords (keywords) can be found in a string. One of the most important applications is the Network Intrusion Detection System (NIDS), such as the well-known SNORT.

The search tree established according to the AC algorithm is called AC-trie (AC search tree). Please refer to FIG. 1 , which illustrates one AC-trie established according to the keyword set {enhappy, happy, happen, happygo}. In Fig. 1, a circle containing numbers represents a state; a state of a double-layered circle is an output state - indicating that when a transition is made to the state, there is a matching output string, for example, state 7 represents a matching output word. The string "enhappy happy"; the solid line is the goto function, the dotted line is the failure function, and the functions of the forward function and the failure function will be explained below. In fact, in addition to the initial state, each state has a failure function to point to the initial state or another state. For the sake of brevity, the failure function to the initial state (for example, the failure function of state 1) is not shown in FIG. When a state's failure function does not refer to the initial State, but refers to another state, indicating that the string represented by the state contains the string represented by the other state. For example, the failure function of state 7 refers to state 12, where the string represented by state 7 contains the string represented by state 12 (the string represented by state 7 is "enhappy", the string represented by state 12 Is "happy").

When the string comparison is performed according to the AC-trie of FIG. 1, the current state (current state) is first set to the initial state 0. Then, for the input string, one character is compared at a time. For the input character, find a matching forward function from at least one forward function corresponding to the current state to determine the next state; if the forward function cannot be found, it will fail according to the failure function. The state indicated by the function is specified as the current state, and then continue to find the forward function that matches. Through the failure function, it will eventually point to the initial state. Since the forward function of the initial state covers all the characters, the advance function and the failure function ensure that the secondary state can be determined after each input of one character. A matching cycle is calculated from the acceptance of an input character to the determination of the secondary state by the advance function and the failure function. After comparing one character, after determining the secondary state, the secondary state is designated as the current state, and then accepting the next character to enter the next comparison cycle. According to the description of the foregoing comparison process, after AC-trie is established, the string comparison is performed through the forward function and the failure function, and all the keywords matching the keyword can be found by one pass search, so Its search time is linear with the length of the input string, ie O(n).

Referring to FIG. 2(a), an example of a string comparison procedure using the AC-trie of FIG. 1 is illustrated. As shown in FIG. 2(a), when the string comparison program proceeds to the output state 14 and the output state 7, it will respectively transfer to the state 2 and the state 12 via a failure function, and then perform subsequent character comparison. . Figure 2(b) is an NFA (non-deterministic finite automata corresponding to Figure 2(a); Limit state machine) string comparison mode, which allows multiple states to be active at the same time, wherein state 0 is always in action, that is, as long as the input word matching the key element e or h is detected in state 0 Yuan, NFA opens a string comparison program. In FIG. 2(b), the first string comparison program (for comparing "happen") and the second string comparison program (for comparing "enhappy") are performed simultaneously when comparing en; The second string comparison program and the third string comparison program (for comparing "happygo") are performed simultaneously when comparing "happy".

As can be seen from the above description, AC-trie is similar in form. DFA (deterministic finite automata) because it can only have one state active at a time. However, compared with the NFA string alignment method, it can be seen that in each comparison period, another state pointed out by the failure function of one of the active states is active in the NFA. Because of all non-initial states, the failure function will eventually link to the initial state, so the initial state will always be active. Therefore, AC-trie can achieve an effect similar to NFA through the function of the failure function. The DFA-form AC-trie only maintains a state that is action-oriented, which is beneficial to the construction of the software, because in the program, it is a sequential execution code; but because each character is viewed, the state may be transferred more than once. Not conducive to the construction of hardware.

If we allow multiple states in AC-trie to act simultaneously, how they operate That is the NFA, there is no need to consider the failure function, which will be beneficial to the implementation of the hardware. In addition, because each state in AC-trie represents a unique string. We take the distance between each state and the initial state as its depth. At each time, in the same depth state, there must be only one state that is active. Because all states of the same depth represent strings of the same length but different contents, if there is more than one state at the same depth, the contradiction with the AC-trie definition is not This may happen. If we assign the same level of state to the same level, then at the hardware implementation, each level requires only one reserved state register. For example, in a set of keyword sets, the longest string is q, then we need at most q scratchpads to preserve the state of each level.

As described above, use AC-trie for searching, suitable for character-oriented A (character-oriented) approach to the processing of data, that is, based on the character to determine the information processed. That is, when AC-trie is used for string comparison, only one character and one character can be viewed, and multiple characters cannot be viewed at the same time. Similarly, the conventional hardware architecture based on AC-trie can only match one character in one clock cycle, and the highest number of aligned characters will be limited by the clock rate of the hardware.

In addition, the continuous advancement of semiconductor technology can be easily based on demand. The hardware architecture required for line design development, and more circuits can be placed in the same area. However, it is not easy to speed up the operation of the circuit, and the circuit that operates at high speed consumes more power. Therefore, taking a general-purpose processor (CPU) as an example, the solution is in a single chip. Put multiple cores in it and improve performance by parallel processing. In the same way, if the hardware device of the string comparison can view multiple characters at the same time in one comparison cycle, the performance will inevitably increase by a multiple.

The main object of the present invention is to provide a multi-character string comparison device capable of flexibly setting a data width, which is elastically set to match the number of characters in a comparison period to fully exert the performance of the hardware.

To achieve the above purpose, a multi-character string ratio that can flexibly set the data width The device is proposed to have: a regular circuit having a plurality of general rule units, each of the general rule units having at least one string input terminal, a plurality of secondary state input terminals, and a plurality of secondary state output terminals, a plurality of comparison output terminals, a first parallel connection input terminal, a second parallel connection input terminal, a first parallel connection output terminal, and a second parallel output terminal, and each of the common rule units has one a transfer rule execution unit and a logic circuit, the transfer rule execution unit performing a transfer rule based on the AC-trie based on the input data of the at least one string input end and the plurality of secondary state input ends And generating a comparison result and outputting data at the plurality of secondary output terminals and the plurality of comparison output terminals, the transfer rule execution unit having a temporary storage unit for storing a start flag and a final flag. The logic circuit performs a logic operation according to the input signal of the first parallel input, the input signal of the second parallel input, the start flag, the final flag, and the comparison result. The first parallel output terminal and the second parallel output terminal respectively generate an output signal, wherein the plurality of general rule units are divided into a plurality of subgroups, and the plurality of the general rule units in each of the subgroups The first parallel connection input terminal, the first parallel connection output terminal, the second parallel connection input terminal, and the second parallel connection output terminal are connected to each other; a state circuit having a plurality of inputs a plurality of secondary output terminals coupled to the plurality of general rule units, and a plurality of output terminals for coupling the plurality of secondary input terminals of the plurality of general rule units; and an output circuit having A plurality of inputs are coupled to the plurality of aligned outputs of the plurality of general rule units, and the plurality of outputs to generate a plurality of aligned output signals.

In an embodiment, the logical operation is: CO=/L AND M AND(F OR(CI AND/F)), and EO=/F AND((EI AND/L)OR(CI AND M AND L)), where CO represents the first parallel Output signal at the output, EO represents the output signal of the second parallel output, CI represents the input signal of the first parallel input, EI represents the input signal of the second parallel input, and F represents the start Flag, L stands for the final flag, M stands for the comparison result, / stands for the inverse operator, AND stands for logical and operator, and OR stands for logical OR operator.

The detailed description of the drawings and the preferred embodiments are set forth in the accompanying drawings.

1210‧‧‧Regular Circuit

1220‧‧‧ State Circuit

1230‧‧‧Output circuit

12101‧‧‧General Rule Unit

121011‧‧‧Transfer rule execution unit

121012‧‧‧Logical Circuit

121011a‧‧‧Processing unit

121011b, 121011c‧‧‧Multiplexer

121011d, 121011e‧‧ ‧ multiplexer

Figure 1 illustrates one of the AC-tries created by the keyword set {enhappy, happy, happen, happygo}.

Figure 2(a) shows an example of a string alignment procedure using the AC-trie of Figure 1.

2(b) is a schematic diagram showing a comparison manner of a NFA (non-deterministic finite automata) word string corresponding to FIG. 2(a).

Figure 3 (a) is a block diagram of a multi-level parallel multi-word string alignment device.

3(b)-3(c) illustrate a rule table for performing string alignment of the present invention.

4(a)-4(b) illustrate an example of string alignment in accordance with the design of the present invention.

FIG. 5 is a schematic diagram showing the transfer function of the AC-trie of FIG. 1 divided into two parts for different types according to the present invention.

Figure 6 illustrates a plurality of auxiliary transfer functions of the present invention.

7-8 illustrate an embodiment of a 1-character transfer function of the present invention.

9-10 illustrate an embodiment of a 3-character transfer function of the present invention.

Figure 11 illustrates an embodiment of an algorithm of the present invention.

FIG. 12 is a block diagram showing a preferred embodiment of a multi-character string alignment device capable of flexibly setting a data width according to the present invention.

13 is a block diagram showing an embodiment of a general rule unit shown in FIG.

14 is a circuit diagram of an embodiment of a general rule unit shown in FIG.

15 is a first parallel input terminal, a first parallel output terminal, a second parallel input terminal, and a second parallel output terminal provided by the general rule unit shown in FIG. A schematic diagram of interconnecting to form a subgroup.

Description of the hardware architecture

In order to let the reader know how the device proposed by the present invention works, the hardware architecture will be explained first, followed by the transfer rules for the hardware architecture, and then how to derive the transfer rules. Now let's explain the transfer rule by example, and the example of this description is based on the keyword set {enhappy, happy, happen, happygo}. Please refer to Figure 1 for the AC-trie created by this keyword set.

First, in order to explain the string alignment method of the present invention, we classify each state of AC-trie according to its depth to a respective level, for example, the initial state is at level 0, the depth of states 1 and 8. 1 is classified as level 1, and so on.

In order to enable the reader to understand the practice of the present invention, please refer to FIG. 3( a ), which is a block diagram of an embodiment of a multi-hierarchical parallel multi-word string alignment device having seven hierarchical units. Parallel to 3 characters. This embodiment parallels 3 characters in a comparison period, so the first 6 hierarchical units are serially connected into 3 pipelines, each of which includes 2 pipelines. Hierarchy unit. The first to third hierarchical units correspond to level 0, and the hierarchical units STG(1) and STG(2) respectively handle the case where only the last two characters and the last character of the pattern character are matched. The hierarchical units STG(4) to STG(6) correspond to the levels 1 to 3, and the levels 4 and subsequent states are collectively corresponding to the hierarchical units STG(7). The first six hierarchical units operate in the same way as the NFA. The last hierarchical unit, the hierarchical unit STG(7), operates in the same way as DFA. In addition, a priority multiplexer pmux(0) is included for determining the CUR_ST sent to the hierarchical unit STG(7) by the NX outputted by the hierarchical units STG(4)~STG(7). In addition, the priority multiplexer pmux(1)~(3) is used to determine the comparison output OP(1)~OP(3) for selecting the final comparison output from the comparison output of the seven hierarchical units.

The hierarchy and pipelines of this block diagram are only used to illustrate the architecture of the present invention. In a practical application, the number of pipelines is determined by the number of characters in a parallel alignment, and the number of classes is determined by application requirements. .

Transfer rule description

Figures 3(b) and 3(c) illustrate a rule table having a total of 30 transfer rules, which are generated according to the aforementioned keyword set and belong to 7 hierarchical units. FIG. 3(b) shows the first to the 19th rules, which are the rules of the hierarchical units (7) and (6), and 3(c) shows the rules of the other hierarchical units.

The transfer rules in this rule table are ranked in order of priority from highest to lowest. Wherein, the rule of the later hierarchical unit has higher priority than the rule of the preceding hierarchical unit, for example, the priority of the rule of the hierarchical unit (7) is higher than the rule of the hierarchical unit (1) to (6), so the hierarchical unit The rules of (7) are placed at the top. In the same hierarchical unit, the rules with the exact matching pattern characters have higher priority, for example, considering rules 6 and 7, which are in the same hierarchical unit (7), because the rule 6 is completely (exact) compares the input 3 characters, while rule 7 only compares before Two input characters, and the first two characters of rule 6 and rule 7 are also "py", so when rule 6 is triggered, rule 7 will also be triggered, but the output is compared. It is determined by Rule 6 with higher priority. Rule 6 will simultaneously determine the comparison output and the secondary state corresponding to the three input characters, while rule 7 only determines the comparison output corresponding to the first two input characters, but does not affect the secondary state and corresponds to the third input. The output of the characters is compared.

The first column of the rule table is the rule number (rule no), and the rule number is only for the square. It is stated that there is no substantial effect and the data of the rule number is not stored in the rule unit. The second column of the rule table is the stage number, which represents the hierarchical unit to which this rule belongs. According to the circuit architecture described above, the hierarchical number - used to indicate the hierarchical unit to which the rule belongs - does not need to be stored in the scratchpad. However, in the circuit architecture to be described later, the hierarchical number must be stored in the rule unit because it is used to control the associated data transmission circuit to select the input data of the rule unit and determine the location of the output data, thereby achieving the foregoing plurality. The same function of the hierarchy unit.

The other fields of the rules table can be roughly divided into pattern data and output resources. The sample data includes fields PMASK, P_ST, and P_CHRS, wherein the field PMASK is a pattern mask, the field P_ST is the current state, and the field P_CHRS is a pattern character. The output data includes fields OMASK, NX_ST, and OP1~OP3. The field OMASK is the output mask, the field NX_ST is the secondary state, and the fields OP1~OP3 are the comparison outputs.

The number of pattern characters P_CHRS corresponds to the number of characters of the parallel alignment, for example, In this example, three characters are compared at a time, and each transfer rule has three pattern characters. The bits of the pattern mask PMASK sequentially correspond to the current state P_ST and the individual pattern characters P_CHRS, such as the Most Significant Bit (MSB), that is, the bit 3 of the PMASK (bit 3). , corresponding to the current state P_ST, and the next highest bit, that is, bit 2 of PMASK (bit 2), corresponding to the first pattern character, the Least Significant Bit (LSB), that is, bit 0 (bit 0) of PMASK, corresponding to the last pattern character. However, here is only a data representation of a pattern mask, and is not limited to this method. Those skilled in the art can easily design different data representation manners to achieve the functions mentioned herein. .

When the corresponding pattern mask bit is '1', it indicates that the corresponding template is to be matched. Material, and when it is '0', it means that the corresponding pattern data is don't care. For easy resolution, the wildcard character is used in P_CHRS. 'To indicate that the corresponding template character is don't care. For example, when bit 2 (bit 2) and bit 1 (bit 1) of PMASK in the transfer rule of the hierarchical unit (1) are both '0' and bit 0 is '1', then the first and the first of P_CHRS 2 sample characters are '? ', indicating that regardless of the first and second input characters, it is a match, only the actual comparison of the third input character. The P_CHRS of the hierarchical unit (2) is only required to match the second and third characters. The current status of the P_ST system data in the rules table. The previous hierarchical units (1)~(3) have no current state P_ST, and only the input characters and the pattern characters P_CHRS are compared. However, in order to make the rules format consistent, the P_ST of the pattern data is marked. And it is determined by bit 3 of PMASK in the transfer rule whether or not to compare the current state.

The transfer rule table shows the layer of AC-trie corresponding to each hierarchical unit. The P_ST of the pattern data of the transfer rule such as the hierarchical unit (1) to (3) is 0, which represents the P_ST of the pattern data corresponding to the level 0 and the transfer rule of the other hierarchical unit (4). It is 1 and 8, which is at level 1 of AC-trie, and represents hierarchical unit (4) corresponding to level 1. In addition, the P_ST of the pattern data of the transfer rule of the hierarchical unit (5) is 2 and 9, which is at level 2 of AC-trie, and represents that the hierarchical unit (5) corresponds to the level 2. Similarly, the hierarchical unit (6) can correspond to the level 3 of the AC-trie. However, the hierarchical unit (7) corresponds to the level 4 of the AC-trie and all subsequent levels.

If a transfer rule of the pattern data and the input CUR_ST and If the IN_CHRS matches, the transfer rule is triggered. The triggered transfer rule whose output data may be used to determine the secondary state NX of the hierarchical unit to which the rule belongs and the comparison output OP(1)~OP(3).

NX_ST in the transfer rule is the next state (next state), in each comparison week During the period, the secondary state of the highest priority rule in the triggered rule in the same hierarchical unit is sent to the hierarchical unit behind the same pipeline. For example, in this example, three characters are aligned at a time, and the hierarchical unit is 3) The determined secondary state is sent to the hierarchical unit (6) as the current state, and the secondary state determined by the hierarchical unit (4) is sent to the hierarchical unit (7). If no transfer rule is triggered, the secondary state of the output of the hierarchical unit is zero. OP1, OP2, and OP3 in the transfer rule are comparison outputs corresponding to the first, second, and third input characters, respectively. Similarly, in each comparison cycle, the highest priority comparison output among the triggered transition rules in the same hierarchical unit is treated as the hierarchical unit comparison output.

Output mask OMASK highest bit (MSB), which is the above rule OMASK Bit 3 (bit 3) corresponds to the secondary state NX_ST. The remaining bits are sequentially corresponding to individual output strings, such as the next highest bit, that is, bit 2 (bit 2) of the output mask OMASK, corresponding to the first comparison output OP1, and the lowest The bit (LSB), which is the bit 0 (bit 0) of the output mask OMASK, corresponds to the last comparison output OP3. When a certain bit of OMASK is '0', it indicates that the corresponding data is not valid. For example, bit 3 and bit 0 (bit 3 and bit 0) of OMASK of transfer rule 5 are both '0', indicating that The rules NX_ST and OP3 are not valid, that is, when this rule is triggered, it is not used to determine the secondary state, and does not determine the conforming string output corresponding to the third character of the input character. From the rules table, we can see that when When the character in the pattern character P_CHRS of the shift rule is a wildcard character, the bit 3 (bit 3) of the output mask OMASK will be '0', indicating that the rule only determines The corresponding alignment output does not determine the next state. For example, in rule 4, since its pattern character P_CHRS is "y?'?", the rule 4 does not determine the secondary state.

Since the length of the output string is not fixed, in order to facilitate the design of the hardware, it can be used The status register stores a status code corresponding to the aligned output string, such as transfer rule 3 in the rules table, OP3 is "happygo", and the corresponding status string 16 represents the output string. In the above-described rule table, although the output string is represented only by the number of the state, it is easy for a person skilled in the art to realize the practice of outputting the string by code.

String comparison example

In order to further understand the operation of the present invention, please refer to FIG. 4(a) and FIG. 4(b), which are illustrated as an example of alignment. The input string to be compared is "enhappenhappygo", we compare three characters at a time, so we divide the string into several segments "enh", "app", "enh", "app" And "ygo", in order to compare.

Initialize the state of all registers before comparing them. In the first comparison cycle, according to the input character "enh", rule 25 and rule 30 will be triggered, wherein rule 30 belongs to hierarchical unit (1) and rule 25 belongs to hierarchical unit (3). Rule 30 will determine the secondary state as 8, and this result will be sent to the hierarchical unit (4) that is concatenated behind the hierarchical unit (1), and is treated as the current state by the hierarchical unit (4) in the next comparison period. Rule 25 will determine the secondary state to be 3, and this result will be sent to the hierarchical unit (6) that is concatenated behind the hierarchical unit (3), and will be regarded as the current state by the hierarchical unit (6) in the next comparison period. The aligned outputs determined according to the two triggered rules are all empty strings.

In the second comparison cycle, according to the input character "app" and the previous comparison period The determined secondary state will trigger rule 16 and rule 24, where rule 24 belongs to hierarchy unit (4) and rule 16 belongs to hierarchy unit (6). Rule 24 will determine the secondary state to be 11, and rule 16 will determine the secondary state to be 6. The secondary states determined by the hierarchical units (4) and (6) are sent to the priority multiplexer pmux(0). Since the output of the hierarchical unit (6) has a higher priority order, the priority multiplexer pmux(0) determines the secondary state to be 6 and sends it to the last hierarchical unit (7) for the next comparison. The period is regarded as the current state by the hierarchical unit (7). In addition, the comparison outputs determined by the two triggered rules are all empty strings.

In the third comparison cycle, according to the input character "enh" and the previous comparison period The determined secondary state will trigger rule 13, rule 25 and rule 30, where rule 30 belongs to hierarchical unit (1), rule 25 belongs to hierarchical unit (3), and rule 13 belongs to hierarchical unit (7). Rule 13 does not determine a valid secondary state, but determines that the comparison output OP2 is 14, which is "happen". Rule 30 will determine the secondary state as 8, and this result will be sent to the hierarchical unit (4) that is concatenated behind the hierarchical unit (1), and is treated as the current state by the hierarchical unit (4) in the next comparison period. Rule 25 will determine the secondary state to be 3, and this result will be sent to the hierarchical unit (6) connected in series to the hierarchical unit (3), which is regarded as the current state by the hierarchical unit (6) in the next comparison period. According to the triggered rule, the priority comparison output OP2 is determined by the priority multiplexer pmux(2) to be 14, and both OP1 and OP3 are empty strings. After the comparison period is indicated, the comparison result corresponding to the second input character is "happen".

In the fourth comparison cycle, according to the input character "app" and the previous comparison period The determined secondary state will trigger rule 16 and rule 24, where rule 24 belongs to hierarchy unit (4) and rule 16 belongs to hierarchy unit (6). Rule 24 will determine the secondary state to be 11, and rule 16 will determine the secondary state to be 6. The sub-states 11 and 6 output by the hierarchical units (4) and (6) are prioritized by the priority multiplexer pmux(0) After the rule comparison, the secondary state 6 is output to the last hierarchical unit (7) to be regarded as the current state by the hierarchical unit (7) in the next comparison cycle. In addition, the comparison outputs determined by the two triggered rules are all empty strings.

In the fifth comparison period, according to the input character "ygo" and the secondary state determined by the previous comparison period, rule 11 and rule 12 are triggered, both of which belong to the hierarchical unit (7). Rule 11 will determine that the secondary state is 16 and the comparison output OP1 is 7 and OP3 is 16, wherein the output corresponding to state 7 is "enhappy happy" and the output corresponding to state 16 is "happygo". Rule 11 does not determine a valid secondary state, but the comparison output OP1 is 7. Therefore, the hierarchical unit (7) determines that the secondary state is 16, and still returns the hierarchical unit (7) as the current state of the next comparison cycle. Since rule 11 has a higher priority, it is determined that the final comparison output OP1 is 7 and OP3 is 16, and the comparison output OP2 is an empty string.

Derivation and rule generation of multi-character transfer function

The present invention proposes a simple and efficient method for generating parallel-directed multi-word transfer rules based on the original AC-trie. The method of generating a transfer rule proposed by the present invention will be described below.

Before deriving the multi-character transfer rule, the present invention first obtains a 1-character transition function from the forward function and the failure function of the original AC-trie, and then uses the single character transfer function. Based on this, a multi-character transition function is derived, and the derived multi-character transfer function produces the required transfer rules.

Wherein, the transfer function NX ₁ (0, "{e, h}) = 0 from the initial state 0, "{e, h} refers to any character other than 'e' and 'h', implemented here In the rules described in the examples, the present invention is a wildcard character '? 'To show, in hardware implementation, it is implemented in the form of a mask, that is, the corresponding pattern mask bit is set to '0', so that it conforms to any character, but because it will have With the character '? The priority of the 'rules' is placed after the rules that are completely aligned, so the result of the complete comparison will give priority to the final result.

In AC-trie, if a state's failure function points to an initial state The state indicates that there is a common prefix between the two states. Therefore, when the transition rules corresponding to all states do not match, the transfer rule starting from the initial state will be compared. Based on this fact, when the alignment of a plurality of characters is processed in parallel, with the characteristics of the hardware, a plurality of rules can be simultaneously applied to parallelly match the characters of the different portions.

In addition, the number of characters in the parallel alignment, regardless of the number of states, will still be Stay the same, the same as the original AC-trie. Because, according to the transfer rules of different digital elements established by the same keyword, the same input string is processed, and the obtained state must be the same, so that the transfer rules of these different digital elements can be used to compare the same keywords. .

To illustrate the derivation process, the present invention defines a k-character transfer function NX _k (S ₁ ,T)=S ₂ , where S ₁ is the current state, T is a string of k characters, and S ₂ is a secondary state. . The meaning of this transfer function is that the current state is S ₁ , and after accepting the input string of the k character, the state is converted to S ₂ . For example, a 3-character transfer function NX ₃ (1, nha) = 4, whose current state is 1, and after accepting the 3-character string "nha", its state will be converted to 4. Corresponding to the 3-character string comparison device is a 3-character transfer function.

In addition, the present invention refers to the transfer function NX _k ( S ₂ , T ₂ )= S ₃ as a subsequent transition function of the transfer function NX ₁ ( S ₁ , T ₁ )= S _e , if S ₂ = S _e , which indicates that the initial state of NX _k ( S ₂ , T ₂ )= S _{3 is} the end state of NX ₁ ( S ₁ , T ₁ )= S _e .

The invention can be newly obtained by concatenating a transfer function and its subsequent transfer function Multi-character transfer function. This concatenating operation is defined as follows.

Definition (serial connection of two transfer functions): given a k- character transfer function NX _k ( S ₁ , S ₁ )= S ₂ and a 1- character transfer function NX ₁ ( S ₂ , T ₂ ) = S _3, wherein S _1, S _2, and S ₃ is at the state (state), and T ₁ and T ₂ each character string is k (k -character string) and the string of characters l (l -character string Then, concatenating the two transfer function can obtain a ( k + l ) character transfer function NX _{k + l} ( S ₁ , T ₁ T ₂ )= S ₃ .

In addition, the present invention defines a pseudo state and two auxiliary rotations. "assistant transition function". In Fig. 9, the symbol '-' represents a virtual state, which is a state that is virtually defined in order to constitute a complete transfer function in the derivation process, and is not a state actually existing in the AC-trie. Also, the symbol '? 'Represents an arbitrary character. Next, the present invention defines two auxiliary transitions to assist in constructing the complete multi-character transition functions of the output state.

The first auxiliary transfer function is defined as NX ₁ (-,?)=-, which is transferred from a virtual state to another pseudo state according to an arbitrary character (transits from a pseudo state to another pseudo state on an arbitrary character) .). The second sub-transfer function is defined as _{NX 1 (S op,?)} = -, which according to a line of arbitrary characters is transferred from an output state to a virtual state S _{op (transits from an output state S op} to a pseudo state On an arbitrary character.)

Figure 6 illustrates several auxiliary transfer functions as defined above. In order to distinguish it from the actual transfer function, the auxiliary transfer function is indicated by a broken line in the figure. NX ₁ (0,?) = 0 is not the auxiliary transfer function defined above, but is based on the original AC-trie NX ₁ (0, "{e, h}) = 0, to match the character '? 'Replaced by {e,h}, it is used to solve the problem of alignment. The auxiliary transfer function NX ₁ ( S _op ,?)=- is used to save the matching output of the output state S _op . Therefore, each of the states of the aligned output will have an auxiliary transfer function indicated by a broken line to assist in the derivation of the multi-word transfer function, such as states 7, 12, 14, and 16. NX ₁ (-,?)=- is an additional one-character auxiliary transfer function to assist in constructing a complete multi-word transfer function after the output state. Wildcard character '? 'and virtual state'-' is proposed to construct a multi-character transfer function. In the actual transition rule, the corresponding bit of the pattern mask PMASK and the output mask OMASK is used to control the corresponding behavior.

The derivation process is further illustrated by an example of a 3-character transfer function.

The invention is based on AC-trie when deriving the multi-word transfer function. Based on the 1-character transfer function, the desired multi-word transfer function is obtained by repeated concatenation operations. Based on the hardware architecture proposed by the present invention, the present invention obtains the required 1-character transfer function in two ways, the first of which is used to derive the transfer function used by the hierarchical elements constituting the pipeline, and the second It is used to derive the transfer function used by the last hierarchical unit.

The following description is based on the architecture of a 7-level 3-character string comparison device. Figure 5 As shown, the present invention is divided into two parts according to the AC-trie of Fig. 1, the left half containing the level 0 to 3 state, and the right half containing the level 4 and above. The left half is the transfer function used to push the hierarchical unit of the conduit line, and the failure function is not considered, so the dotted line indicating the failure function is removed. The right half is used to derive the transfer function used by the last hierarchical unit, which still retains the failure function. The boundary points of the left half and the right half are determined according to the number of hierarchical units of the preceding string comparison device. For example, in the embodiment of FIG. 4, there are six hierarchical units constituting three pipelines, that is, operating in an NFA manner. The level of Ac-trie is 0 to 3.

FIG. 7 illustrates a 1-character transfer function of levels 0 to 3, wherein the character transfer function in the figure is directly obtained from the forward function in AC-trie of FIG. 1 because the failure function is not considered. . As shown in Figure 7, a character transfer function starting from the state of the same level is grouped together. For example, in the (a) group, it is a character transfer function of level 0, and at level 0, there is only an initial state (initial state). As mentioned earlier, the transfer function NX ₁ (0,?) = 0 is used to process the alignment problem in which the keyword is not aligned with the input start character. (b) The group is a character transfer function of level 1, and level 1 includes states 1 and 8. (c) Group is a character transfer function of level 2, and level 2 includes states 2 and 9. (d) Group is a character transfer function of level 3, and level 3 includes states 3 and 10.

Figure 8 illustrates a 1-character transfer function of levels 4 through 7, wherein the 1-character transfer function derived from the failure function is indicated by a dashed line. (a) The group is a 1-character transfer function of level 4, and level 4 includes states 4 and 11. (b) The group is a 1-character transfer function of level 5, and level 5 includes states 5, 12, and 13, where state 12 has a matching output, so the auxiliary transfer function NX ₁ (12,?) = -. (c) The group is a 1-character transfer function of level 6, and level 6 includes states 6, 14, and 15, wherein state 14 has more auxiliary transfer functions NX ₁ (14,?)=-; state 6 fails The function points to state 11 and has a transfer function NX ₁ (6,e)=13. In order to make the reader easy to separate, the transfer function added by the failure function is indicated by a broken line. (d) The group is a 1-character transfer function of level 7, and level 7 includes states 7 and 16, where state 7 has a transfer function NX ₁ (7, g) = 15 due to the failure function pointing to state 12; State 16 has more auxiliary transfer functions NX ₁ (16,?)=-.

9 and FIG. 10 are diagrams for explaining a derivation process of obtaining a 3-character transition function by a concatenation operation according to the aforementioned 1-character transfer function, wherein the symbol '+' represents two transfer functions. Serial connection. Figure 9 shows the 3-character transfer function used by the first 6 hierarchical units, and Figure 10 shows the 3-character transfer function used by the 7th hierarchical unit, where the left of '=>' The process of serial connection, the right side of '=>' is the result of serial connection. For the sake of clarity, only the comparison output of the non-empty string is indicated in FIGS. 9 and 10, and the comparison output is an empty string, and is not indicated.

In Fig. 9, the derivation process of the 3-character transfer function of the hierarchical 1 is shown, which is preceded by concatenating the two preceding NX ₁ (0, ?) = 0, and then respectively with the 1 of the state 0 The character transfer function NX ₁ (0, e )=1 and NX ₁ (0, h )=8 are connected in series to obtain two 3-character transfer functions NX ₃ (0,?? e )=1 and NX ₃ (0,?? h )=8, where the first two transfer functions NX ₁ (0,?)=0 indicate that the state continues to be in the initial state until the third character matches 'e' or 'h'. Transfer to state 1 or 8 of level 1. Similarly, in the derivation of the 3-character transfer function of the stratum 2 shown, it is first to concatenate the two 1-character transfer functions of NX ₁ (0,?)=0 and state 0, and then Two congruent transfer functions NX ₃ (0,? en )=2 and NX ₃ (0,? ha )=9 are obtained by concatenating with the subsequent transfer functions of states 1 and 8, respectively.

Hierarchical 1 and 2 3-character transfer functions can be used to solve multi-word string alignment Align problem (aligmnent problem). The 3-character transfer function of level 1 is no more than the first two characters. 'Represents that only the last character is compared, so it is a transfer function that aligns the beginning of the same pattern with the third character of the input string. The 3 character transfer function of level 2 is no better than the first character - with wild characters '? ' indicates that only the last two characters are compared, so it is a transfer function that aligns the beginning of the same version with the second character of the input string.

According to the foregoing manner, the 3-character transfer function of the hierarchy 3 to 7 can be derived through the concatenation operation.

In accordance with the foregoing description, a multi-character transfer function of any number of characters can be readily derived by one of ordinary skill in the art. After deriving the multi-character transfer function, the resulting multi-character transfer rule can be derived from this result.

Algorithm

Hereinafter, the present invention will be described by a program algorithm based on a 1-character transfer function. The practice of generating a k-character transfer function. It is very straightforward to derive the 1-character transfer function from the original AC-trie. According to the foregoing description, the person skilled in the art can easily achieve this practice, so in this description, the relevant part is skipped. Narration. Please refer to the algorithm illustrated in FIG. 11 for the following description.

The input parameter k of the algorithm is the number of characters to be aligned in parallel. Input parameters NXSET contains the original 1-character transfer function, and the result of the algorithm is the k-character transfer function stored in the variable TRSET. The returned k-character transfer function is used to generate the multi-word transfer rules required by the string alignment device of the present invention.

This algorithm is based on a multi-layer loop for each state of the original AC-trie The corresponding k-character transfer function is derived. In the second line of the beginning, clear TRSET. In the loop between the 3rd line and the 21st line, all of the corresponding k-character transfer functions are derived for each state Si in the AC-trie. In line 5, all 1-character transfer functions of state Si are copied to NSET.

Repeat the k-1 line between the 7th line and the 19th line, in the form of iteration The Si character transfer function of Si and its subsequent k-1 1-character transfer function are used to obtain the k-character transfer function of Si. After repeating the loop between line 7 and line 19 of k-1 times, NSET contains all the k-character transfer functions starting from Si. On line 20, add NSET to TRSET, then back to line 5 and continue processing the next state. When all the states are processed, the algorithm ends.

The loop between line 7 and line 19 is then discussed further. On line 8, empty TMPSET. The loop between line 10 and line 17 is based on each transfer stored in NSET The function NXi is executed once. On line 11, assign the secondary state of NXi to NX_ST. The loop between lines 13 to 16 is executed once for each transfer function NXj starting with NX_ST. In line 14, the transfer function NXj is concatenated with the transfer function NXi to obtain a new transfer function NEW_TR. On line 15, add NEW_TR to TMPSET. Among them, the number of pattern characters of the transfer function NEW_TR will be one more than the number of pattern characters of the transfer function NXi. In the foregoing concatenation process, the derived multi-word transfer functions may all be composed of auxiliary transfer functions. In the 22nd line, the useless transfer function is removed.

According to the description of the foregoing algorithm, after deriving the multi-word transfer function, A multi-word transfer rule applied to the string comparison device of the present invention is generated based on the derived multi-word transfer function. After the k-character transfer rule is established, the order of the rules needs to be rearranged, wherein the rules set by the later classes have higher priority, for example, the priority of the hierarchy 7 is the highest, and the priority of the hierarchy 1 is the lowest. . In the same hierarchy, the pattern of exact matching patterns is prior to the partially matched pattern. For example, in the rule table of Figures 3(a)-3(b), it is a rule that starts with the same state (p_st field in the table), for example, rules 3 and 4 start with state 11, The pattern string of rule 3 is "ygo", and the pattern string of rule 4 is "y?'?", the last two characters of the latter are not aligned, so rule 4 has a lower priority.

A simple approach is to sort by the hierarchy and then in the same class, then Sorting according to the binary value of the pattern mask PMASK - the numerical order has a higher priority. For example, the PMASK of rule 3 is "1111", while the PMASK of rule 4 is "1100", and "1100" is less than "1111", so rule 4 is listed later. Although the rules of the foregoing embodiments are not ordered according to the binary values of the pattern mask PMASK, those skilled in the art of the present invention should be able to easily follow the method. Implementation.

For the 1-character transfer function, the comparison output of each transfer function (matching Output) can be represented by the second state. However, for a multi-character transfer function, such as a k-character transfer function, where k>1, if each k-character transfer function outputs only the secondary state, information about the state passing through it will be hidden. . In such a case, only the aligned output corresponding to the last input character can be known, and the aligned output corresponding to the previous k-1 input characters will be missed. Therefore, when using the aforementioned algorithm to derive a multi-word transfer function, the alignment result corresponding to each character must be retained in the process of concatenation. Although this part is not mentioned in the description of the aforementioned algorithm, the person skilled in the art of the present invention should be able to easily achieve it.

Based on the foregoing principles, the present invention proposes an elastically configurable data width Multi-word string alignment architecture to improve string alignment efficiency.

Please refer to FIG. 12, which illustrates the multi-character word of the flexible width of the present invention. A block diagram of a preferred embodiment of a string comparison device. As shown in FIG. 12, the device includes a regular circuit 1210, a state circuit 1220, and an output circuit 1230.

The rules circuit 1210 has M general rule units 12101. Please refer to FIG. 13, which illustrates a block diagram of an embodiment of a general rule unit 12101. As shown in FIG. 13, the general rule unit 12101 has at least one string input terminal IN-CHRS, a plurality of secondary state input terminals N _XI , a plurality of secondary state output terminals N _XO , a plurality of comparison output terminals OP, and a first The input terminal CI, a second parallel input terminal EI, a first parallel output terminal CO, and a second parallel output terminal EO, and each of the general rule units 12101 each have a transfer rule execution unit 121011 And a logic circuit 121012.

The transfer rule execution unit 121011 generates a transfer rule based on the AC-trie based on the input data of the at least one string input terminal IN-CHRS and the plurality of secondary input terminals N _XI to generate a transfer rule. Comparing the result M and outputting data at the plurality of secondary output terminals N _XO and the plurality of comparison output terminals OP, the transfer rule execution unit 121011 has a temporary storage unit (not shown) for storing one Rule data, a starting flag F and a final flag L.

The logic circuit 121012 is based on the input signal of the first parallel input terminal CI, The second parallel input signal EI, the start flag F, the final flag L, and the comparison result M are logically operated to connect the first parallel output terminal CO and the second parallel The output EO generates an output signal, respectively.

Please refer to FIG. 14 , which illustrates a circuit diagram for implementing the transfer rule execution unit 121011 and the logic circuit 121012. As shown in FIG. 14, the transfer rule execution unit 121011 is executed by a processing unit 121011a, a multiplexer 121011b, a multiplexer 121011c, a demultiplexer 121011d, and a demultiplexer 121011e. Based on one of the transfer rules established by the trie, a comparison result M is generated and the data is outputted at the plurality of secondary output terminals N _XO and the plurality of comparison outputs OP. The processing unit 121011a internally has a temporary storage unit (not shown) for storing a rule data, a start flag F and a final flag L. The processing unit 121011a compares the input CUR_ST, XC1, and XC2 with the stored rule data. When it is a match, the comparison result M is 1, otherwise the comparison result M is 0.

The signal ST_SEL of the processing unit 121011a is used to control the multiplexer 121011b to Select the corresponding status value as the current status of the input CUR_ST. The signal NX_SEL is used to control the demultiplexer 121011d to send the secondary NX_ST to the corresponding output. SEQ_NO is used to control the multiplexer 121011c to select the corresponding input character, and to control the demultiplexer 121011e to send the comparison outputs XOP1 and XOP2 to the corresponding outputs. Among them, the solution multiplexer 121011d and 121011e are in the signal The output is only when EN is 1.

The logic circuit 121012 is mainly used to perform a logic operation, and its contents are as follows: CO=/L AND M AND(F OR(CI AND/F)), and EO=/F AND((EI AND/L)OR(CI AND M AND L)), where / represents an inverting operator, AND represents a logical and operator, and OR represents a logical OR operator.

In operation, the plurality of general rule units 12101 are divided into a plurality of subgroups, and the plurality of the common rule units 12101 in each of the subgroups are by the first parallel input terminal CI, the first The output terminal CO, the second parallel input terminal EI, and the second parallel output terminal EO are connected to each other.

To further illustrate the role of the general rule unit, an example will be described below. Each general rule unit can process 2 input characters. In this example, 3 general rule units are connected into a group, and thus can be used to process a 6-character transfer rule, in this example NX ₆ (0, Happyg )=15, where a corresponding alignment output OP5 corresponding to the fifth input character has a value of 12. This 6-character transfer rule is generated according to the aforementioned algorithm. Referring to FIG. 15 , the three general rule units 12101 are configured by the first parallel input terminal CI, the first parallel output terminal CO, the second parallel input terminal EI, and the second A schematic diagram in which the output terminals EO are connected to each other to form a subgroup to compare six characters (C1-C6) at a time. As shown in FIG. 15, the general rule unit 12101 of F=1 is the start general rule unit, that is, the rule unit 1, whose SEQ_NO=1, so that the selected characters C1 and C2 are input characters. The intermediate general rule unit 12101, that is, the rule unit 2, has both F and L 0, and its SEQ_NO=2, so the selected characters C3 and C4 are input characters. The general rule unit 12101 of L=1 is the final general rule unit, that is, the rule unit 2, and SEQ_NO=3, so the selected characters C5 and C6 are input characters. And when the comparison result of the foregoing three rule units is met, only the final general rule unit outputs the state NX. In this way, we can pick up the required data width to perform a multi-character string comparison program.

Additionally, state circuit 1220 has a plurality of inputs coupled to said plurality of secondary output terminals N _{XO of} said plurality of general rule units, and a plurality of outputs coupled to said plurality of said plurality of general rule units Secondary input N _XI . The state circuit 1220 determines the state values of the plurality of secondary inputs N _XI in accordance with one of the plurality of secondary outputs N _XO , and the priority is determined according to the transfer rule. The state circuit 1220 has a temporary storage unit (not shown) for storing state values for storing the determined secondary states. The output circuit 1230 has a plurality of inputs for coupling the plurality of aligned output terminals OP of the plurality of general rule units, and a plurality of outputs for generating a plurality of aligned output signals MOP. The output circuit 1230 determines the content of the plurality of comparison output signals MOP according to a priority order of the plurality of comparison output terminals OP, and the priority order is also determined according to the transfer rule.

So far, the content of the present invention has been disclosed in detail, and the data width can be flexibly set according to its According to the design of the degree, the present invention can flexibly set the number of characters to be matched as needed to fully exert the performance of the hardware.

The present invention is the preferred embodiment, and the source is changed or modified locally. Those who are acquainted with the technical idea of the case and who are familiar with the skill can not deduct the patent right of the case.

In summary, this case shows its difference in terms of purpose, means and function. In the technical characteristics of Xizhi, and its first invention is practical and practical, it is also in compliance with the patent requirements of the invention. Please ask your review committee to inspect it and pray for an early patent.

12101‧‧‧General Rule Unit

Claims (2)

A multi-character string matching device capable of flexibly setting a data width, comprising: a rule circuit having a plurality of general rule units, each of the general rule units having at least one string input end and a plurality of sub-states An input end, a plurality of secondary output terminals, a plurality of comparison output terminals, a first parallel connection input terminal, a second parallel connection input terminal, a first parallel connection output terminal, and a second parallel connection output terminal, Each of the general rule units has a transfer rule execution unit and a logic circuit, and the transfer rule execution unit performs an AC according to the input data of the at least one string input terminal and the plurality of secondary state input terminals. -trie generates a comparison result based on one of the transfer rules, and outputs data at the plurality of secondary output terminals and the plurality of comparison outputs, the transfer rule execution unit has a temporary storage unit for storing a start flag and a final flag, the logic circuit is based on the input signal of the first parallel input, the input signal of the second parallel input, the start flag, the final flag, and the Performing a logic operation on the comparison result to generate an output signal at the first parallel output end and the second parallel output end, wherein the plurality of general rule units are divided into a plurality of subgroups, and each of the sub-groups The plurality of the general rule units in the group are mutually coupled by the first parallel input, the first parallel output, the second parallel input, and the second parallel output a state circuit having a plurality of inputs for coupling the plurality of secondary outputs of the plurality of general rule units, and a plurality of outputs for coupling the plurality of times of the plurality of general rule units And an output circuit having a plurality of inputs for coupling the plurality of aligned outputs of the plurality of general rule units and a plurality of outputs for generating a plurality of aligned output signals. The multi-character string alignment device capable of flexibly setting a data width as described in claim 1, wherein the logical operation is: CO=/L AND M AND(F OR(CI AND/F)) And EO=/F AND((EI AND/L)OR(CI AND M AND L)), wherein CO represents an output signal of the first parallel output, and EO represents an output signal of the second parallel output CI represents the input signal of the first parallel input, EI represents the input signal of the second parallel input, F represents the start flag, L represents the final flag, and M represents the comparison As a result, / represents an inverting operator, AND represents a logical and operator, and OR represents a logical OR operator.