Impulse regular expression matching
View Patent ↗Disclosed is a method and apparatus for matching regular expressions. A buffer of symbols giving a number of the last occurrence positions of each symbol is maintained. When two constants match on either side of a regular expression operator, the buffer of symbols is queried to determine if a member of the complement of the regular expression operator occurred between the two constants. If so, then the operator was not satisfied. If not, then the operator was satisfied.
1. A system that matches a string of symbols to a regular expression pattern, said regular expression pattern comprising a first constant, a second constant, and a first operator, said first operator occurring between said first constant and said second constant in said regular expression pattern, comprising:
a processor;
a memory;
a deterministic finite automaton (DFA) engine that matches said first constant to said regular expression pattern starting at a first position in said string of symbols, the first DFA engine matching said second constant to said regular expression pattern ending at a second position in said string of symbols; and
a buffer of symbols that associates a plurality of positions of occurrences of a plurality of symbols in said string of symbols, said buffer of symbols producing an indicator that a position of a symbol from a complementary set of symbols is between said first position and said second position, said complementary set of symbols being based on a complement of said first operator, said indicator corresponding to whether the first operator is satisfied.
2. The system of claim 1 , wherein said buffer of symbols selects an occurrence position from said plurality of positions of occurrences based on associations to said complementary set of symbols.
3. The system of claim 1 , further comprising:
a plurality of that match a plurality of constants to said regular expression pattern at a plurality of starting positions and a plurality of ending positions in said string of symbols, said plurality of starting positions and said plurality of ending positions defining a plurality of ranges of positions that are compared with at least one of said positions of occurrences to determine if at least one of a plurality of operators occurring between two of said plurality of constants is not satisfied.
4. A method of matching a string of symbols to a regular expression pattern, said regular expression pattern comprising a first constant, a second constant, and a first operator, said first operator occurring between said first constant and said second constant in said regular expression pattern, comprising:
using a first deterministic finite automaton (DFA), matching said first constant to said regular expression starting at a first position in said string of symbols and matching said second constant to said regular expression ending at a second position in said string of symbols; and,
associating a plurality of positions of occurrences of a plurality of symbols in said string of symbols;
producing an indicator that a position of a symbol from a complementary set of symbols is between said first position and said second position, said complementary set of symbols being based on a complement of said first operator, said indicator corresponding to whether the first operator is satisfied.
5. The method of claim 4 , further comprising:
selecting an occurrence position from said plurality of positions of occurrences based on associations to said complementary set of symbols.
6. The method of claim 4 , further comprising:
matching a plurality of constants to said regular expression pattern at a plurality of starting positions and a plurality of ending positions in said string of symbols, said plurality of starting positions and said plurality of ending positions defining a plurality of ranges of positions that are compared with at least one of said positions of occurrences to determine if at least one of a plurality of operators occurring between two of said plurality of constants is not satisfied.
7. One or more non-transitory, computer readable medium having instructions stored thereon for matching a string of symbols to a regular expression pattern, said regular expression pattern comprising a first constant, a second constant, and a first operator, said first operator occurring between said first constant and said second constant in said regular expression pattern that, when executed by a computer, at least instruct the computer to:
using a first deterministic finite automaton (DFA), match said first constant to said regular expression starting at a first position in said string of symbols and match said second constant to said regular expression ending at a second position in said string of symbols; and,
associate a plurality of positions of occurrences of a plurality of symbols in said string of symbols; and,
produce an indicator that a position of a symbol from a complementary set of symbols is between said first position and said second position, said complementary set of symbols being based on a complement of said first operator, said indicator corresponding to whether the first operator is satisfied.
8. The one or more non-transitory, computer readable medium of claim 7 , wherein the computer is further instructed to:
select an occurrence position from said plurality of positions of occurrences based on associations to said complementary set of symbols.
9. The one or more non-transitory, computer readable medium of claim 7 , wherein the computer is further instructed to:
match a plurality of constants to said regular expression pattern at a plurality of starting positions and a plurality of ending positions in said string of symbols, said plurality of starting positions and said plurality of ending positions defining a plurality of ranges of positions that are compared with at least one of said positions of occurrences to determine if at least one of a plurality of operators occurring between two of said plurality of constants is not satisfied.