String matching method

A string matching device extracts a string by shifting a start position from an input data stream, compares the extracted string with a sub-string included in a target string, and when a prefix of a target string is detected from the string extracted from the input data stream, it selects one of the strings output in the next stage based on the start position of the corresponding string and uses it to detect the sub-string. Also, the device can consecutively detect at least one target string from the input data stream by using a state transition process.

CROSS-REFERENCE TO RELATED APPLICATION

This application claims priority to and the benefit of Korean Patent Application No. 10-2009-0082086 filed in the Korean Intellectual Property Office on Sep. 1, 2009, the entire contents of which are incorporated herein by reference.

BACKGROUND OF THE INVENTION

(a) Field of the Invention

The present invention relates to a string matching method.

(b) Description of the Related Art

Recently, factors that threaten information security on the network have appeared in complex and various manners. Also, these threatening factors can occur in all layers of packets that are transmitted through the network.

Accordingly, network equipment and communication terminals provide various functions for sensing and intercepting such. Particularly, various types of pattern matching skills are utilized to find specific patterns relating to the threatening factors. The pattern matching skill starts by finding characters of strings that are included in the packets.

Recently, it has been possible to transmit packets at a high speed through the network due to the development of communication networks. However, the conventional string matching or pattern matching skills have difficulty in parallel processing and thus have a restriction in high-speed data processing.

SUMMARY OF THE INVENTION

The present invention has been made in an effort to provide a string matching method for efficiently matching strings for high-speed data streams that are transmitted through the network.

An exemplary embodiment of the present invention provides a string matching method by a string matching device including: dividing each of a plurality of target strings into at least one sub-string; extracting a plurality of strings from an input data stream; generating a third string by combining a first string and a second string before the first string from among the plurality of strings; extracting a plurality of fourth strings with different start positions from the third string; detecting the sub-string from among the fourth strings; and detecting one of the target strings based on the detected sub-string.

Another embodiment of the present invention provides a string matching method by a string matching device including: dividing each of a plurality of target strings into at least one sub-string; dividing the most significant sub-string from among the at least one sub-string as a prefix for the respective target strings; extracting a plurality of strings with different start positions from an input data stream; detecting a prefix corresponding to one of the plurality of strings from among the prefixes for the plurality of target strings; selecting a string from among the plurality of strings based on a control signal; detecting a sub-string corresponding to the selected string from among the sub-strings except the prefix; determining whether to change the control signal according to the prefix detecting result and the sub-string detecting result; and detecting one of the plurality of target strings based on the detected prefix and the detected sub-string.

Another embodiment of the present invention provides a string matching method by a string matching device including: dividing each of a plurality of target strings into at least one sub-string; dividing the prefix that is the most significant sub-string from among the at least one sub-string and other sub-strings excluding the most significant sub-string for respective target strings; setting a state value of each of the other sub-strings; setting next state values of the at least one sub-string based on the order of the at least one sub-string and the state values; extracting a plurality of strings with different start positions from an input data stream; detecting a sub-string corresponding to at least one string from among the plurality of strings based on a state variable; updating the state variable with one next state value corresponding to the detect sub-string from among the next state values of the at least one sub-string; and detecting one of the target strings based on the state variable and the detected sub-string.

DETAILED DESCRIPTION OF THE EMBODIMENTS

A string detecting method and device according to an exemplary embodiment of the present invention will now be described in detail with reference to accompanying drawings.

A string matching method and device according to a first exemplary embodiment of the present invention will now be described in detail with reference toFIG. 1toFIG. 4.

FIG. 1shows a configuration diagram of a string matching device according to a first exemplary embodiment of the present invention, andFIG. 2shows a configuration diagram of a string according to a first exemplary embodiment of the present invention.

Referring toFIG. 1, the string matching device100includes an input buffer101, a delay buffer102, a distributor103, a memory104, a comparator105, a concatenation circuit106, and an encoding circuit107.

The input buffer101arranges an input data stream in a predetermined size to generate a string stream, and sequentially outputs a plurality of strings included in the string stream. Here, when the size of the string included in the string stream is N, the input buffer101generates a string stream from the input data stream, temporarily stores the same, and outputs a string with the size N for each clock signal.

Each string output by the input buffer101includes a plurality of characters. Therefore, when each character is expressed with C with the assumption that the size if each character is given to be 1, the string with the size N can be expressed as C0C1. . . C(N−1). Here, C0represents the most significant character of the string.

The delay buffer102temporarily stores the string output by the input buffer101, delays it by 1 clock signal, and outputs the delayed string. Accordingly, the string newly output by the input buffer101and the delayed string output by the delay buffer102are simultaneously input to the distributor103.

For example, the string that is second output by the input buffer101is simultaneously input to the distributor103together with the string that is first output by the input buffer, is delayed by the delay buffer102by 1 clock signal, and then is output. The string output by the input buffer101will be referred to as the “a first string,” and the string output by the delay buffer102will be called “a second string” hereinafter.

The distributor103combines the first string output by the input buffer101and the second string output by the delay buffer102by positioning the two strings on a lower part and a higher part, respectively, and thereby generates a new string. In this instance, the generated string is twice the size of the string output by the input buffer101. That is, when the size of the first string is assumed to be N, the size of the string that is generated by combining the first string and the second string by the distributor103becomes 2N. The string that is generated by combining the first string and the second string by the distributor103will be called “the third string.”

When the third string is generated, the distributor103extracts a plurality of strings that are positioned to be separated from the most significant character of the third string by a predetermined offset and respectively have the same size as the first string from the third string, and then outputs the plurality of strings. That is, the distributor103generates and outputs a plurality of strings that are included in the third string, have different start positions, and have the same size as the first string.

The string generated from the third string by the distributor103will be called “the fourth string.”

Also, the start position of the fourth string at the third string will be called an “offset.”

When the size of the third string is assumed to be 2N and each character is expressed with C, the third string can be expressed as C0C1. . . C(2N−1), and C0corresponds to the most significant character of the third string. Also, C0C1. . . C(N−1)from among the third string corresponds to the second string output by the delay buffer102, and CNC(N+1). . . C(2N−1)corresponds to the first string output by the input buffer101.

Therefore, when a predetermined offset for generating the fourth string is given to be k, the fourth string that is positioned at the offset k from among the third string can be expressed as CkC(k+1). . . C(k+N−1). Further, when the number of the fourth strings that are simultaneously generated is given to be N, the fourth strings that can be generated from the third string become C0C1. . . C(N−1), C1C2. . . CN, . . . , C(N−1)CN. . . C(2N−2)depending on k. Accordingly, the distributor103shifts the offset by each character in the third string, and extracts the fourth string. Hence, the fourth string may share at least one character with another fourth string.

The memory104divides at least one string to be detected from the input data stream into at least one sub-string and stores the same. That is, when the size of the string to be detected is L and L is greater than the size of the first string that is N, the memory104divides the corresponding string into sub-strings with the size that is less than N and stores them.

For example, when the string to be detected is “ABCDEFGHMNS,” the string is divided into “ABCD,” “EFGH,” and “MNS,” which are stored in the memory104. The string to be detected from the input data stream will be referred to as the “target string.”

When a plurality of the fourth strings output by distributor103correspond to the at least one sub-string stored in the memory104, the comparator105outputs a detection signal for indicating that the corresponding sub-strings are detected. Here, the detection signal is sorted per sub-string and can be sorted per offset corresponding to the fourth string, and then is output to the concatenation circuit106. Therefore, the concatenation circuit106can check which sub-string that corresponds to an offset is detected based on the detection signal.

The concatenation circuit106determines whether to detect the target string by checking whether the detection signals for the sub-strings that are included in the same target string and correspond to the same offset are sequentially input based on the detection signal output by the comparator105, and when the target string is determined to be detected, the concatenation circuit106outputs a detection signal for indicating the detection. Here, the detection signal is identified by each target string and is output to the encoding circuit107. Therefore, the encoding circuit107can check which target string is detected based on the detection signal.

Upon having determined that the target string is detected based on the detection signal output by the concatenation circuit106, the encoding circuit107outputs a string ID corresponding to the detected target string.

An operation of the string matching device100will now be described with reference toFIG. 2.

It will be assumed that the target strings are “ABCDEFGHMNS,” “EFGHMNOP,” and “GHMNQR,” the size N of the first string output by the input buffer101is 4, and the data stream that is input to the input buffer101is “XYABCDEFGHMNQROP . . . .”

Therefore, the target strings are divided into sub-strings including “ABCD,” “EFGH,” “MNS,” “EFGH,” “MNOP,” “GHMN,” and “QR” to be stored in the memory104.

Referring toFIG. 2, the respective columns of Phase1, Phase2, and Phase3represent output data of the input buffer101, and input data and output data of the distributor103in the corresponding stage.

That is, the input buffer101arranges the input data stream of Phase1by 4 bytes and sequentially outputs the first string. The delay buffer102delays the first string output by the input buffer101by 1 clock signal, and outputs the second string. Therefore, the first string and the second string are input to the distributor103by 8 bytes in a like manner of Phase2, and are used to generate the third string.

For example, when the input buffer101outputs the first string “CDEF,” the delay buffer102outputs “XYAB” output by the input buffer101by 1 clock signal in advance as the second string. Therefore, the two strings are combined by the distributor103to generate the third string “XYABCDEF.”

The distributor103generates fourth strings corresponding to different offsets in a like manner of Phase3by using the third string that is generated by combining the first string and the second string.

For example, the distributor103generates and outputs the fourth strings “XYAB,” “YABC,” “ABCD,” and “BCDE” from the third string “XYABCDEF” with different offsets. Here, “XYAB” is positioned on the offset0, “YABC” on the offset1, “ABCD” on the offset2, and “BCDE” on the offset3.

The fourth strings “XYAB,” “YABC,” “ABCD,” and “BCDE” are simultaneously compared to the sub-strings “ABCD,” “EFGH,” . . . , “QR” stored in the memory104by the comparator105. Each time a sub-string is detected from among the fourth string, the comparator105outputs a detection signal for indicating detection of a sub-string.

