Begin anchor annotation in DFAs
View Patent ↗Disclosed is a method and system of matching a string of symbols to a ruleset. The ruleset comprise a set of rules. The method includes ignoring begin anchor requirements when constructing a DFA from all the rules of the ruleset, annotating the accepting states of the DFA with the begin anchor information, executing the DFA, and checking begin anchor annotations to determine if begin anchor requirement are satisfied if an accepting state is reached. Embodiments also include rulesets with begin anchors on matches, rulesets with early exit information on non-accepting states, and rulesets with accept begin anchors in accepting states.
1. A method of matching a string of symbols to a ruleset, said ruleset comprising a set of pattern matching rules, comprising:
at a compiler;
ignoring begin anchor requirements when constructing a DFA from all the rules of the ruleset; and
annotating the accepting states of the DFA with begin anchor information;
at a server,
receiving an input stream comprising said string of symbols;
to match symbols in said string of symbols, executing the DFA by a descent from a DFA root state;
checking the begin anchor annotations to determine whether begin anchor requirements are satisfied if an accepting state match is reached; and
reporting the match if the begin anchor requirements as annotated are satisfied; and
prior to descent of the DFA, building a record of which begin anchors are satisfied by a first symbol position, wherein the record is referable during each DFA descent to check begin anchor status.
2. The method of claim 1 , wherein the step of annotating the accepting states comprises annotating each instruction that indicates a match with the begin anchor requirement.
3. A method of matching a string of symbols to a ruleset, said ruleset comprising a set of pattern matching rules, comprising:
at a compiler;
ignoring begin anchor requirements when constructing a DFA from all the rules of the ruleset;
annotating the accepting states of the DFA with begin anchor information;
when a potential match in an accepting state is annotated with begin anchor requirements, encoding such information with a single indicator, wherein at least one indicator represents a plurality of supported anchors; and
at a server,
receiving an input stream comprising said string of symbols;
to match symbols in said string of symbols, executing the DFA by a descent from a DFA root state;
checking the begin anchor annotations to determine whether begin anchor requirements are satisfied if an accepting state match is reached; and
reporting the match if the begin anchor requirements as annotated are satisfied.
4. A method of matching a string of symbols to a ruleset, said ruleset comprising a set of pattern matching rules, comprising:
at a compiler,
ignoring begin anchor requirements when constructing a DFA from all the rules of the ruleset; and
annotating at least one state of the DFA with early exit information, said early exit information comprising begin anchor requirements for all accepting states reachable from said state; and
at a server,
receiving an input stream comprising said string of symbols;
to match symbols in said string of symbols, executing the DFA by a descent from a DFA root state; and
terminating the descent if, during the execution of the DFA when visiting said at least one state, early exit information is not satisfied.
5. The method of claim 4 , wherein the step of annotating at least one state of the DFA comprises annotating all states of the DFA with early exit information.
6. The method of claim 4 , wherein the step of annotating at least one state of the DFA comprises annotating all non-accepting states with early exit information.
7. A method of matching a string of symbols to a ruleset, said ruleset comprising a set of pattern matching rules, comprising:
at a compiler,
ignoring begin anchor requirements when constructing a DFA from all the rules of the ruleset; and
annotating at least one accepting state of the DFA with accept begin anchor information, said accept begin anchor information indicating all distinct begin anchor requirements for rule matches associated with said accepting state; and
at a server,
receiving an input stream comprising said string of symbols;
to match symbols in said string of symbols, executing the DFA by a descent from a DFA root state;
if an accepting state is visited, comparing the accept begin anchor annotations directly to a current anchor status;
if at least one accept begin anchor is satisfied by the current anchor status, determining that at least one match is successful; and
if it is determined that at least one match is successful, examining each match to determine if its anchor requirements are satisfied, and outputting information for each match if its anchor requirements are satisfied.
8. The method of claim 7 , further comprising:
updating last accepting state information for greedy matching if it is determined that at least one match is successful.