Impulse regular expression matching
AssigneeIntel Corporation
InventorsAlexander Podkolzin, Lav Ivanovic, Anatoli Bolotov, Mikhail Grinchuk, Sergey Afonin
Life of this patent
Estimating the term…
Abstract
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.
Claims9
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.
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.
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.
Dependencies are inferred from the claim text.