Managing an expression-based DFA construction process

摘要

DFA construction may be aborted if the DFA will become too big for the computing device to handle or based on user preferences. A DFA may be constructed from an NFA, which is constructed from an expression. The expression may have a total number of operands and operators r. The determination to abort DFA construction may be based on the operands. If the number of DFA nodes constructed is more than a lower threshold and the number of DFA nodes constructed is greater than a function, f(r), the DFA construction may be aborted. If the number of DFA nodes is greater than a higher threshold, the DFA construction may be aborted. The lower threshold may be determined based on computing device capabilities and user preference. The higher threshold may be based on computing device capabilities.

主权项

1. A method for optimizing pattern analysis, the method comprising:
constructing a non-deterministic finite automaton (NFA) from a regular expression; initiating construction of a deterministic finite automaton (DFA) from the NFA by an application stored in a memory and executed by a processor of a computing device, wherein initiating construction of the DFA includes identifying a quantity of DFA nodes of the DFA; identifying a total quantity of operands and operators present in the regular expression; calculating the square of the identified total quantity of operands and operators of the regular expression; and aborting construction of the DFA based at least partially on a determination that the identified quantity of DFA nodes of the DFA is greater than the calculated square of the identified total quantity of operands and operators in the regular expression.