For example, when the data stream input to the input buffer101is “XYABCDEFGHMNQROP . . . ,” the comparator105can detect the fourth strings corresponding to the sub-strings “ABCD,” “EFGH,” “GHMN,” and “QR”. Here, in the case of the sub-strings such as “MNS” or “QR” that do not have 4 bytes, the comparator105compares the sub-strings starting from the most significant byte of the fourth string by the length that corresponds to the length of the sub-string to be compared. That is, the comparator105compares the top 3 bytes of the fourth string and the “MNS” in the case of “MNS,” and compares the top 2 bytes of the fourth string and “QR” in the case of “QR.”

Referring toFIG. 2, the fourth strings that are positioned on the offset0from among the fourth strings output by the comparator105consecutively correspond to the sub-strings “GHMN” and “QR.”

Therefore, the comparator105consecutively outputs detection signals for the two sub-strings that are sequentially input to the concatenation circuit106. Also, the concatenation circuit106outputs a detection signal for indicating that the target string “GHMNQR” configured with “GHMN” and “QR” corresponding to the same offset is detected. When the two detection signals correspond to different offsets even if the detection signal for “GHMN” and the detection signal for “QR” are consecutively input, the concatenation circuit106determines that no target string has been detected.

Therefore, the encoding circuit107outputs a string ID that corresponds to “GHMNQR.”

For example, when the string ID's1,2, and3are given to “ABCDEFGHMNS,” “EFGHMNOP,” and “GHMNQR,” respectively, the encoding circuit107outputs3which is the string ID of “GHMNQR.”

FIG. 3shows a configuration diagram of a concatenation circuit according to a first exemplary embodiment of the present invention, showing the case of M stages.

For example, when en1is “1” in the second multiplexer1004-1of the first stage, the signal output by the flipflop1002-1of the first stage is input to the AND gate1001-2of the second stage. On the contrary, when en1is “0,” the signal output by the flipflop1002-1of the first stage is not transmitted to the AND gate1001-2of the second stage. Therefore, the concatenation circuit106is divided into a plurality of sub-concatenation circuits or is connected to be operable by the control signals en1, en2, . . . , enM.

A target string is detected by the connected sub-concatenation circuits. For example, when it is assumed that the target string is “ABCDEFGHMNS” and the size N of the first string output by the input buffer101is 4, “ABCDEFGHMNS” is divided into sub-strings including “ABCD,” “EFGH,” and “MNS.”

Accordingly, detection signals for indicating detection of the sub-strings “ABCD,” “EFGH,” and “MNS” are sequentially input to the sub1, sub2, and sub3of the concatenation circuit106from the comparator105for each clock signal, and str3of the concatenation circuit106finally becomes “1” to show that the target string “ABCDEFGHMNS” is detected. Here, en1and en2are both set to be “1” and en3is set to be “0” so that the sub-concatenation circuits corresponding to the sub-strings “ABCD,” “EFGH,” and “MNS” may be connected with each other and may output the final detection result for “ABCDEFGHMNS.”

FIG. 4shows a flowchart of a string matching method by a string matching device according to a first exemplary embodiment of the present invention.

Referring toFIG. 4, the string matching device100divides at least one target string into at least one sub-string and stores the same in the memory104(S101). Here, the size of the sub-string is selected to be less than the size of the first string output by the input buffer101.

When the data stream is input to the input buffer101, the input buffer101arranges the input data stream by a predetermined size N to generate a string stream, temporarily stores the generated string stream, and outputs the first string of the size N included in the string stream for each clock signal (S102).

Therefore, the distributor103combines the first string that is output by the input buffer101and the second string that is output after the first string that is output by the input buffer101at the previous clock signal is delayed by the delay buffer102to generate a third string (S103), and generates a plurality of fourth strings with different offsets from the third string (S104). That is, the distributor103generates a plurality of fourth strings that have different start positions beginning from the third string and have the same size as the first string.

The comparator105simultaneously compares the fourth strings with the sub-strings stored in the memory104, and when there are some fourth strings that correspond to the sub-strings, the comparator105outputs detection signals for indicating that the corresponding sub-strings are detected (S105).

Also, the concatenation circuit106checks whether the target string is detected (S106) by checking whether the detection signals for the sub-strings that are included in the same target string and correspond to the same offset are sequentially input based on the detection signal that is output by the comparator105. When the detection signals for the corresponding sub-strings are sequentially input, the concatenation circuit106determines that the corresponding target string is detected, and outputs a detection signal for indicating the determination. Accordingly, the encoding circuit107outputs a string ID that corresponds to the detected target string in the concatenation circuit106(S107).

A string matching method and device according to a second exemplary embodiment of the present invention will now be described in detail with reference toFIG. 5toFIG. 8.

FIG. 5shows a configuration diagram of a string matching device according to a second exemplary embodiment of the present invention,FIG. 6shows a detailed configuration diagram of an entry and a concatenation circuit according to a second exemplary embodiment of the present invention, andFIG. 7shows an example of storing a sub-string of a target string per memory of each entry according to a second exemplary embodiment of the present invention.

Referring toFIG. 5, the string matching device200includes an input buffer201, a delay buffer202, a distributor203, a plurality of entries204-1,204-2, . . . ,204-P, a concatenation circuit205, and an encoding circuit206.

The input buffer201, the delay buffer202, and the distributor203of the string matching device200according to the second exemplary embodiment of the present invention perform the same operations as the input buffer101, the delay buffer102, and the distributor103of the string matching device100according to the first exemplary embodiment, so detailed descriptions thereof will not be provided.

Referring toFIG. 6, the entries204-1,204-2, . . . ,204-P include a memory2001and a plurality of comparators2002-1,2002-2, . . . ,2002-N. Here, the number of the comparators2002-1,2002-2, . . . ,2002-N included in the entry204-pcorresponds to the size N of the first string that is output by the input buffer201.

The memory2001stores one of the sub-strings of at least one target string. For example, when the length of the target string is L and the size of the first string output by the input buffer201is N, the target string is divided into sub-strings with the size that is less than N, and the sub-strings are stored in the memory2001of the entry204-p.

For example, when it is assumed that the target string is “EFGHMNOP” and N is 4, “EFGHMNOP” is divided into the sub-string “EFGH” and the sub-string “MNOP,” and the sub-strings are stored in the memory2001of the first entry204-1and the second entry204-2, respectively. That is, “EFGH” is stored in the memory2001of the first entry204-1, and “MNOP” is stored in the memory2001of the second entry204-2.

The comparators2002-1,2002-2, . . . ,2002-N are classified by the offsets in a like manner of the method for classifying the fourth strings, and when the fourth string that corresponds to the same offset from among a plurality of fourth strings that are output by the distributor203is compared to the sub-string that is stored in the memory2001and they are found to correspond with each other, the comparators2002-1,2002-2, . . . ,2002-N output a detection signal for indicating that the corresponding sub-string is detected. Different fourth strings are input to a plurality of comparators2002-1,2002-2, . . . ,2002-N included in a single entry204-p. That is, when the fourth strings output by the distributor203are input to the entry204-p, they are divided for the respective offsets to be input to the respective comparators2002-1,2002-2, . . . ,2002-N.

Therefore, when the distributor203outputs the fourth strings that are provided at N different offsets, the entry204-puses the N comparators2002-1,2002-2, . . . ,2002-N to compare the corresponding sub-strings and the N fourth strings, and when the fourth strings correspond to the sub-strings, the entry204-poutputs a detection signal for indicating that the corresponding sub-string is detected.

When the sub-string stored in the memory2001has a size that is less than that of the first string, the comparators2002-1,2002-2, . . . ,2002-N combine “don't care” bytes with the corresponding sub-string to update the sub-string to be the same size of the first string, and compares the updated sub-string and the fourth string. The “don't care” term signifies that the corresponding byte may have any type of data.

For example, when it is assumed that N is 4 and the target string is “GHMNQR,” the target string is divided into sub-strings “GHMN” and “QR.”

Therefore, “QR” needs 2 more bytes so as to have a 4-byte data form, and the added 2 bytes become “don't care” terms.

Referring toFIG. 5, the concatenation circuit205classifies the detection signals output by the entries204-1,204-2, . . . ,204-P for the respective offsets, and checks whether the sub-strings that are included in the same target string and correspond to the same offset are sequentially input to determine whether to detect the target string.

When the target string is determined to have been detected, the concatenation circuit205outputs a detection signal for indicating the determination. Here, the concatenation circuit205outputs the detection signal by the target strings. Therefore, the encoding circuit206can check which target string is detected based on the detection signal.

Upon having determined that the target string is detected based on the detection signal output by the concatenation circuit106, the encoding circuit206outputs a string ID of the corresponding target string.

An operation of the string matching device200will now be described with reference toFIG. 2andFIG. 7.

First, it will be assumed that the size N of the first string is 4, the number P of the entry204-pis 7, and the target strings are “ABCDEFGHMNS,” “EFGHMNOP,” and “GHMNQR.”

Therefore, as shown inFIG. 7, the sub-strings “ABCD,” “EFGH,” “MNS*,” “EFGH,” “MNOP,” “GHMN,” and “QR**” are stored in the memory2001of the entry204-p. Here, “*” of “MNS*” and “QR**” represent “don't care terms. Therefore, the comparators2002-1,2002-2, . . . ,2002-N of the third entry204-3output detection signals based on the result of comparing 3 characters “MNS” irrespective of the last byte of “MNS*.”

Also, the comparators2002-1,2002-2, . . . ,2002-N of the seventh entry204-7output detection signals based on the result of comparing two characters “QR” of “QR**.”

When it is assumed that “XYABCDEFGHMNQROP . . . ” is input to the input data stream, as shown inFIG. 2, the distributor203outputs the fourth strings “XYAB,” “YABC,” “ABCD,” and “BCDE” in the first stage. Therefore, it is found that the sub-string “ABCD” stored in the memory2001of the first entry204-1corresponds to the fourth string “ABCD” corresponding to the offset2. Further, since the fourth string corresponding to the offset2is input to the third comparator2002-3, the third comparator2002-3of the first entry204-1outputs a detection signal for indicating that the corresponding sub-string is detected to the concatenation circuit205.

