Dual dfa decomposition for large scale regular expression matching

A method for matching a first input string with a first regular expression set in a data processing system, the method comprising:

• determining, by the data processing system, a minimal set of non-overlapping symbol sets that are represented in the first regular expression set;
• mapping, by the data processing system, the non-overlapping symbol sets to new symbols, respectively;
• generating, by the data processing system, a second regular expression set by re-writing the first regular expression set to remove components that cause state machine complexities;
• generating, by the data processing system, a third regular expression set by replacing symbol sets in expressions in the first regular expression with the corresponding new symbols;
• and
• determining, by the data processing system, whether the first input string matches the first regular expression using a first state machine built from the second regular expression set and a second state machine build from the third regular expression set.