System and method for DFA-NFA splitting
View Patent ↗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.
1. 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.
2. The method of claim 1 , wherein the step of compiling an entrance ruleset into a DFA comprises:
generating entrance expressions corresponding to said determined entrance paths;
compiling said entrance expressions into an entrance NFA; and
compiling, by subset construction, said entrance NFA into said DFA for execution by said DFA engine.
3. The method of claim 1 , wherein said step of compiling an entrance ruleset into a DFA comprises:
labeling each NFA state and transition on any entrance path with a list of entrance path IDs which correspond to all determined entrance paths traversing said NFA state;
treating each state with multiple IDs listed as multiple states during subset construction with one variant for each ID;
including all ID variants of each start state in the subset for a DFA root state; and
when constructing DFA next states, limiting NFA transitions so that each NFA state may transition only through NFA transitions with the same ID.
4. The method of claim 1 , wherein said plurality of factors are summed in the cost function.
5. The method of claim 1 , wherein said plurality of factors are summed in the cost function and said plurality of factors are individually multiplied by a cost weight.
6. 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.
7. The method of claim 6 , wherein said step of compiling an entrance ruleset into a DFA comprises:
generating entrance expressions corresponding to said selected entrance paths;
compiling said entrance expressions into an entrance NFA; and
compiling by subset construction said entrance NFA into said DFA for execution by a DFA engine.
8. The method of claim 6 , wherein said plurality of factors are summed in the cost function.
9. The method of claim 6 , wherein said plurality of factors are summed in said cost function and said plurality of factors are individually multiplied by a cost weight.