Also, in the third stage, the distributor203outputs the fourth strings “GHMN,” “HMNQ,” MNQR,” and “NQRO.”

Therefore, it is found that the sub-string “GHMN” stored in the memory2001of the sixth entry204-6corresponds to the fourth string “GHMN” corresponding to the offset0. Since the fourth string corresponding to the offset0is input to the first comparator2002-1, the first comparator2002-1of the sixth entry204-6outputs a detection signal for indicating that the sub-string is detected to the concatenation circuit205.

Also, in the fourth stage, the distributor203outputs a fourth string such as “QROP.”

Hence, it is found that the sub-string “QR**” stored in the memory2001of the seventh entry204-7corresponds to the fourth string “QROP” corresponding to the offset0. Since the fourth string “QROP” corresponding to the offset0is input to the first comparator2002-1, the first comparator2002-1of the seventh entry204-7outputs a detection signal for indicating that the corresponding sub-string is detected to the concatenation circuit205.

Therefore, since the detection signal for “GHMN” and the detection signal for “QR**” corresponding to the same offset are sequentially input, the concatenation circuit205determines that the target string “GHMNQR” is detected and outputs a detection signal for indicating the determination. When the detection signal for “GHMN” and the detection signal for “QR**” are sequentially input but they correspond to different offsets, the concatenation circuit205determines that the target string is not detected.

FIG. 8shows a flowchart of a string matching method of a string matching device according to a second exemplary embodiment of the present invention.

Referring toFIG. 8, the string matching device200divides at least one target string into at least one sub-string, and stores the sub-strings in the memory2001of the entry204-p(S201).

When a data stream is input to the input buffer201, the input buffer201arranges the input data stream with a predetermined size N to generate a string stream, temporarily stores the generated string stream, and outputs the first string with the size N included in the string stream for each clock signal (S202).

Therefore, the distributor203generates a third string by combining a first string that is output by the input buffer201and a second string that is output by delaying the first string that is output by the input buffer201at the previous clock signal through the delay buffer202(S203), and generates a plurality of fourth strings with different offsets from the third string (S204). That is, the distributor203generates a plurality of fourth strings that have different start positions and have the same size as the first string from the third string.

The entries204-1,204-2, . . . ,204-P simultaneously compare the sub-string stored in the corresponding memory2001and a plurality of fourth strings by using the comparators2002-1,2002-2, . . . ,2002-N that are classified by the offset, and when the fourth string corresponds to the sub-string, the same output detection signals for indicating that a corresponding sub-string is detected (S205).

Also, the concatenation circuit205classifies the detection signals output by the entries204-1,204-2, . . . ,204-P by offsets, and checks a detection state of the target string by checking whether the detection signals for the sub-strings that are included in the same target string for the respective offsets and correspond to the same offset are sequentially input (S206).

When the detection signals for the corresponding sub-strings are sequentially input, the concatenation circuit205determines that the corresponding target string is detected, and outputs a detection signal for indicating the determination. Hence, the encoding circuit206outputs a string ID that corresponds to the target string that is detected by the concatenation circuit205(S207).

A string matching method and device according to a third exemplary embodiment of the present invention will now be described with reference toFIG. 9andFIG. 10.

FIG. 9shows a configuration diagram of a string matching device according to a third exemplary embodiment of the present invention.

Referring toFIG. 9, the string matching device300includes an input buffer301, a delay buffer302, a distributor303, a memory304, a first comparator305, an offset controller306, an offset selector307, a second comparator308, a concatenation circuit309, and an encoding circuit310.

The input buffer301, the delay buffer302, and the distributor303of the string matching device300according to the third exemplary embodiment of the present invention perform the same functions as the input buffer101, the delay buffer102, and the distributor103of the string matching device100according to the first exemplary embodiment, so no detailed description thereof will be provided.

The memory304divides at least one target string into at least one sub-string and stores the same. For example, when the length of the target string is L and the size of the first string output by the input buffer301is N, the target string is divided into sub-strings with the size that is less than N to be stored in the memory304. The most significant sub-string from among the sub-strings will be called a prefix hereinafter.

The first comparator305simultaneously compares a plurality of fourth strings output by the distributor303with at least one prefix stored in the memory304.

When a fourth string corresponds to the prefix, the first comparator305outputs a detection signal for indicating that the corresponding prefix is detected. Here, the detection signal is classified by the offset that corresponds to the fourth string in addition to by the prefix, and is then output. Therefore, the concatenation circuit309can check which prefix is detected based on the detection signal, and the offset controller306can check to which offset it corresponds based on the detection signal.

The offset controller306outputs an offset control signal by using offset information of the fourth string corresponding to a detection signal based on the detection signal output by the first comparator305. In the initial state of the offset control signal, no fourth string is selected.

The offset selector307selects one of the fourth strings output by the distributor303based on the offset control signal output by the offset controller306, and outputs it.

The second comparator308simultaneously compares the fourth string selected by the offset selector307and the sub-strings that are stored in the memory304, and when there is a sub-string that corresponds to the selected fourth string from among the corresponding sub-strings, the second comparator308outputs a detection signal for indicating the correspondence. Here, the detection signal is divided by the respective sub-strings to be output. Hence, the concatenation circuit309can check which sub-string is detected based on the detection signal.

The concatenation circuit309checks whether a prefix that is included in the same target string and corresponds to the same offset and detection signals for remaining sub-strings are sequentially input based on the detection signals output by the first comparator305and the second comparator308.

When the corresponding prefix and the detection signals for the residual sub-strings are sequentially input, the concatenation circuit309determines that the corresponding target string is detected, and outputs a detection signal for indicating the determination. Here, the detection signals are output by the target strings. Therefore, the encoding circuit310can check which target string is detected based on the detection signals.

The encoding circuit310outputs an ID of a target string when the concatenation circuit309outputs a detection signal for indicating that the corresponding target string is detected.

An operation of the string matching device300will now be described with reference toFIG. 2.

First, it will be assumed that the target strings are “ABCDEFGHMNS,” “EFGHMNOP,” and “GHMNQR,” and the size N of the first string output by the input buffer101is 4. Therefore, the target strings are divided into sub-strings “ABCD,” “EFGH,” “MNS,” “EFGH,” “MNOP,” “GHMN,” and “QR” that are stored in the memory304. Here, “ABCD,” “EFGH,” and “GHMN” are classified by the prefix of the target strings.

When it is assumed that “XYABCDEFGHMNQROP . . . ” is input to the input data stream, the distributor303outputs the fourth strings “XYAB,” “YABC,” “ABCD,” and “BCDE” at the first stage as shown inFIG. 2. Therefore, “ABCD” positioned at the offset2from among the fourth strings corresponds to the prefix “ABCD” of the target string “ABCDEFGHMNS.”

Accordingly, the first comparator305outputs a detection signal for indicating that the prefix “ABCD” of the target string “ABCDEFGHMNS” is detected. Further, since the detection signal corresponds to the offset2, the offset controller306outputs an offset control signal for selecting the fourth string corresponding to the offset2in the next stage.

The offset selector307selects the fourth string that corresponds to the offset2from among a plurality of fourth strings that are input based on the offset control signal output by the offset controller306, and outputs the same. Therefore, in the second stage, the offset selector307selects the fourth string “EFGH” corresponding to the offset2from among the fourth strings “CDEF,” “DEFG,” “EFGH,” and “FGHM” output by the distributor303, and outputs it.

Accordingly, the second comparator308compares the fourth string “EFGH” selected by the offset selector307and the sub-strings except the prefix, checks that the selected fourth string “EFGH” corresponds to the sub-string “EFGH,” and outputs a detection signal for indicating that the sub-string “EFGH” is detected.

“EFGH” positioned at the offset2from among the fourth strings “CDEF,” “DEFG,” “EFGH,” and “FGHM” output by the distributor303corresponds to the prefix “EFGH” of the target string “EFGHMNOP.”

Therefore, the first comparator305outputs a detection signal for indicating that the prefix “EFGH” is detected.

However, in this case, the offset controller306does not change the offset control signal since the prefix that corresponds to the offset2is detected in the previous stage when the prefix is detected. That is, in this case, the offset controller306processes in advance that the sub-string “EFGH” is detected.

In the third stage, no sub-string that corresponds to the fourth string “MNQR” corresponding to the offset2output by the offset selector307is detected from among the residual sub-strings except the prefix. On the other hand, in the third stage, “GHMN” that is positioned at the offset0from among a plurality of fourth strings output by the distributor303corresponds to the prefix “GHMN” of the target string “GHMNQR.”

Therefore, the first comparator305outputs a detection signal for indicating that the prefix “GHMN” is detected. Also, the offset controller306outputs an offset control signal for controlling to select the fourth string corresponding to the offset0in the next stage since there is no sub-string that is detected through the second comparator308in the third stage and the fourth string “GHMN” that corresponds to the offset0corresponds to the prefix “GHMN.”

Therefore, in the fourth stage, the offset selector307selects the fourth string “QROP” that corresponds to the offset0from among the fourth strings output by the distributor303and outputs the same, and the second comparator308checks that the two top characters of the fourth string “QROP” corresponds to the sub-string “QR” stored in the memory304and outputs a detection signal for indicating the correspondence. In the case of the sub-string having a size that is less than N in a like manner of “MNS” or “QR,” the second comparator308compares the fourth string and the above-noted sub-string by the length of the sub-string to be compared beginning from the most significant character. That is, in the case of the sub-string “MNS,” the second comparator308compares the top three characters of the fourth string with the sub-string “MNS,” and in the case of the sub-string “QR,” it compares the top two characters of the fourth string with the sub-string “QR.”

Since the detection signal for the prefix “GHMN” corresponding to the same offset and the detection signal for the sub-string “QR” are sequentially input based on the detection signals output by the first comparator305and the second comparator308, the concatenation circuit309determines that the target string “GHMNQR” is detected and outputs a detection signal for indicating the determination.

FIG. 10shows a flowchart of a string matching method by a string matching device according to a third exemplary embodiment of the present invention.

