1/(1-1/k)-Optimal Algorithm for Regular Expression Grouping
Ting Liu · 2012
Dividing regular expression sets into multiple groups is an important process to solve the problem of DFA state explosion.Previous grouping algorithms are heuristic or are done by brute-force,which have poor grouping results.This paper analyzes the reasons of states explosion and summarizes conflicting relationship among regular expressions of some types.When conflicts are non-negative and independent,the optimum k-grouping problem of regular expression sets can be reduced to the maximum k-cut problem,which is NP-hard.Based on the idea of local searching,a new grouping algorithm named GRELS is introduced to solve the problem efficiently,which is 1/(1-1/k)-approximation for maximum k-cut problem.Comparing with previous grouping algorithms,GRELS has the minimum number of states for the same number of groups,and requires the least time to update grouping results when pattern sets change.