AREA/ENERGY COMPLEX REGULAR EXPRESSION PATTERN MATCHING HARDWARE FILTER BASED ON TRUNCATED DETERMINISTIC FINITE AUTOMATA (DFA)
A method and apparatus are described for performing complex regex pattern matching utilizing filters based on truncated Deterministic Finite Automata (DFA). For example, one embodiment of a method comprises: representing a set of reference strings as a DFA; truncating the DFA based on a truncating policy, wherein the truncated DFA does not generate a false positive match; creating a filter based on the truncated DFA; filtering an input string against the set of reference strings by running the input string through the filter.
1 . An apparatus comprising:
a string convertor circuit to represent a set of reference strings as a deterministic finite automaton (DFA);
a DFA truncator circuit to truncate the DFA based on a truncating policy, wherein the truncated DFA does not generate a false positive match;
a filter circuit, based on the truncated DFA, to filter an input string against the set of reference strings.
2 . The apparatus of claim 1 , wherein the truncating policy comprises truncating the DFA at a fixed depth.
3 . The apparatus of claim 1 , wherein the truncating policy comprises truncating the DFA based on a selected probability of reaching a certain state in the DFA.
4 . The apparatus of claim 1 , wherein the filter circuit comprises a memory to store one or more state-transition pairs of the truncated DFA.
5 . The apparatus of claim 4 , wherein the one or more state-transition pairs of the truncated DFA comprise every unique state-transition pairs in the truncated DFA.
6 . The apparatus of claim 4 , wherein the one or more state-transition pairs of the truncated DFA comprise one or more frequently-matched unique state-transition pairs in the truncated DFA.
7 . The apparatus of claim 4 , wherein the filter circuit comprises one or more range comparator circuits to detect whether a given character from the input string is within a range of characters specified by one of the one or more state-transition pairs in the truncated DFA.
8 . The apparatus of claim 7 , wherein the detection of whether a given character from the input string is within a range of characters specified by one of the one or more state-transition pairs in the truncated DFA is made irrespective of whether the given character is of uppercase or lowercase representation.
9 . A method comprising:
representing a set of reference strings as a deterministic finite automaton (DFA);
truncating the DFA such that the truncated DFA does not generate a false positive match;
filtering an input string against the set of reference strings using a filter based on the truncated DFA.
10 . The method of claim 9 , wherein truncating the DFA comprises truncating the DFA at a fixed depth.
11 . The method of claim 9 , wherein truncating the DFA comprises truncating the DFA based on a selected probability of reaching a certain state in the DFA.
12 . The method of claim 9 , wherein filtering the input string against the set of reference strings comprises:
identifying one or more state-transition pairs in the truncated DFA;
storing the identified one or more state-transition pairs in a memory;
detecting whether a given character from the input string is within a range of characters specified by one of the one or more identified state-transition pairs in the truncated DFA.
13 . The method of claim 12 , wherein the one or more identified state-transition pairs comprise every unique state-transition pairs in the truncated DFA.
14 . The method of claim 12 , wherein the one or more identified state-transition pairs comprise one or more frequently-matched unique state-transition pairs in the truncated DFA.
15 . The method of claim 12 , wherein the detection of whether a given character from the input string is within a range of characters specified by one of the one or more identified state-transition pairs in the truncated DFA is made irrespective of whether the given character is of uppercase or lowercase representation.