In the string matching method according to the third exemplary embodiment of the present invention, the processes S302to S304are performed in a like manner of the processes S102to S104of the string matching method according to the first exemplary embodiment, and hence no detailed description thereof will be provided.

Referring toFIG. 10, the string matching device300divides at least one target string into at least one sub-string, divides sub-strings into a prefix and other sub-strings except the prefix, and stores them in the memory304(S301). Here, the size of the sub-string is selected to be less than that of the first string output by the input buffer301.

When a plurality of fourth strings are generated by the distributor303, the first comparator305simultaneously compares the fourth strings with the prefixes stored in the memory304(S305), checks whether there are a fourth string and a prefix that correspond with each other (S306), and outputs a detection signal for indicating that the corresponding prefix is detected when a fourth string and a prefix that correspond with each other are found. Also, the offset controller306outputs an offset control signal by using offset information of the fourth string corresponding to a detection signal based on the detection signal output by the first comparator305(S307).

The offset selector307selects one of the fourth strings output by the distributor303based on the offset control signal output by the offset controller306, and outputs it (S308). Accordingly, the second comparator308simultaneously compares the fourth string selected by the offset selector307and the sub-strings that are stored in the memory304(S309), and when there exists a sub-string that corresponds to the selected fourth string, it outputs a detection signal for indicating the existence.

When the sub-string is detected through the first comparator305and the second comparator308, the concatenation circuit309checks whether the detection signals for the prefix that is included in the same target string and corresponds to the same offset and residual sub-strings except the prefix are sequentially input, and when the detection signals for the corresponding sub-string are sequentially input, it determines that the corresponding target string is detected (S310) and outputs a detection signal for indicating the determination.

Accordingly, the encoding circuit310finally outputs a string ID of the detected target string (S311).

A string matching method and device according to a fourth exemplary embodiment of the present invention will now be described in detail with reference toFIG. 11toFIG. 18.

A state transition process used for the fourth exemplary embodiment of the present invention will now be described before the fourth exemplary embodiment of the present invention is described.

In general, the state transition process represents a process in which the current state transits to the next state according to the current state and input data. Therefore, a lookup memory for storing a plurality of data included in the corresponding process and state values relating to the respective data is needed so as to perform the state transition process. Also, a state transition memory for storing the state values for indicating the next states that can be transited is needed.

That is, a system for performing the state transition process compares the input data and state variables for indicating current states with the data that are stored in the lookup memory and state values relating to the data. Further, when there is a state value that corresponds to the state variable according to the comparison result, that is, when the lookup memory has data relating to the current state, the system reads an index corresponding to the pair of the corresponding data and the state value of the corresponding data from the lookup memory.

The system reads a state value for indicating the next state of the current state from the state transition memory based on the index that is read from the lookup memory, and updates the state variable for indicating the current state based on the state value. That is, the system for performing the state transition process changes the state variable for indicating the current state according to the state value for indicating the next state, and is then transited to the next state.

FIG. 11shows a configuration diagram of a string matching device according to a fourth exemplary embodiment of the present invention.FIG. 12shows a configuration diagram of a prefix processor according to a fourth exemplary embodiment of the present invention, andFIG. 13shows a configuration diagram of a sub-string processor according to a fourth exemplary embodiment of the present invention. Also,FIG. 14andFIG. 15show an example of a state transition process according to a fourth exemplary embodiment of the present invention, andFIG. 16shows an example of data that are stored in respective constituent elements according to a fourth exemplary embodiment of the present invention.

Referring toFIG. 11, the string matching device includes an input buffer401, a delay buffer402, a distributor403, a prefix processor404, an offset selector405, a sub-string processor406, a path selector407, and a state transition processor408.

The input buffer401, the delay buffer402, and the distributor403of the string matching device400according to the fourth exemplary embodiment of the present invention perform the same functions of the input buffer101, the delay buffer102, and the distributor103of the string matching device100according to the first exemplary embodiment, so no detailed corresponding description will be provided.

At least one target string is divided into at least one sub-string. For example, when the length of the target string is L and the size of the first string output by the input buffer401is N, the target string is divided into sub-strings having the size less than N. The most significant sub-string from among the sub-strings will be called the “prefix.”

Further, the entries4010-1,4010-2, . . . ,4010-P respectively include a memory4011and a plurality of comparators4012-1,4012-2, . . . ,4012-N. In this instance, the number of comparators4012-1,4012-2, . . . ,4012-N included in the respective entries4010-1,4010-2, . . . ,4010-P is set according to the size N of the first string output by the input buffer401.

The memory4011stores the prefix. Here, different prefixes are stored in the memory4011corresponding to the entries4010-1,4010-2, . . . ,4010-P.

For example, when it is assumed that the size N of the first string is 4 and the target string includes “ABCDEFGHMNS,” “EFGHMNOP,” and “GHMNQR,” the prefix “ABCD” of “ABCDEFGHMNS” is stored in the memory4011of the first entry4010-1. Also, the prefix “EFGH” of “EFGHMNOP” is stored in the memory4011of the second entry4010-2, and the prefix “GHMN” of “GHMNQR” is stored in the memory4011of the third entry4010-3. When there is another target string “ABCDMNOP,” the prefix “ABCD” of “ABCDMNOP” need not use another entry since it is stored in the memory4011of the first entry4010-1.

The respective comparators4012-1,4012-2, . . . ,4012-N are divided according to the offsets in a like manner of the fourth string classifying method, and compare the fourth string of the corresponding offset from among a plurality of the fourth strings output by the distributor403and the prefix that is stored in the memory4011, and outputs a detection signal for indicating that the corresponding prefix is detected when the fourth string corresponds to the prefix.

Here, in the case of comparing the prefix and the fourth string, the comparators4012-1,4012-2, . . . ,4012-N combine the bytes of the “don't care” term and the corresponding prefix, updates them to be the same size of the first string, and compares then when the size of the corresponding prefix is less than the size of the first string.

In addition, different fourth strings are input to a plurality of comparators4012-1,4012-2, . . . ,4012-N included in one of the entries4010-1,4010-2, . . . ,4010-P. That is, a plurality of fourth strings are divided by the offsets and are input to the comparators4012-1,4012-2, . . . ,4012-N. That is, the comparators4012-1,4012-2, . . . ,4012-N compare the fourth strings having different offsets and the prefixes to output detection signals.

Therefore, the encoding circuit4020and the offset controller4030can check the detected prefix and the offset of the fourth string corresponding to the detected prefix by checking the comparators4012-1,4012-2, . . . ,4012-N for outputting the detection signal.

The encoding circuit4020classifies the detection signals output by the comparators4012-1,4012-2, . . . ,4012-N of the entries4010-1,4010-2, . . . ,4010-P by the offsets, and selects one of the detection signals output by the entries4010-1,4010-2, . . . ,4010-P. Here, the encoding circuit4020sets priorities in the order of the detection signal corresponding to the offset0, the detection signal corresponding to the offset1, . . . , and the detection signal corresponding to the offset N−1, and selects the detection signal with the greatest priority so that the detection signal corresponding to the offset0may have the greatest priority, and then it encodes the selected detection signal with the index to output a prefix index corresponding to the detected prefix and simultaneously output the detection signal for indicating that a prefix is detected.

The offset controller4030classifies the detection signals output by the comparators4012-1,4012-2, . . . ,4012-N of the entries4010-1,4010-2, . . . ,4010-P for the respective offsets, selects the same detection signal as that selected by the encoding circuit4020from among the detection signals output by the entries4010-1,4010-2, . . . ,4010-P, and outputs an offset control signal by using offset information of the fourth string corresponding to the selected detection signal.

Referring toFIG. 11, the offset selector405selects one of the fourth strings output by the distributor403and outputs the same based on the offset control signal output by the offset controller4030of the prefix processor404. Here, the offset selector405does not change the selected offset based on the state variable for indicating the current state when a sub-string for the target string from which a prefix is detected is detected when the offset control signal is input.

Referring toFIG. 13, the sub-string processor406is realized with a ternary content addressable memory (TCAM), and includes a plurality of entries4040-1,4040-2, . . . ,4040-M and an encoding circuit4050.

The memory4041stores the sub-string and a state value that can correspond to the sub-string. Here, the entries4040-1,4040-2, . . . ,4040-M store the pairs of different {sub-string, state value} in the corresponding memory4041.

The comparator4042compares the fourth string selected and output by the offset selector405and sub-string stored in the memory4041, and simultaneously compares the state value corresponding to the sub-string and the state variable for indicating the current state of the state transition process. When the fourth string corresponds to the sub-string and the state value corresponding to the sub-string corresponds to the state variable for indicating the current state, the comparator4042outputs a detection signal for indicating that the sub-string corresponding to the current state is detected. Here, the detection signal is divided by the sub-string and the state value corresponding to the sub-string and is then output. Therefore, the encoding circuit4050can check which sub-string is detected and what the state value corresponding to the sub-string based on the detection signal is. Also, when the size of the sub-string to be compared is less than the first string, the comparator4042combines the bytes that are “don't care” terms of the corresponding sub-string, updates them to be the same size of the first string, and compares them.

The encoding circuit4050encodes the detection signal with the index to output a sub-string index corresponding to the current state and the detected sub-string, and simultaneously outputs a detection signal for indicating that a sub-string is detected based on the detection signal output by the entries4040-1,4040-2, . . . ,4040-M. Here, the numbers of the entries4040-1,4040-2, . . . ,4040-M corresponding to the pair of {sub-string, state value} are used for the sub-string index.

Referring toFIG. 11, the path selector407selects one of the prefix index output by the prefix processor404and the sub-string index output by the sub-string processor406based on the state variable for indicating the current state of the state transition process and the detection signals output by the prefix processor404and the sub-string processor406, and then outputs the same.

Assuming that the number of the entries4010-1,4010-2, . . . ,4010-P included in the prefix processor404is P, the path selector407outputs the prefix index when selecting and outputting the corresponding prefix index output by the prefix processor404. However, when selecting and outputting the sub-string index output by the sub-string processor406, the path selector407adds P to the sub-string index and then outputs the added result.

