System and method for DFA-NFA splitting
AssigneeIntel Corporation
InventorMichael Ruehle
Life of this patent
Estimating the term…
Abstract
Cost factors are utilized and may be estimated to determine split points in a DFA-NFA hybrid. The cost factors may comprise NFA start states, DFA backup factor, DFA-NFA token frequency, DFA steps to match, and NFA states to match. Other cost factors may be used as necessary. The cost factors are multiplied by tunable coefficients and summed. NFA states at minimum cost points are determined for entrance states in the NFA. A DFA is compiled from the entrance paths to the entrance states. NFA states and transitions needed only to reach entrance states may be deleted and all remaining NFA states are made available for execution by the NFA engine. An NFA representation of an NFA is examined by bounded depth-first recursion from each start state.
Claims9
A method of splitting an automaton into a DFA portion and an NFA portion, the method comprising:
- compiling a ruleset into an NFA representation;
- analyzing said NFA to determine entrance paths for matching by a DFA engine and tail portions for matching by an NFA engine, said entrance paths and tail portions covering a whole NFA;
- and
- compiling said entrance paths into a DFA for execution by a DFA engine, wherein accepting states of said DFA are configured to signal from said DFA engine to an NFA engine to activate associated tail portion entrance states inside said NFA engine;
- wherein said process of analyzing comprises evaluating a cost function, said cost function comprising a plurality of factors, said plurality of factors comprising NFA start states, DFA backup factor, DFA-NFA token frequency, DFA steps to match, and NFA states to match.
A method of splitting an automaton into a DFA portion and an NFA portion, the method comprising:
- compiling a ruleset into an NFA representation;
- analyzing said NFA to determine entrance paths for matching by a DFA engine and tail portions for matching by an NFA engine, said entrance paths and tail portions covering a whole NFA;
- and
- compiling said entrance paths into a DFA for execution by a DFA engine, wherein accepting states of said DFA are configured to signal from said DFA engine to an NFA engine to activate associated tail portion entrance states inside said NFA engine;
- wherein said process of analyzing comprises:
- evaluating a cost function, said cost function comprising a plurality of factors comprising NFA start states, DFA backup factor, DFA-NFA token frequency, DFA steps to match, and NFA states to match;
- and
- recursively analyzing said NFA, wherein entrance paths are examined in depth first order, and selected when the cost function values are lower than cost function values for shorter and longer entrance paths.
Dependencies are inferred from the claim text.