METHOD AND DEVICE FOR CREATING PATTERN MATCHING STATE MACHINE

• US 20100229040A1
• Filed: 05/17/2010
• Published: 09/09/2010
• Est. Priority Date: 02/01/2008
• Status: Active Grant

• Current Assignee: Huawei Technologies Co., Ltd. (Huawei Investment & Holding Co., Ltd.)
• Original Assignee: Huawei Technologies Co., Ltd. (Huawei Investment & Holding Co., Ltd.)
• Inventors: WEI, Qikun, CHEN, Guohai, CHEN, Jian
• Granted Patent: US 8,583,961 B2
• Time in Patent Office: Days
• US Class Current: 714/27
• CPC Class Codes: G06F 16/3331 Query processing

Abstract

A method and a device for creating a pattern matching state machine are provided. The method includes: obtaining a predefined keyword set; generating a Goto function according to the keyword set; constructing a Failure function according to the generated Goto function, and setting that an acceptable input set of the Failure state of each state is not a subset of an acceptable input set of the state, where the acceptable input set of the state indicates that when any symbol within the symbol set is input in the state, the Goto function of the state does not fail; and generating an Output function according to the Goto function and the Failure function.

Claims

1. A method for creating a pattern matching state machine, comprising:

obtaining a predefined keyword set;

generating a Goto function according to the keyword set;

constructing a Failure function according to the generated Goto function, and setting that an acceptable input set of a Failure state of each state is not a subset of an acceptable input set of the state, wherein the acceptable input set of the state indicates that when any symbol within the symbol set is input in the state, the Goto function of the state does not fail; and

generating an Output function according to the Goto function and the Failure function.

2. The method according to claim 1, wherein the constructing the Failure function according to the generated Goto function comprises:

setting the Failure state of all states having a depth of 1 to an initial state, and indicating the initial state with state 0;

executing the following steps on state r having a depth of d-1 in sequence, for determining the Failure state of state s having a depth of d;

obtaining the Failure state of state r having the depth of d-1 as a current state, and executing the following steps;

traversing the input symbol set, determining whether the Goto function fails when the input symbols are input in the current state, and determining whether an acceptable input set of a goto state obtained by the Goto function when the input symbols are input in the current state is a subset of an acceptable input set of state s, wherein the input symbol set comprises all the input symbol capable of being used by the pattern matching state machine;

continuing the determination step by using the Failure state of the current state as the new current state, if the Goto function fails when the input symbols are input in the current state, or the acceptable input set of the goto state obtained through the Goto function when the input symbols are input in the current state is the subset of the acceptable input set of state s;

using a value of the Goto function when the input symbols are input in the current state as the Failure state of state s having the depth of d if the Goto function does not fail when the input symbols are input in the current state, and the acceptable input set of the goto state obtained through the Goto function when the input symbols are input in the current state is not the subset of the acceptable input set of state s; and

ending processing state r, if the Goto function fails when all the input symbols are input in state r.

3. The method according to claim 2, wherein the determining whether the acceptable input set of the goto state obtained through the Goto function when the input symbols are input in the current state is the subset of the acceptable input set of state s comprises:

traversing the input symbol set, determining that the acceptable input set of the goto state obtained through the Goto function when the input symbols are input in the current state is not the subset of the acceptable input set of state s, if a symbol b satisfying conditions g(g (state, a), b)≠

fail and g(s, b)=fail exists, wherein a is an input symbol in state r having the depth of d-1;

otherwise, determining that the acceptable input set of the goto state obtained through the Goto function when the input symbols are input in the current state is the subset of the acceptable input set of state s.

4. The method according to claim 2, further comprising:

using the value of the Goto function when the input symbols are input in the current state as the Failure state of state s having the depth of d if the value of the Goto function is 0 when the input symbols are input in the current state.

5. The method according to claim 3, further comprising:

using the value of the Goto function when the input symbols are input in the current state as the Failure state of state s having the depth of d if the value of the Goto function is 0 when the input symbols are input in the current state.

6. The method according to claim 2, further comprising:

directly setting the Failure state of state s having the depth of d to 0, if the Goto function does not fail when the input symbols are input in the current state, and the acceptable input set of the goto state obtained through the Goto function when the input symbols are input in the current state is the subset of the acceptable input set of state s, and the current state is 0.

7. The method according to claim 3, further comprising:

directly setting the Failure state of state s having the depth of d to 0, if the Goto function does not fail when the input symbols are input in the current state, and the acceptable input set of the Goto state obtained through the Goto function when the input symbols are input in the current state is the subset of the acceptable input set of state s, and the current state is 0.

8. A device of creating a pattern matching state machine, comprising:

an obtaining unit, adapted to obtain a predefined keyword set;

a Goto function generating unit, adapted to generate a Goto function according to the keyword set;

a Failure function generating unit, adapted to construct a Failure function according to the generated Goto function, and set that an acceptable input set of a Failure state of each state is not a subset of an acceptable input set of the state, wherein the acceptable input set of the state indicates that when any symbol within the symbol set is input in the state, the Goto function of the state does not fail; and

an Output function generating unit, adapted to generate an Output function according to the Goto function and the Failure function.

9. The device according to claim 8, wherein the Failure function generating unit comprises:

a setting sub-unit, adapted to set the Failure state of all states having a depth of 1 to an initial state;

a state obtaining sub-unit, adapted to obtain a Failure state of a previous state r having a depth of d-1 as a current state in sequence;

a Failure state generating sub-unit, adapted to traverse the input symbol set, determine whether the Goto function fails when the input symbols are input in the current state, and determine whether an acceptable input set of a goto state obtained through the Goto function when the input symbols are input in the current state is a subset of an acceptable input set of state s;

continue determination by using the Failure state of the current state as the new current state, if the Goto function fails when the input symbols are input in the current state, or the acceptable input set of the goto state obtained through the Goto function when the input symbols are input in the current state is the subset of the acceptable input set of the current state s having the depth d;

use a value of the Goto function when the input symbols are input in the current state as the Failure state of state s having the depth of d, if the Goto function does not fail when the input symbols are input in the current state, and the acceptable input set of the goto state obtained by the Goto function when the input symbols are input in the current state is not the subset of the acceptable input set of state s; and

end processing state r, if the Goto function fails when all the input symbols are input in state r.

10. The device according to claim 9, wherein the Failure state generating sub-unit determines whether the acceptable input set of the goto state obtained through the Goto function when the input symbols are input in the current state is the subset of the acceptable input set of state s according to the following procedure:

traversing the input symbol set, determining that the acceptable input set of the goto state obtained through the Goto function when the input symbols are input in the current state is not the subset of the acceptable input set of state s, if a symbol b satisfying condition g(g (state, a), b)≠

fail and g(s, b)=fail exists, wherein a is an input symbol in state r having the depth of d-1;

otherwise, determining that the acceptable input set of the goto state obtained through the Goto function when the input symbols are input in the current state is the subset of the acceptable input set of state s.

11. The device according to claim 9, further comprising:

a first determination unit, adapted to use the value of the Goto function when the input symbols are input in the current state as the Failure state of state s having the depth of d, when determining that the Goto function is 0 when the input symbols are input in the current state.

12. The device according to claim 10, further comprising:

a first determination unit, adapted to use the value of the Goto function when the input symbols are input in the current state as the Failure state of state s having the depth of d, when determining that the Goto function is 0 when the input symbols are input in the current state.

13. The device according to claim 9, further comprising:

a second determination unit, adapted to directly set the Failure state of state s having the depth of d to 0 when determining that the Goto function does not fail when the input symbols are input in the current state, the acceptable input set of the goto state obtained through the Goto function when the input symbols are input in the current state is the subset of the acceptable input set of state s, and the current state is 0.

14. The device according to claim 10, further comprising:

a second determination unit, adapted to directly set the Failure state of state s having the depth of d to 0 when determining that the Goto function does not fail when the input symbols are input in the current state, the acceptable input set of the Goto state obtained through the Goto function when the input symbols are input in the current state is the subset of the acceptable input set of state s, and the current state is 0.