For example, when the current state is 1, the sub-string “EFGH” is detected by the sub-string processor406, and 1 is output for the sub-string index, the path selector407outputs (P+1) for the index. Also, when the current state is 2, the sub-string “MNQR” is detected by the sub-string processor406, and 2 is output for the sub-string index, the path selector407outputs (P+2) for the index. In addition, P can be expressed with the number of the prefixes extracted from at least one target string.

The state transition processor408stores the state value for indicating the next state of the state transition process for each index output by the path selector407. The state value for indicating the next state will be called the “next state value,” and the string ID of the corresponding target string for a specific index is stored together with the next state value. Here, the index for storing the string ID corresponds to the least significant sub-string from among the sub-strings of the target string.

The state transition processor408reads the next state value corresponding to the index output by the path selector407from among the stored per-index next state value, updates the state variable for indicating the current state with the next state value, and outputs the updated state variable to the offset selector405, the sub-string processor406, and the path selector407

In this instance, when there is a string ID corresponding to the index input by the path selector407, the state transition processor408outputs a detection signal for indicating that the target string is detected, and outputs the corresponding string ID.

An operation of the string matching device400will now be described with reference toFIG. 2andFIG. 14.

It will be assumed that the target string is “ABCDEFGHMNQR,” the size N of the first string is 4, and the input data stream is “XYABCDEFGHMNQROP . . . .”

Hence, the sub-strings “ABCD,” “EFGH,” and “MNQR” must be sequentially detected so as to detect “ABCDEFGHMNQR.”

Here, “ABCD” corresponds to the prefix.

Therefore, the prefix “ABCD” is stored in the first entry4010-1of the prefix processor404, and the sub-strings “EFGH” and “MNQR” are stored in the sub-string processor406together with the corresponding state values.

Also, the strings output by the input buffer401, the delay buffer402, and the distributor403are shown inFIG. 2.

Further, referring toFIG. 14, the state variable is 0 in the initial state of the state transition process. When the prefix “ABCD” is detected in the state0, the next state becomes1. In addition, when the sub-string “EFGH” is detected in the state1, the next state becomes2, and when the sub-string “MNQR” is detected in the state2, the next state becomes3, and the state3indicates that the target string “ABCDEFGHMNQR” is detected.

This process will be described in further detail.

In the first stage, the fourth string “ABCD” corresponding to the offset2from among the fourth strings output by the distributor403corresponds to the prefix “ABCD” stored in the first entry4010-1of the prefix processor404. Therefore, the third comparator4012-3of the first entry4010-1outputs a detection signal for indicating that the prefix “ABCD” is detected.

Hence, the encoding circuit4020outputs the number, that is, 1, of the first entry4010-1for outputting the detection signal as a prefix index. Also, the offset controller4030outputs an offset control signal for controlling the offset selector405to select the fourth string corresponding to the offset2since the fourth string corresponding to the prefix “ABCD” is provided at the offset2.

Also, since the state variable for indicating the current state is 0 in the first stage and no sub-string is detected by the sub-string processor406, the path selector407selects and outputs the prefix index1output by the encoding circuit4020of the prefix processor404. Upon having selected the prefix index output by the prefix processor404, the path selector407outputs the prefix index to the state transition processor408.

The state transition processor408receives the index1from the path selector407, and outputs the next state value1corresponding to the index1as the state variable.

In the second stage, the offset selector405selects the fourth string “EFGH” corresponding to the offset2from among the fourth strings output by the distributor403and outputs the same based on the offset control signal output by the offset controller4030of the prefix processor404.

Since the state variable output by the state transition processor408in the previous stage is 1, the current state becomes1. Therefore, the sub-string processor406recognizes the current state based on the input state variable, checks the sub-string “EFHG” that must be detected in the current state1, compares it with the fourth string selected and output by the offset selector405to check that the two strings correspond with each other, and outputs the entry number1corresponding to the state value1of the sub-string “EFHG” as a sub-string index.

Hence, since the current state is 1 and no detection signal is output by the prefix processor404, the path selector407selects and outputs the sub-string index output by the sub-string processor406. In the case of selecting and outputting the sub-string index output by the sub-string processor406, the path selector407adds the number P of the entries included in the prefix processor404to the sub-string index and outputs the added result to the state transition processor408. Therefore, since the current state is 1 and the sub-string “EFGH” is detected by the sub-string processor406, the path selector407outputs the index (P+1) that is generated by adding P to the sub-string index1.

On receiving the index (P+1), the state transition processor408updates the state variable with the next state value2corresponding to the index.

In the third stage, the offset selector405selects the fourth string “MNQR” corresponding to the offset2from among the fourth strings output by the distributor403, and outputs the same. Since the state variable output by the state transition processor408in the previous stage is 2, the current state becomes2. Therefore, the sub-string processor406checks the sub-string “MNQR” that must be detected in the current state2, compares the same with the fourth string “MNQR” output by the offset selector405to check that the two strings correspond with each other, and outputs the entry number corresponding to the state value2of the corresponding sub-string “MNQR” as a sub-string index.

Since the current state is 2 and no detection signal is output by the prefix processor404, the path selector407outputs the index (P+2) that is generated by adding P to the sub-string index output by the sub-string processor406to the state transition processor408.

Therefore, the state transition processor408checks whether there is a string ID corresponding to the input index (P+2), recognizes that the target string “ABCDEFGHMNQR” is detected, and outputs the corresponding string ID.

An operation of the string matching device400will now be described with reference toFIG. 2,FIG. 15, andFIG. 16.

It will be assumed that the target string includes “ABCDEFGHMNQR,” “EFGHMNOP,” and “GHMNQR,” the size N of the first string is 4, and the input data stream is “XYABCDEFGHMNQROP . . . ”. Accordingly, the sub-strings “ABCD,” “EFGH,” and “MNQR” must be sequentially detected in order to detect “ABCDEFGHMNQR,” “EFGH” and “MNOP” must be sequentially detected in order to detect “EFGHMNOP,” and “GHMN” and “QR” must be sequentially detected in order to detect “GHMNQR.”

As shown inFIG. 16, the prefixes “ABCD,” “EFGH,” and “GHMN” are respectively stored in the first entry4010-1, the second entry4010-2, and the third entry4010-3of the prefix processor404. Also, the sub-strings “EFGH,” “MNS**,” “MNOP,” and “QR**” are respectively stored in the first entry4040-1, the second entry4040-2, the third entry4040-3, and the fourth entry4040-4of the sub-string processor406. Further, the sub-strings “MNOP” and “MNQR” that can be additionally generated are stored in the fifth entry4040-5, the sixth entry4040-6, and the seventh entry4040-7of the sub-string processor406. Also, the state values corresponding to the respective sub-strings are stored together with them. Here, * denotes the “don't care” term. The “don't care” term represents that the corresponding byte may have any data.

Also, the strings output by the input buffer401, the delay buffer402, and the distributor403are as shown inFIG. 2.

Further, referring toFIG. 15, the state variable corresponding to the initial state of the state transition process is 0. When the prefix “ABCD” is detected in the state0, the next state becomes1, when the sub-string “EFGH” is detected in the state1, the next state becomes2, when the sub-string “MNS” is detected in the state2, the next state becomes3, and when the state becomes the state3, the target string “ABCDEFGHMNS” is recognized to be detected.

Also, when the prefix “GHMN” is detected in the state0, the next state becomes6, when the sub-string “QR” is detected in the state6, the next state becomes7, when the state becomes the state7, the target string “GHMNQR” is recognized to be detected, and when the sub-string “MNQR” is detected in the state2, the next state becomes the state7. This is because “GHMNQR” is resultantly detected when “MNQR” is detected in the state2since the state2indicates that “ABCDEFGH” is detected and “ABCDEFGH” includes “GH.”

Therefore, as shown inFIG. 16, it is needed to set the state transition process by adding an additional state transition to the state transition process, thereby considering the cases that may happen.

This process will now be described in further detail.

In the first stage, the fourth string “ABCD” corresponding to the offset2from among the fourth strings output by the distributor403corresponds to the prefix “ABCD” stored in the first entry4010-1of the prefix processor404. Therefore, the third comparator4012-3of the first entry4010-1outputs a detection signal for indicating that the prefix “ABCD” is detected.

Hence, the encoding circuit4020of the prefix processor404outputs the index1corresponding to the first entry4010-1to the prefix index.

Also, since the fourth string corresponding to the prefix “ABCD” is positioned at the offset2, the offset controller4030outputs an offset control signal for the offset selector405to select the fourth string corresponding to the offset2.

Further, since the state variable for indicating the current state is 0 and no sub-string is detected by the sub-string processor406in the first stage, the path selector407selects and outputs the prefix index1output by the encoding circuit4020of the prefix processor404. In the case of selecting the prefix index output by the prefix processor404, the path selector407outputs the same to the state transition processor408.

The state transition processor408receives the index1from the path selector407, and outputs the state value1corresponding to the index1from among the next state values set for respective indexes as a state variable. As shown inFIG. 16, the state transition processor408stores the next state values corresponding for each index output by the path selector407in consideration of the state transition process. In this instance, the state transition processor408stores the next state values for the respective indexes by dividing the prefix indexes and the indexes corresponding to the sub-string indexes. The state transition processor408stores string ID's of target strings corresponding to specific indexes from among the indexes together with the next state values. Here, the specific index represents the index that is output when the sub-strings for the target strings are detected.

In the second stage, the offset selector405selects the fourth string “EFGH” corresponding to the offset2from among the fourth strings output by the distributor403based on the offset control signal output by the offset controller4030of the prefix processor404, and outputs the same.

In the previous stage, since the state variable output by the state transition processor408is 1, the current state becomes1. Therefore, the sub-string processor406recognizes the current state based on the input state variable, checks the sub-string “EFHG” to be detected in the current state1, compares it with the fourth string selected by the offset selector405to check that the two strings correspond with each other, and outputs the state value corresponding to the sub-string, that is, the entry number1corresponding to the state value1of the sub-string “EFGH”, as a sub-string index.

