Method and device for creating pattern matching state machine
First Claim
Patent Images
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.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
12 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. - View Dependent Claims (2, 3, 4, 5, 6)
-
-
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. - View Dependent Claims (8, 9, 10, 11, 12)
-
Specification