Determination and Handling of Subexpression Overlaps in Regular Expression Decompositions

Abstract

A computer-implemented method for transforming a finite state automaton (FSA) of a regular expression includes determining, by a computer, a first subexpression R 1 and a second subexpression R 2 in the regular expression; calculating an overlap FSA, the overlap FSA configured to determine the existence of a partial overlap or a full overlap between the first subexpression R 1 and the second subexpression R 2 ; determining whether the overlap FSA has an accepting state; and in the event the overlap FSA is determined not to have an accepting state, determining that the transformation of the regular expression is safe, and constructing a transformed FSA of the regular expression comprising a first FSA for the first subexpression R 1 and a second FSA for the second subexpression R 2 .

1 . A computer-implemented method for transforming a finite state automaton (FSA) of a regular expression, the method comprising:
 determining, by a computer, a first subexpression R 1  and a second subexpression R 2  in the regular expression;   calculating an overlap FSA, the overlap FSA configured to determine the existence of a partial overlap or a full overlap between the first subexpression R 1  and the second subexpression R 2 ;   determining whether the overlap FSA has an accepting state; and   in the event the overlap FSA is determined not to have an accepting state, determining that the transformation of the regular expression is safe, and constructing a transformed FSA of the regular expression comprising a first FSA for the first subexpression R 1  and a second FSA for the second subexpression R 2 .   
     
     
         2 . The method of  claim 1 , wherein the overlap FSA is given by:
   (.* R   1   .*∪.*R   2 )\( R   1   .*R   2 ).   
     
     
         3 . The method of  claim 1 , further comprising in the event the overlap FSA is determined to have an accepting state, determining that the transformation of the regular expression is not safe. 
     
     
         4 . The method of  claim 1 , further comprising in the event the overlap FSA is determined to have an accepting state, calculating one or more overlap FSAs, the one or more overlap FSAs configured to determine the existence of multiple full overlap between the first subexpression R 1  and the second subexpression R 2 . 
     
     
         5 . The method of  claim 4 , wherein the number of one or more overlap FSAs is equal to a maximum number N MAX  of occurrences of first subexpression R 1  in second subexpression R 2 , and wherein each of the one or more overlap FSAs is configured to detect a false positive result corresponding to a respective number N, from 1 to N MAX , of occurrences of first subexpression R 1  in second subexpression R 2 . 
     
     
         6 . The method of  claim 5 , further comprising:
 setting a value of a counter in a post-processor to zero;   scanning an input stream by the first FSA, the second FSA, and the one or more overlap FSAs;   incrementing the counter whenever a match is reported by the first FSA to the post-processor; and   in the event a match is reported by the second FSA to the post-processor:
 determining whether a particular FSA of the one or more overlap FSAs is at an accepting state, and in the event the particular FSA is at an accepting state:
 determining whether the value of the counter is greater than or equal to a value of N associated with the particular FSA, and in the event the value of the counter is greater than or equal to N, reporting a match for the regular expression in the input stream by the post-processor. 
 
   
     
     
         7 . The method of  claim 4 , further comprising determining whether the one or more overlap FSAs have memory requirements that are greater than a predetermined threshold, and in the event the one or more overlap FSAs are determined to have memory requirements that are greater than the predetermined threshold, constructing an untransformed FSA of the regular expression. 
     
     
         8 - 20 . (canceled)