“EFGH” positioned at the offset2from among the fourth strings output by the distributor403corresponds to the prefix “EFGH” of the target string “EFGHMNOP.”

Therefore, the prefix processor404outputs the prefix index2for indicating that the prefix “EFGH” corresponding to the offset2is detected. In addition, since the fourth string corresponding to the prefix “EFGH” is positioned at the offset2, the offset controller4030outputs an offset control signal for the offset selector405to select the fourth string corresponding to the offset2.

The path selector407selects the sub-string index output by the sub-string processor406since the state variable for indicating the current state is 1 when the prefix processor404outputs the prefix index, that is, since the state transition for detecting the target string is progressed. In the case of selecting and outputting the sub-string index output by the sub-string processor406, the path selector407adds P to the selected sub-string index and outputs the added result to the state transition processor408. Therefore, since the current state is 1 and the sub-string “EFGH” is detected by the sub-string processor406, the path selector407outputs the index (P+1) that is the summation of the sub-string index1and P.

The state transition processor408receives the index (P+1) and updates the state variable with the next state value2corresponding to the index.

In the third stage, since the state variable of the previous stage is 1, that is, since state transition for detecting the target string is in progress, the offset selector405does not change the offset to be selected but selects the fourth string “MNQR” corresponding to the offset2from among the fourth strings output by the distributor403, and outputs the same. Since the state variable output by the state transition processor408in the previous stage is 2, the current state becomes2. Therefore, the sub-string processor406recognizes the current state based on the input state variable, checks the sub-string “MNQR” to be detected in the current state2, compares it with the fourth string selected by the offset selector405to check whether the two strings correspond with each other, and outputs the entry number6corresponding to the state value corresponding to the sub-string that is the state value2of the sub-string “MNQR” as a sub-string index. Here, the sub-string “MNQR” is stored in the entry6and the index7, and “MNQR” corresponding to the state value2is stored in the entry6, and hence the sub-string processor406outputs the sub-string index6.

“GHMN” that is positioned at the offset0from among the fourth strings output by the distributor403corresponds to the prefix “GHMN” of the target string “GHMNQR.”

Therefore, the prefix processor404outputs a prefix index for indicating that the prefix “GHMN” corresponding to the offset0is detected. Also, the offset controller4030outputs an offset control signal for the offset selector405to select the fourth string corresponding to the offset0since the fourth string corresponding to the prefix “GHMN” is positioned at the offset0.

The path selector407adds P to the sub-string index output by the sub-string processor406and outputs the added result to the state transition processor408since the state variable for indicating the current state is 2 when the prefix index is output by the prefix processor404, that is, since state transition for detecting the target string is progressed. Therefore, since the current state is 2 and the sub-string “MNQR” is detected by the sub-string processor406, the path selector407outputs the index (P+6) which is a summation of the sub-string index6and P.

The state transition processor408receives the index (P+6), perceives the target string “GHMNQR” is detected by checking whether there is a string ID of the target string corresponding to the index, and outputs the string ID of the corresponding target string.

FIG. 17andFIG. 18show a flowchart of a string matching method by a string matching device according to a fourth exemplary embodiment of the present invention.

Since the processes S403to S405in the string matching method according to the fourth exemplary embodiment of the present invention are performed in a like manner of the processes S102to S104in the string matching method according to the first exemplary embodiment, no corresponding detailed description will be provided.

Referring toFIG. 17andFIG. 18, the string matching device400divides at least one target string into at least one sub-string, stores the sub-strings corresponding to the prefix in the prefix processor404, and stores other sub-strings in the sub-string processor406(S401). Here, the size of the sub-string is selected to be less than the size of the first string output by the input buffer401.

The string matching device400stores the state value corresponding to the sub-string of at least one target string in the sub-string processor406, and stores the next state value corresponding to the index output by the path selector407in the state transition processor408(S402). Here, when the index corresponds to target string detection, the state transition processor408stores the corresponding string ID. In this instance, the next state value for each index is set based on the state transition process corresponding to the string matching method.

When a plurality of fourth strings are generated through the distributor403, the respective entries4010-1,4010-2, . . . ,4010-P of the prefix processor404simultaneously compare the prefix stored in the corresponding memory4011and a plurality of fourth strings by using the comparators4012-1,4012-2, . . . ,4012-N divided by the offset (S406) to thus check whether a fourth string and a prefix that correspond with each other (S407) exist, and output detection signals for indicating that a corresponding prefix is detected when there are the fourth string and the prefix corresponding with each other. Also, the encoding circuit4020of the prefix processor404selects one of the detection signals output by the entries4010-1,4010-2, . . .4010-P, encodes the selected detection signal with the index, and outputs a prefix index corresponding to the detected prefix. Further, the offset controller4030of the prefix processor404outputs an offset control signal by using offset information corresponding to the detection signal selected by the encoding circuit4020(S408).

Accordingly, the offset selector405selects one of the fourth strings output by the distributor403and outputs the same based on the offset control signal output by the offset controller4030of the prefix processor404(S409).

Also, the sub-string processor406simultaneously compares the sub-strings stored in the entries4040-1,4040-2, . . . ,4040-M and the fourth string selected and output by the offset selector405, and simultaneously compares the state values corresponding to the sub-strings with the state variable for indicating the current state of the state transition process (S410). When a fourth string and a sub-string that correspond with each other exist and the state value corresponding to the sub-string and the state variable for indicating the current state correspond with each other, the sub-string processor406determines that the sub-string corresponding to the current state is detected (S411), and outputs a sub-string index for indicating that the sub-string corresponding to the current state is detected (S412).

When the prefix processor404or the sub-string processor406outputs the prefix index or the sub-string index, the path selector407checks the index to be output in the current state based on the state variable for indicating the current state, and selects and outputs one of the prefix index and the sub-string index as an index (S413). Here, the prefix processor404outputs the number of the entries4010-1,4010-2, . . . ,4010-P from which the prefix is detected as prefix indexes. Also, the sub-string processor406outputs the number of the entries4040-1,4040-2, . . . ,4040-P from which the sub-string is detected as a sub-string index.

When the index selected by the path selector407is a sub-string index (S414), the path selector407adds the number P of the entries included in the prefix processor404to the sub-string index, and outputs it as an index (S415). On the contrary, when the index selected by the path selector407is a prefix index (S414), the path selector407outputs the prefix index as an index (S416).

The state transition processor408checks whether the index output by the path selector407has a corresponding string ID (S417), and when there exists a corresponding string ID, it recognizes that the target string is detected, and outputs the corresponding string ID (S418). On the contrary, when there is no corresponding string ID, the state transition processor408updates the state variable for indicating the current state of the state transition process with the next state value corresponding to the index (S419), and moves to the next stage to repeat the string matching process.

A string matching method and device according to a fifth exemplary embodiment of the present invention will now be described in detail with reference toFIG. 19toFIG. 22.

FIG. 19shows a configuration diagram of a string matching device according to a fifth exemplary embodiment of the present invention, andFIG. 20shows an example of data that are stored in respective constituent elements according to a fifth exemplary embodiment of the present invention.

Referring toFIG. 19, the string matching device includes an input buffer501, a delay buffer502, a distributor503, a prefix processor504, an offset selector505, a sub-string processor506, a first state transition processor507, a second state transition processor508, and a path selector509.

The input buffer501, the delay buffer502, and the distributor503of the string matching device500according to the fifth exemplary embodiment of the present invention performs the same functions as the input buffer101, the delay buffer102, and the distributor103of the string matching device100according to the first exemplary embodiment, so detailed descriptions thereof will be omitted.

Also, the prefix processor504, the offset selector505, and the sub-string processor506perform the same functions as the prefix processor404, the offset selector405, and the sub-string processor406of the string matching device400according to the fourth exemplary embodiment, so no detailed description thereof will be provided.

The first state transition processor507stores the next state value for each prefix index output by the prefix processor504, and stores the same together with the string ID for a specific prefix index. Here, when the target string is configured with the prefix corresponding to the prefix index, the string ID corresponding to the prefix index is stored in the first state transition processor507.

Also, the first state transition processor507outputs the next state value corresponding to the prefix index output by the prefix processor504, and when a string ID corresponding to the prefix index output by the prefix processor504exists, it outputs a detection signal for indicating that the target string is detected, and outputs a corresponding string ID.

The second state transition processor508stores the next state values for respective sub-string indexes output by the sub-string processor506, and stores corresponding string ID's for specific sub-string indexes. Here, when the sub-string corresponding to the sub-string index is the least significant sub-string of the target string, the string ID corresponding to the sub-string index is stored in the second state transition processor508.

Also, the second state transition processor508outputs the next state value corresponding to the sub-string index output by the sub-string processor506, and when a string ID that corresponds to the sub-string index exists, it outputs a detection signal for indicating that the target string is detected, and outputs the string ID corresponding to the sub-string index.

The path selector509selects one of the next state values output by the first state transition processor507and the second state transition processor508based on the state variable for indicating the current state of the state transition process, updates the state variable for indicating the current state of the state transition process with the selected next state value, selects one of the string ID's output by the first state transition processor507and the second state transition processor508, and outputs the selected string ID. The state variable updated by the path selector509is output to the offset selector505and the sub-string processor506.

An operation of the string matching device500will now be described with reference toFIG. 2,FIG. 15, andFIG. 20.

It is assumed that the target string is “ABCDEFGHMNQR,” “EFGHMNOP,” and “GHMNQR,” the size N of the first string is 4, and the data stream input to the input buffer501is “XYABCDEFGHMNQROP . . . ”

Hence, the sub-strings “ABCD,” “EFGH,” and “MNQR” must be sequentially detected in order to detect “ABCDEFGHMNQR,” “EFGH” and “MNOP” must be sequentially detected in order to detect “EFGHMNOP,” and “GHMN” and “QR” must be sequentially detected in order to detect “GHMNQR.”

Referring toFIG. 20, the first state transition processor507stores the next state values for respective prefix indexes output by the prefix processor504, and stores a predetermined string ID for a specific prefix index.

Further, the second state transition processor508stores the next state values for respective sub-string indexes output by the sub-string processor506, and stores a predetermined string ID for a specific index.

