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.
2. The method of claim 1 , wherein construction of the DFA is aborted based also in part on a determination that the identified quantity of DFA nodes in the DFA is greater than a predetermined lower threshold.
3. The method of claim 1 , wherein construction of the DFA is aborted based at least partially on usage of the memory, the processor, or some combination thereof.
4. The method of claim 1 , wherein construction of the DFA is aborted based at least partially on a time waiting for the construction of the DFA to complete.
5. A non-transitory computer-readable storage medium having embodied thereon a program, the program being executable by a processor to perform 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, 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 a 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.
6. The non-transitory computer-readable storage medium of claim 5 , wherein construction of the DFA is aborted based at least in part on identifying that the identified quantity of DFA nodes in the DFA is greater than a predetermined lower threshold.
7. The non-transitory computer-readable storage medium of claim 5 , wherein construction of the DFA is aborted based at least partially on usage of a memory, a processor, or some combination thereof.
8. The non-transitory computer-readable storage medium of claim 5 , wherein construction of the DFA is aborted based at least partially on a time waiting for the construction of the DFA to complete.
9. A system for optimizing pattern analysis, the system comprising:
a processor; and
a memory coupled to the processor, wherein execution of instructions stored in the memory by the processor:
constructs a non-deterministic finite automaton (NFA) from a regular expression,
initiates construction of a deterministic finite automaton (DFA) from the NFA, wherein initiating construction of the DFA includes identifying a quantity of DFA nodes of the DFA,
identifies a total quantity of operands and operators present in the regular expression,
calculates a square of the identified total quantity of operands and operators of the regular expression, and
aborts 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.
10. The system of claim 9 , wherein aborting construction of the DFA is further based at least partially on usage of the memory, the processor, or some combination thereof.
11. The system of claim 9 , wherein aborting construction of the DFA is further based at least partially on a time waiting for the construction of the DFA to complete.
12. The system of claim 9 , wherein construction of the DFA is aborted based at least in part on identifying that the identified quantity of DFA nodes in the DFA is greater than a predetermined lower threshold.