Input partitioning and minimization for automaton implementations of capturing group regular expressions
View Patent ↗A method for submatch extraction may include receiving an input string, receiving a regular expression, and converting the regular expression with capturing groups into a plurality of finite automata to extract submatches. The method further includes using a first automaton to determine whether the input string is in a language described by the regular expression, and to process the input string, and using states of the first automaton in a second automaton to extract the submatches. In addition, input partitioning and automaton minimization techniques may be employed to reduce the storage area consumed by the plurality of finite automata.
1. In a system including a first automaton for finding a match between an input string and a regular expression and including a second automaton for extracting submatches corresponding to capturing groups in the regular expression, a method for creating input partitions for the first and second automata, the method comprising:
grouping a plurality of first state transition entries of the first automaton into a first automaton input partition when all of the first state transition entries cause the first automaton to transition from a first current state to the same first next state; and
grouping a plurality of selected states of the first automaton into a second automaton input partition when (1) all of the selected states cause the second automaton to transition from a second current state to the same second next state and (2) all of the selected states cause the second automaton to output a same tag value, wherein the tag value indicates a start and an end of a corresponding extracted submatch.
2. The method of claim 1 , wherein:
the first automaton determines whether the input string matches the regular expression by processing characters of the input string in a reversed order; and
the second automaton determines boundaries of the submatches by processing states transitioned by the first automaton in a reversed order.
3. The method of claim 1 , wherein the first automaton transitions from the first current state to the first next state in response to a transition function defined by the first current state and the first automaton input partition.
4. The method of claim 1 , wherein the second automaton transitions from the second current state to the second next state in response to a transition function defined by the second current state and the second automaton input partition.
5. The method of claim 1 , further comprising:
grouping the plurality of selected states of the first automaton into a first initial partition when (1) the selected states are either all final states or all non-final states and (2) all the selected states cause the second automaton to generate the same tag value when provided as inputs to the second current state of the second automaton; and
deriving, for the first automaton, a first equivalent automaton having a minimum number of states in response to grouping the plurality of selected states of the first automation into the first initial partition.
6. The method of claim 1 , further comprising:
removing certain states from the second automaton input partition to define a second initial partition when the certain states cause the second automaton to generate different tag values when provided as inputs to the second current state of the second automaton; and
deriving, for the second automaton, a second equivalent automaton having a minimum number of states in response to defining the second initial partition.
7. The method of claim 1 , wherein the plurality of first state transition entries represent a set of input values included in the input string, and wherein the first automaton input partition is defined by a single coded value representing the set of input values of the first automaton.
8. A system for creating input partitions for first and second automata, wherein the first automaton is to find a match between an input string and a regular expression and the second automaton is to extract submatches corresponding to capturing groups in the regular expression, the system comprising:
means for grouping a plurality of first state transition entries of the first automaton into a first automaton input partition when all of the first state transition entries cause the first automaton to transition from a first current state to the same first next state; and
means for grouping a plurality of selected states of the first automaton into a second automaton input partition when (1) when all of the selected states cause the second automaton to transition from a second current state to the same second next state and (2) all of the selected states cause the second automaton to output a same tag value, wherein the tag value indicates a start and an end of a corresponding extracted submatch.
9. The system of claim 8 , wherein:
the first automaton determines whether the input string matches the regular expression by processing characters of the input string in a reversed order; and
the second automaton determines boundaries of the submatches by processing states transitioned by the first automaton in a reversed order.
10. The system of claim 8 , wherein the first automaton is to transition from the first current state to the first next state in response to a transition function defined by the first current state and the first automaton input partition.
11. The system of claim 8 , wherein the second automaton is to transition from the second current state to the second next state in response to a transition function defined by the second current state and the second automaton input partition.
12. The system of claim 8 , further comprising:
means for grouping the selected states of the first automaton into a first initial partition when (1) the selected states are either all final states or all non-final states and (2) all the selected states cause the second automaton to generate the same tag value when provided as inputs to the second current state of the second automaton; and
means for deriving, for the first automaton, a first equivalent automaton having a minimum number of states in response to the first initial partition.
13. The system of claim 8 , further comprising:
means for removing certain states from the second automaton input partition to define a second initial partition when the certain states cause the second automaton to generate different tag values when provided as inputs to the second current state of the second automaton; and
means for deriving, for the second automaton, a second equivalent automaton having a minimum number of states in response to the second initial partition.
14. The system of claim 8 , wherein the plurality of first state transition entries represent a set of input values included in the input string, and wherein the first automaton input partition is defined by a single coded value representing the set of input values of the first automaton.
15. A system for creating input partitions for first and second automata, wherein the first automaton is to find a match between an input string and a regular expression and the second automaton is to extract submatches corresponding to capturing groups in the regular expression, the system comprising:
a processor; and
a memory coupled to the processor and having stored therein computer-executable instructions that when executed by the processor cause the system to:
group a plurality of first state transition entries of the first automaton into a first automaton input partition if all of the first state transition entries cause the first automaton to transition from a first current state to the same first next state; and
group a plurality of selected states of the first automaton into a second automaton input partition if (1) all of the selected states cause the second automaton to transition from a second current state to the same second next state and (2) all of the selected states cause the second automaton to output a same tag value, wherein the tag value indicates a start and an end of a corresponding extracted submatch.
16. The system of claim 15 , wherein:
the first automaton determines whether the input string matches the regular expression by processing characters of the input string in a reversed order; and
the second automaton determines boundaries of the submatches by processing states transitioned by the first automaton in a reversed order.
17. The system of claim 15 , wherein the instructions, when executed by the processor, further cause the system to:
group the selected states of the first automaton into a first initial partition if (1) the selected states are either all final states or all non-final states and (2) all the selected states cause the second automaton to generate the same tag value when provided as inputs to the second current state of the second automaton; and
derive, for the first automaton, a first equivalent automaton having a minimum number of states in response to the first initial partition.
18. The system of claim 15 , wherein the instructions, when executed by the processor, further cause the system to:
remove certain states from the second automaton input partition to define a second initial partition if the certain states cause the second automaton to generate different tag values when provided as inputs to the second current state of the second automaton; and
derive, for the second automaton, a second equivalent automaton having a minimum number of states in response to the second initial partition.
19. The system of claim 15 , wherein the plurality of first state transition entries represent a set of input values included in the input string, and wherein the first automaton input partition is defined by a single coded value representing the set of input values of the first automaton.