Regular expression matching
View Patent ↗Example embodiments relate to regular expression matching. An example method may include generating a data structure based on a non-deterministic finite automaton (NFA) that represents a regular expression. The data structure may include a set of segments where each segment indicates a segment starting state of the NFA. Each segment may represent zero or more consecutive states of the NFA starting at the segment starting state. Different segments of the set of segments may be capable of indicating different segment starting states on the NFA. Each segment may represent a partial match of the regular expression to the string. The method may further include analyzing the string in relation to the NFA. The method may further include modifying the data structure as the string is analyzed. Such modification may include attempting to expand at least one of the segments in the set to represent additional states of the NFA.
1. A method for matching a regular expression to a string, the method comprising:
generating, by a processor of a computing device, a data structure based on a non-deterministic finite automaton (NFA) that represents the regular expression, wherein the data structure includes a set of segments, each segment indicating a segment starting state of the NFA, and each segment representing zero or more consecutive states of the NFA starting at the segment starting state, and wherein different segments of the set of segments are capable of indicating different segment starting states on the NFA, and wherein each segment represents a partial match of the regular expression to the string;
analyzing, by the processor, the string in relation to the NFA; and
modifying, by the processor, the data structure as the string is analyzed, such modification including attempting to expand at least one of the segments in the set to represent additional states of the NFA.
2. The method of claim 1 , wherein analyzing the string includes:
maintaining a pointer to a currently analyzed character of the string, wherein the currently analyzed character is compared to states of the NFA; and
jumping the pointer to later characters of the string when none of the segments of the set can be extended further, wherein the jumping includes moving the pointer over multiple characters of the string that have not yet been analyzed.
3. The method of claim 1 , wherein attempting to expand at least one of the segments includes attempting to expand a first segment to the left and to the right.
4. The method of claim 1 , wherein attempting to expand at least one of the segments includes attempting to expand a first segment to the left when a currently analyzed character of the text string matches a state represented by the first segment.
5. The method of claim 4 , wherein attempting to expand at least one of the segments includes attempting to expand the first segment to the right when a currently analyzed character of the text string matches a state represented by the first segment and the first segment cannot be extended any further to the left.
6. The method of claim 1 , wherein the modification includes attempting to expand multiple segments in the set such that each segment represents additional states of the NFA.
7. The method of claim 1 , wherein the set of segments only includes one segment for each state of the NFA, and wherein the modification includes attempting to expand all segments in the set such that each segment represents additional states of the NFA.
8. The method of claim 1 , wherein the set of segments initially only includes one segment for each state of a subset of the states of the NFA, wherein the subset of states of the NFA is separated from the rest of the states of the NFA by a state that represents a wildcard, and wherein the modification includes attempting to expand all segments in the set such that each segment represents additional states of the NFA.
9. A non-transitory machine-readable storage medium storing instructions for matching a regular expression to a string, the instructions executable by a processor of a computing device to cause the processor to:
generate a data structure based on a non-deterministic finite automaton (NFA) that represents the regular expression, wherein the data structure initially includes a first state that includes a set of segments, each segment indicating a segment starting state of the NFA, and each segment representing zero or more consecutive states of the NFA starting at the segment starting state, and wherein different segments of the set of segments are capable of indicating different segment starting states on the NFA, and wherein each segment represents a partial match of the regular expression to the string;
analyze the string in relation to the NFA, wherein a pointer is maintained to a currently analyzed character of the string; and
modify the data structure as the string is analyzed, such modification including adding states to the data structure as characters of the string are matched to states of the NFA.
10. The non-transitory machine-readable storage medium of claim 9 , wherein the added states include a second state that includes a set of segments that are the same as the segments of the first state except that at least one of the segments is expanded to represent additional states of the NFA.
11. The non-transitory machine-readable storage medium of claim 9 , wherein the added states include a third state that includes a set of segments that are the same as the segments of the first state except that multiple of the segments are expanded to represent additional states of the NFA.
12. The non-transitory machine-readable storage medium of claim 9 , wherein the instructions are further to cause the processor to modify the data structure to add edges to the added states from existing states of the data structure, wherein each edge represents a type of movement of the pointer on the string.
13. The non-transitory machine-readable storage medium of claim 12 , wherein each edge is related to how the set of segments of the particular added state change compared to the source state from which the edge came.
14. The non-transitory machine-readable storage medium of claim 13 , wherein each edge represents one of the following: extend left, extend right, jump at least one character to the right.
15. A system, comprising:
at least one repository to store a string, a non-deterministic finite automaton (NFA) that represents a regular expression, and a data structure based on the NFA, wherein the data structure includes a set of segments, each segment indicating a segment starting state of the NFA, and each segment representing zero or more consecutive states of the NFA starting at the segment starting state, and wherein different segments of the set of segments are capable of indicating different segment starting states on the NFA, and wherein each segment represents a partial match of the regular expression to the string;
a processor; and
a memory storing instructions that when executed cause the processor to match the regular expression to the string, wherein to match the regular expression to the string, the instructions are to cause the processor to analyze the string in relation to the NFA and modify the data structure as the string is analyzed, such modification including attempting to expand at least one of the segments in the set to represent additional states of the NFA.
16. The system of claim 15 , wherein the instructions are to cause the processor to analyze the string, including causing the processor to:
maintain a pointer to a currently analyzed character of the string, wherein the currently analyzed character is compared to states of the NFA; and
jump the pointer to later characters of the string when none of the segments of the set can be extended further, wherein the jumping includes moving the pointer over multiple characters of the string that have not yet been analyzed.
17. The system of claim 15 , wherein to attempt to expand at least one of the segments, the instructions are to cause the processor to attempt to expand a first segment to the left when a currently analyzed character of the text string matches a state represented by the first segment.
18. The system of claim 15 , wherein to attempt to expand at least one of the segments, the instructions are to cause the processor to attempt to expand the first segment to the right when a currently analyzed character of the text string matches a state represented by the first segment and the first segment cannot be extended to the left.