The strings output by the input buffer501, the delay buffer502, and the distributor503are shown inFIG. 2.

Referring toFIG. 15, the state variable corresponding to the initial state of the state transition process is 0. When the prefix “ABCD” is detected in the state0, the next state becomes1, and when the sub-string “EFGH” is detected in the state1, the next state becomes2. When the sub-string “MNS” is detected in the state2, the next state becomes3, and when the state becomes the state3, the target string “ABCDEFGHMNS” is recognized as detected.

When the prefix “GHMN” is detected in the state0, the next state becomes6, and when the sub-string “QR” is detected in the state6, the next state becomes7, and when the state becomes state7, the target string “GHMNQR” is recognized as detected. When the sub-string “MNQR” is detected in the state2, the next state becomes the state7. This is because the state2indicates the state in which “ABCDEFGH” is detected and “ABCDEFGH” includes “GH,” and “GHMNQR” is resultantly detected when “MNQR” is detected in the state2. Therefore, as shown inFIG. 20, it is needed to set the state transition process by adding an additional state transition to the state transition process, thereby considering the cases that may happen.

This process will now be described in further detail.

In the first stage, the fourth string “ABCD” corresponding to the offset2from among the fourth strings output by the distributor503corresponds to the prefix “ABCD” stored in the first entry of the prefix processor504. The first entry outputs a detection signal for indicating that the prefix “ABCD” is detected.

The prefix processor504outputs the index corresponding to the first entry, that is, 1 as a prefix index.

Also, since the fourth string corresponding to the prefix “ABCD” is positioned at the offset2, the prefix processor504outputs an offset control signal for the offset selector505to select the fourth string corresponding to the offset2.

Since the prefix index output by the prefix processor504is 1, the first state transition processor507outputs the next state value1corresponding to the prefix index1. Since the state variable for indicating the current state of the state transition process is 0 and no sub-string is detected by the sub-string processor506, the path selector509updates the state variable with the next state value1output by the first state transition processor507.

In the second stage, the offset selector505selects the fourth string “EFGH” corresponding to the offset2from among the fourth strings output by the distributor503based on the offset control signal output by the prefix processor504, and outputs the same.

The current state becomes1since the state variable output by the path selector509in the previous stage is 1. The sub-string processor506recognizes the current state based on the state variable input by the path selector509, checks the sub-string “EFHG” to be detected in the current state1, compares it with the fourth string selected by the offset selector505to check that the two strings correspond with each other, and outputs the sub-string index1corresponding to the state value that corresponds to the sub-string, that is, the state value1of the sub-string “EFGH.”

Upon receiving the sub-string index1from the sub-string processor506, the second state transition processor508outputs the corresponding next state value2.

“EFGH” that is positioned at the offset2from among the fourth strings output by the distributor503corresponds to the prefix “EFGH” of the target string “EFGHMNOP.”

The prefix processor504outputs the prefix index2for indicating that the prefix “EFGH” corresponding to the offset2is detected. Also, since the fourth string corresponding to the prefix “EFGH” is positioned at the offset2, the prefix processor504outputs an offset control signal for the offset selector505to select the fourth string corresponding to the offset2.

The first state transition processor507outputs the next state value4corresponding to the prefix index2since the prefix index output by the prefix processor504is 2.

Also, since the state variable for indicating the current state is1when the next state value is output by the first state transition processor507, that is, since state transition for detecting the target string is in progress, the path selector509updates the state variable with the next state value2output by the second state transition processor508.

In the third stage, since the state variable of the previous stage is 1, that is, since state transition for detecting the target string is in progress, the offset selector505does not change the offset to be selected, and selects the fourth string “MNQR” corresponding to the offset2from among the fourth strings output by the distributor503and then outputs the same. Since the state variable updated and output by the path selector509in the previous stage is 2, the current state becomes2.

The sub-string processor506recognizes the current state based on the input state variable, checks the sub-string “MNQR” to be detected by the current state2, compares it with the fourth string selected by the offset selector505to check that the two strings correspond with each other, and outputs the sub-string index6corresponding to the state value that corresponds to the sub-string, that is, the state value2of the sub-string “MNQR.”

Here, since “MNQR” corresponding to the state value2is stored in the entry6while the sub-string “MNQR” is respectively stored in the entry6and the entry7, the sub-string processor506outputs the sub-string index6.

Upon receiving the sub-string index6from the sub-string processor506, the second state transition processor508checks that there is a corresponding string ID, recognizes that the target string “GHMNQR” is detected, outputs the string ID3of the corresponding target string, and also outputs a detection signal for indicating that the target string is detected.

The path selector509recognizes that the target string is detected by the second state transition processor508based on the detection signal output by the second state transition processor508, and finally outputs the string ID that is 3 that is output by the second state transition processor508.

FIG. 21andFIG. 22show a flowchart of a string matching method by a string matching device according to a fifth exemplary embodiment of the present invention.

In the string matching method according to the fifth exemplary embodiment of the present invention, the processes S503to S505are performed in a like manner of the processes S102to S104of the string matching method according to the first exemplary embodiment, so no detailed description thereof will be provided.

Referring toFIG. 21andFIG. 22, the string matching device500divides at least one target string into at least one sub-string, stores the sub-strings corresponding to the prefixes in the prefix processor504, and stores other sub-strings in the sub-string processor506(S501). Here, the sizes of the sub-strings are selected to be less than the size of the first string output by the input buffer501.

The string matching device500stores the state values corresponding to the respective sub-strings of at least one target string in the sub-string processor50, and stores the next state values corresponding to the respective prefix indexes output by the prefix processor504in the first state transition processor507. Here, when each prefix index corresponds to the target string detection, the first state transition processor507stores them together with the corresponding string ID's, and also stores the next state values corresponding to respective sub-string indexes output by the sub-string processor506in the second state transition processor508(S502). In this instance, when the sub-string index corresponds to the target string detection, the second state transition processor508stores them together with the corresponding string ID's. Also, the next state value for respective indexes and the corresponding string ID's are set based on the state transition process corresponding to the string matching method.

When a plurality of fourth strings are generated by the distributor503, the respective entries (not shown) of the prefix processor504simultaneously compare the prefix stored in the corresponding memory (not shown) and a plurality of fourth strings by using comparators (not shown) that are classified by the offset (S506), and when there are a fourth string and a prefix that correspond with each other (S507), the same output detection signals for indicating that the corresponding prefix is detected is output.

An encoding circuit (not shown) of the prefix processor504selects one of the detection signals output by the entries (not shown), and outputs an index corresponding to the selected detection signal as a prefix index. An offset controller (not shown) of the prefix processor504outputs an offset control signal by using offset information corresponding to the detection signal selected by the encoding circuit (not shown) (S508).

Hence, the offset selector505selects and outputs one of the fourth strings output by the distributor503based on the offset control signal output by the offset controller (not shown) of the prefix processor504(S509). The sub-string processor506simultaneously compares the sub-strings stored in the entries (not shown) and the fourth string selected by the offset selector505, also simultaneously compares the state values corresponding to the sub-strings and the state variable for indicating the current state of the state transition process (S510), and when the fourth string corresponds to the sub-string and the state value corresponding to the sub-string corresponds to the state variable for indicating the current state, it determines that the sub-string corresponding to the current state is detected and outputs the corresponding sub-string index (S511) and (S512).

The first state transition processor507checks whether there is a string ID corresponding to the prefix index output by the prefix processor504(S513), and when a corresponding string ID exists, it recognizes that the target string is detected and outputs the corresponding string ID (S514), and if not, it outputs the next state value corresponding to the prefix index (S515).

The second state transition processor508checks whether there is a string ID corresponding to the sub-string index output by the sub-string processor506(S513), and when a corresponding string ID exists, it recognizes that the target string is detected and outputs the corresponding string ID (S514), and if not, it outputs the next state value corresponding to the sub-string index (S515).

Accordingly, the path selector509selects one of the string ID's output by the first state transition processor507and the second state transition processor508and outputs the selected string ID based on the state variable for indicating the current state of the state transition process, selects one of the next state values output by the first state transition processor507and the second state transition processor508, updates the state variable for indicating the current state of the state transition process with the selected next state value (S516), and repeats the string matching process in the next stage.

A string matching method and device according to a sixth exemplary embodiment of the present invention will now be described in detail with reference toFIG. 23toFIG. 27.

FIG. 23shows a configuration diagram of a string matching device according to a sixth exemplary embodiment of the present invention,FIG. 24shows an example of a state transition process according to a sixth exemplary embodiment of the present invention, andFIG. 25shows an example of data that are stored in respective constituent elements according to a sixth exemplary embodiment of the present invention.

Referring toFIG. 23, the string matching device includes an input buffer601, a delay buffer602, a distributor603, a prefix processor604, an offset selector605, a sub-string processor606, a string ID processor607, a state transition processor608, a state selector610, and a string ID selector609.

The input buffer601, the delay buffer602, and the distributor603of the string matching device600according to the sixth exemplary embodiment of the present invention perform the same functions as the input buffer101, the delay buffer102, and the distributor103of the string matching device100according to the first exemplary embodiment, so no detailed description thereof will be provided.

The prefix processor604, the offset selector605, and the sub-string processor606perform the same functions as the prefix processor404, the offset selector405, and the sub-string processor406of the string matching device400according to the fourth exemplary embodiment, so no detailed description thereof will be provided.

The string ID processor607stores string ID's for specific indexes from among the prefix indexes output by the prefix processor604, and when there is a string ID corresponding to the prefix index output by the prefix processor604, it outputs a corresponding string ID and simultaneously outputs a detection signal for indicating that the target string is detected. Here, when the target string is configured with the prefix corresponding to the prefix index, the string ID corresponding to the prefix index is stored in the string ID processor607.

The state transition processor608stores the next state value for respective sub-string indexes output by the sub-string processor606, and stores the string ID's for specific sub-string indexes. In this instance, when the sub-string corresponding to the sub-string index is the least significant sub-string of the target string, the string ID corresponding to the sub-string index is stored in the state transition processor608.

