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 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 before said first constant in said regular expression pattern, comprising:
matching said first constant using a deterministic finite automaton (DFA); and,
in response to matching said first constant, matching said first operator by determining if a member of a complement of a symbol set defined by said first operator occurred in said string of symbols between a starting position of said first operator in said string of symbols and an ending position of said first operator in said string of symbols.
2. The method of claim 1 , further comprising:
associating an indicator of a position in said string of symbols of said member of said complement of said symbol set; and,
wherein said determining if said member of said complement of said symbol set is between said starting position and said ending position in said string of symbols is based on said indicator.
3. The method of claim 1 , further comprising:
receiving an indicator of a position in said string of symbols of said member of said complement of said symbol set;
based on said indicator, determining if said member of said complement of said symbol set is between said starting position and said ending position in said string of symbols is based on said indicator.
4. A 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 before said first constant in said regular expression pattern that, when executed by a computer, at least instruct the computer to:
match said first constant using a deterministic finite automaton (DFA); and,
in response to matching said first constant, match said first operator by determining if a member of a complement of a symbol set defined by said first operator occurred in said string of symbols between a starting position of said first operator in said string of symbols and an ending position of said first operator in said string of symbols.
5. The non-transitory computer readable medium of claim 4 , wherein the computer is further instructed to:
associate an indicator of a position in said string of symbols of said member of said complement of said symbol set; and,
wherein said determining if said member of said complement of said symbol set is between said starting position and said ending position in said string of symbols is based on said indicator.
6. The non-transitory computer readable medium of claim 4 , wherein the computer is further instructed to:
receive an indicator of a position in said string of symbols of said member of said complement of said symbol set;
based on said indicator, determine if said member of said complement of said symbol set is between said starting position and said ending position in said string of symbols is based on said indicator.