Determining regular expression match lengths
A method and apparatus are disclosed for determining the lengths of one or more substrings of an input string that matches a regular expression (regex) The input string is searched for the regex using an non-deterministic finite automaton (NFA), and upon detecting a match state a selected portion of the input string is marked as a match string. The NFA is inverted to create a reverse NFA that embodies the inverse of the regex. For some embodiments, the reverse NFA is created by inverting the NFA such that the match state of the NFA becomes the initial state of the reverse NFA, the initial state of the NFA becomes the match state of the reverse NFA, and the goto transitions of the NFA are inverted to form corresponding goto transitions in the reverse NFA. The match string is reversed and searched for the inverted regex using the reverse NFA, and a counter is incremented for each character processed during the reverse search operation. The current value of the counter each time the match state in the reverse NFA is reached indicates the character length of a corresponding substring that matches the regex.
1. A method of determining lengths of one or more substrings within an input string of characters that matches a regular expression embodied by a non-deterministic finite state automaton (NFA) stored in a search system including a forward search engine, a reverse search engine, and an inversion circuit, the method comprising:
comparing the input string with the regular expression using the NFA in a forward search operation performed in the forward search engine;
detecting a match state in the NFA in the forward search engine;
selecting a portion of the input string as a match string in response to the match state;
inverting the NFA to create a reverse NFA that embodies an inverted regular expression;
reversing the match string using the inversion circuit to create a reverse match string;
comparing the reverse match string with the inverted regular expression using the reverse NFA in a reverse search operation performed in the reverse search engine; and
incrementing a count value in response to each character processed in the reverse search operation performed in the reverse search engine.
2. The method of claim 1 , wherein the NFA comprises an initial state and a number of intermediate states between the initial state and the match state, and wherein the match state of the NFA corresponds to an initial state of the reverse NFA.
3. The method of claim 2 , wherein the initial state of the NFA corresponds to a match state of the reverse NFA.
4. The method of claim 3 , further comprising:
storing the count value each time the match state of the reverse NFA is reached during the reverse search operation, wherein each stored count value indicates the character length of a corresponding matching substring.
5. A system for determining lengths of one or more substrings within an input string of characters that matches a regular expression embodied by a non-deterministic finite state automaton (NFA), comprising:
means for comparing the input string with the regular expression using the NFA in a forward search operation;
means for detecting a match state in the NFA;
means for selecting a portion of the input string as a match string in response to the match state;
means for inverting the NFA to create a reverse NFA that embodies an inverted regular expression;
means for reversing the match string to create a reverse match string;
means for comparing the reverse match string with the inverted regular expression using the reverse NFA in a reverse search operation; and
means for incrementing a count value in response to each character processed in the reverse search operation.
6. The system of claim 5 , wherein the NFA comprises an initial state and a number of intermediate states between the initial state and the match state, and wherein the match state of the NFA corresponds to an initial state of the reverse NFA.
7. The system of claim 6 , wherein the initial state of the NFA corresponds to a match state of the reverse NFA.
8. The system of claim 7 , further comprising:
means for storing the count value each time the match state of the reverse NFA is reached during the reverse search operation, wherein each stored count value indicates the character length of a corresponding matching substring.
9. A system for determining lengths of one or more substrings within an input string of characters that matches a regular expression embodied by a non-deterministic finite state automaton (NFA), comprising:
a search engine configured to compare the input string with the regular expression to identify a match string that contains the one or more substrings that match the regular expression;
an inversion circuit coupled to the search engine and configured to invert the match string to create a reverse match string;
a reverse search engine configured to compare the reverse match string with an inverted regular expression that embodies a reverse NFA; and
a counter circuit coupled to the reverse search engine and configured to increment a count value upon each compare cycle in the reverse search engine, wherein the counter circuit outputs the count value each time a match condition is detected in the reverse search engine.
10. The system of claim 9 , wherein each count value output by the counter circuit indicates the number of characters in a corresponding one of the matching substrings.
11. The system of claim 9 , wherein the NFA comprises an initial state and a number of intermediate states between the initial state and the match state, and wherein the match state of the NFA corresponds to an initial state of the reverse NFA.
12. The system of claim 11 , wherein the initial state of the NFA corresponds to a match state of the reverse NFA.
13. The system of claim 9 , wherein the search engine comprises a first content addressable memory (CAM) device, and the reverse search engine comprises a second CAM device.