Also, the state transition processor608outputs the next state value corresponding to the sub-string index output by the sub-string processor606, and when there is a string ID corresponding to the sub-string index, it outputs a detection signal for indicating that the target string is detected, and outputs a string ID corresponding to the sub-string index.

The state selector610selects one of the prefix index output by the prefix processor604and the next state value output by the state transition processor608based on the state variable for indicating the current state of the state transition process, and updates the state variable for indicating the current state of the state transition process with the selected prefix index or next state value. The state variable output by the state selector610is output to the offset selector605and the sub-string processor606.

The string ID selector609selects one of the string ID's output by the string ID processor607or the state transition processor608based on the detection signal output by the string ID processor607or the state transition processor608and the state variable for indicating the current state of the state transition process, and outputs the selected string ID.

An operation of the string matching device600will now be described with reference toFIG. 2,FIG. 24, andFIG. 25.

First, it will be assumed that the target strings are “ABCDEFGHMNQR,” “EFGHMNOP,” and “GHMNQR,” the size N of the first string is 4, the number of entries included in the prefix processor604is P, and the data stream input to the input buffer601is “XYABCDEFGHMNQROP . . . ”.

In order to detect “ABCDEFGHMNQR,” “ABCD,” “EFGH,” and “MNQR” must be sequentially detected, to detect “EFGHMNOP,” “EFGH” and “MNOP” must be sequentially detected, and to detect “GHMNQR,” “GHMN” and “QR” must be sequentially detected. Here, “ABCD,” “EFGH,” and “GHMN” correspond to the prefixes.

The strings output by the input buffer601, the delay buffer602, and the distributor603are shown inFIG. 2.

Referring toFIGS. 24 and 23, when a prefix is detected in the initial state corresponding to the state0, the number of the corresponding entry from among the entries included in the prefix processor604is selected as a prefix index to be used as the state variable.

For example, when the prefix “ABCD” is stored in the first entry of the prefix processor604as shown inFIG. 24andFIG. 25and the prefix “ABCD” is then detected, the prefix processor604outputs the prefix index as 1 corresponding to the first entry, and the same is used as the state variable. In a like manner, when the prefix “EFGH” is stored in the second entry of the prefix processor604and the prefix “EFGH” is then detected, the prefix processor604outputs the prefix index as 2 corresponding to the second entry, and the same is used as the state variable again.

Referring toFIG. 24, when the prefix index output by the prefix processor604is used as the state variable for indicating the state of the state transition process and a sub-string is detected by the sub-string processor606, the state variable output by the state transition processor608becomes greater than (P+1). For example, when the current state is 1 and the sub-string “EFGH” is detected, the state variable output by the state transition processor608becomes (P+1), and when the current state is (P+1) and the sub-string “MNS” is detected, the state variable output by the state transition processor608becomes (P+2).

The above-noted process will be described in further detail.

In the first stage, the fourth string “ABCD” corresponding to the offset2from among the fourth strings output by the distributor603corresponds to the prefix “ABCD” stored in the first entry of the prefix processor604. The prefix processor604accordingly outputs a detection signal for indicating that the prefix “ABCD” is detected, and outputs the prefix index1of the prefix “ABCD.”

Here, the value output as the index of the prefix uses the number of the entry at which the corresponding prefix is detected.

Since the fourth string corresponding to the prefix “ABCD” is positioned at the offset2, the prefix processor604outputs an offset control signal for the offset selector605to select the fourth string corresponding to the offset2.

Since the prefix index1is output by the prefix processor604, the state variable for indicating the current state of the state transition process is 0, and no sub-string is detected by the sub-string processor606, the state selector610updates the state variable of the state transition process with the prefix index1output by the prefix processor604.

Since the prefix index output by the prefix processor604is 1 and there is no corresponding string ID, the string ID processor607determines that no string is detected, and hence, the output by the string ID processor607is useless.

In the second stage, the offset selector605selects and outputs the fourth string “EFGH” corresponding to the offset2from among the fourth strings output by the distributor603based on the offset control signal output by the prefix processor604.

Since the state variable output by the state selector610in the previous stage is 1, the current state becomes1. The sub-string processor606compares the sub-string “EFHG” to be detected in the current state1and the fourth string selected by the offset selector605to check whether the two strings correspond with each other, and outputs the sub-string index1corresponding to the state value of the sub-string, that is, the state value1of the sub-string “EFGH.”

Upon receiving the sub-string index1from the sub-string processor606, the state transition processor608outputs the corresponding next state value (P+1) as a state variable.

“EFGH” positioned at the offset2from among the fourth strings output by the distributor603corresponds to the prefix “EFGH” of the target string “EFGHMNOP.”

The prefix processor604outputs the prefix index2for indicating that the prefix “EFGH” corresponding to the offset2is detected. Since the fourth string corresponding to the prefix “EFGH” is positioned at the offset2, the prefix processor604outputs an offset control signal for the offset selector605to select the fourth string corresponding to the offset2.

Since the state variable for indicating the current state is1when the prefix index is output by the prefix processor604, that is, since state transition for detecting the target string is in progress, the state selector610selects the next state value (P+1) output by the state transition processor608as the state variable for indicating the current state, and then outputs it.

In the third stage, since the state variable of the previous stage is 1, that is, since state transition for detecting the target string is in progress, the offset selector605does not change the offset to be selected, but selects the fourth string “MNQR” corresponding to the offset2from among the fourth strings output by the distributor603and outputs it. Since the state variable output by the state selector610in the previous stage is (P+1), the current state becomes (P+1). The sub-string processor606recognizes the current state based on the input state variable, checks the sub-string “MNQR” to be detected in the current state (P+1), compares it with the fourth string selected by the offset selector605to check that the two strings correspond with each other, and outputs the sub-string index6corresponding to the state value that corresponds to the sub-string, that is, the state value2of the sub-string “MNQR.”

Here, since the sub-string “MNQR” is stored in the entry6and the entry7and “MNQR” corresponding to the state value (P+1) is stored in the entry6, the sub-string processor606outputs the sub-string index6.

The state transition processor608checks that the sub-string index6input by the sub-string processor606has a corresponding string ID to recognize that the target string “GHMNQR” is detected, and outputs the corresponding string ID that is 3. The state transition processor608outputs a signal for indicating that the target string is detected.

The string ID selector609checks that the target string is detected by checking the detection signal output by the state transition processor608, and selects and outputs the string ID output by the state transition processor608.

FIG. 26andFIG. 27show a flowchart of a string matching method by a string matching device according to a sixth exemplary embodiment of the present invention.

The processes S603to S605in the string matching method according to the sixth exemplary embodiment of the present invention are performed in a like manner of the processes S102to S104in the string matching method according to the first exemplary embodiment, so no detailed description thereof will be provided.

Referring toFIG. 26andFIG. 27, the string matching device600divides at least one target string into at least one sub-string, stores sub-strings corresponding to the prefixes in the prefix processor604, and stores other sub-strings in the sub-string processor606(S601). Here, the sizes of the respective sub-strings are selected to be less than the size of the first string output by the input buffer601.

The string matching device600stores the state value corresponding to the sub-string of at least one target string in the sub-string processor606, stores the string ID corresponding to the prefix index output by the prefix processor604in the string ID processor607, and stores the next state value corresponding to the sub-string index output by the sub-string processor606in the state transition processor608(S602). Here, when the sub-string index corresponds to the target string detection, the state transition processor608stores it together with the corresponding string ID. The next state value for each sub-string index and the corresponding string ID are set based on the state transition process corresponding to the string matching method.

When a plurality of fourth strings are generated by the distributor603, respective entries (not shown) of the prefix processor604simultaneously compare the prefix stored in a memory (not shown) and the fourth strings by using comparators (not shown) that are classified by the offset (S606), and when there are a prefix and a fourth string that correspond with each other, they output a detection signal for indicating that the corresponding prefix is detected (S607and S608).

An encoding circuit (not shown) of the prefix processor604selects one of the detection signals output by the entries (not shown), and outputs the corresponding prefix index based on the selected detection signal. An offset controller (not shown) of the prefix processor604outputs an offset control signal by using offset information corresponding to the detection signal selected by the encoding circuit (not shown) (S608).

Accordingly, the offset selector605selects and outputs one of the fourth strings output by the distributor603based on the offset control signal output by the offset controller (not shown) of the prefix processor604(S609). The sub-string processor606simultaneously compares the sub-string stored in the entries (not shown) and the fourth string selected by the offset selector605, and simultaneously compares the state values corresponding to the sub-strings with the state variable for indicating the current state of the state transition process (S610), and when there are a fourth string and a sub-string that correspond with each other and the state value corresponding to the corresponding sub-string corresponds to the state variable for indicating the current state, it output a sub-string index for indicating that the sub-string corresponding to the current state is detected (S611) and (S612).

The string ID processor607checks whether there is a string ID corresponding to the prefix index output by the prefix processor604(S613), and when the corresponding string ID is found, it recognizes that the target string is detected and outputs the corresponding string ID.

The state transition processor608checks whether there is a string ID corresponding to sub-string index output by the sub-string processor606(S613), and when the corresponding string ID is found, it recognizes that the target string is detected and outputs the corresponding string ID, and when there is no corresponding string ID, it outputs the next state value corresponding to the sub-string index.

The string ID selector609selects one of the string ID's output by the string ID processor607or the state transition processor608based on the detection signal output by the string ID processor607or the state transition processor608and the state variable for indicating the current state of the state transition process, and outputs the selected string ID (S614).

The state selector610selects one of the prefix index output by the prefix processor604and the next state value output by the state transition processor608based on the state variable for indicating the current state of the state transition process, updates the state variable for indicating the current state of the state transition process with the selected prefix index or the next state value (S615), and goes to the next state to repeat the string matching process.

According to the exemplary embodiments of the present invention, it is possible to efficiently perform a string matching process on a high-speed data stream.

The above-described embodiments can be realized through a program for realizing functions corresponding to the configuration of the embodiments or a recording medium for recording the program in addition to through the above-described device and/or method, which is easily realized by a person skilled in the art.