A grouping algorithm based on Regular Expression Similarity for DFA construction
Yao Tie, Xu Qiang, Jinrong He · 2011
In the process of constructing the deterministic finite automation (DFA) for Regular Expression Engine, we studied the similar relationship between the regular expressions, and in the progress of studying how to construct the DFA engine by the grouping algorithm, we proposed the concept and formula of Regular Expression Similarity after collecting a large number of testing data and referring to cluster analysis. Test results showed that the grouping algorithm supervised by the similarity can avoid Regular Expression fragments which lead to DFA state expansion dramatically. So the generation of DFA engine after grouping can become more effective.