Method and device for creating pattern matching state machine

• US 8,583,961 B2
• Filed: 05/17/2010
• Issued: 11/12/2013
• 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: Chen, Jian, Wei, Qikun, Chen, Guohai
• Primary Examiner(s): PATEL, KAMINI B
• Application Number:
  US12/781,650
• Publication Number:
  US 20100229040A1
• Time in Patent Office: 1,275 Days
• Field of Search: 714/27
• 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;

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.

2. The method according to claim 1, 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.

3. The method according to claim 1, 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.

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 1, 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.

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. A device of creating a pattern matching state machine, comprising:

one or more processors; and

a memory for storing instructions, which, when executed by the one or more processors, cause the one or more processors to;

obtain a predefined keyword set;

generate a Goto function according to the keyword set;

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

generate an Output function according to the Goto function and the Failure function;

wherein when the instructions cause the one or more processors to construct the Failure function according to the generated Goto function, the one or more processors are further configured to;

set the Failure state of all states having a depth of 1 to an initial state;

obtain a Failure state of a previous state r having a depth of d-1 as a current state in sequence;

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.

8. The device according to claim 7, wherein the instructions cause the one or more processors to determine 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, the one or more processors are further configured to:

traverse the input symbol set, determine 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, determine 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 states.

9. The device according to claim 7, wherein the instructions further cause the one or more processors 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.

10. The device according to claim 8, wherein the instructions further cause the one or more processors 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.

11. The device according to claim 7, wherein the instructions further cause the one or more processors 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.

12. The device according to claim 8, wherein the instructions further cause the one or more processors 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.