Patent Document ID: 10042654
Application ID: 14300633
Patent Flag: 1

Claim One:
1. A computer program product for preventing state explosion by distributing sets of regular expressions to a fixed number of state machine engines, the computer program product comprising: a non-transitory computer readable storage medium having program code embodied therewith, the program code executable by the computer to perform a method comprising: combining a plurality of regular expressions into a single compound regular expression; creating a single nondeterministic finite automaton (NFA) including a plurality of NFA states based on the compound regular expression; performing an interference analysis for each pair of NFA states to identify all pairs of NFA states that would potentially interfere in an equivalent deterministic finite automaton (DFA) performing the interference analysis further comprising: performing a co-occurrence analysis for each pair of NFA states to determine whether the two constituent states can simultaneously be active in the NFA, performing the co-occurrence analysis further comprising determining whether the input to any one of the NFA states while a first of the two constituent states is active may result in a second transition from the one of the NFA states to a second of the two constituent states while the first of the two constituent states remains active; and performing an independence analysis for each pair of NFA states having a positive result in the co-occurrence analysis to determine whether each of the two constituent states can be active in the NFA while the other is not active, wherein all pairs of NFA states having a positive result in the independence analysis are deemed to potentially interfere in the equivalent DFA; creating an interference graph representing all regular expressions associated with potentially interfering NFA states based on the results of the interference analysis; performing a graph coloring algorithm on the interference graph to assign a color to each represented regular expression in the graph; representing each regular expression associated with a potentially interfering NFA state by a node in the interference graph; connecting each pair of regular expressions associated with potentially interfering states by an edge, wherein each color corresponds to a particular DFA engine available to execute at least a portion of the equivalent DFA; wherein when there is not a node in the interference graph with fewer edges than a total number of colors, causing the graph coloring algorithm is configured to: select a first node having the greatest number of edge connections in the interference graph, split the first node into two or more constituent nodes, each of which has fewer edge connections than the total number of available colors, the split of the first node being a split of an underlying regular expression, and then assign a DFA extension to at least one of the constituent nodes in order to maintain the original NFA functionality; and based on there being no DFA extension available to assign for the first node, mark the first node as fixed and then restart coloring; wherein when there are nodes in the interference graph with fewer edges than the total number of colors, the graph coloring algorithm is configured to remove the nodes having fewer edges than the total number of colors from the interference graph; assigning regular expressions of a particular color to a particular DFA engine corresponding to the particular color; and executing regular expressions by corresponding DFA engines on streams of input characters.