Implementations and Running Times
There are at least three different algorithms that decide if and how a given regular expression matches a string.
The oldest and fastest rely on a result in formal language theory that allows every nondeterministic finite automaton (NFA) to be transformed into a deterministic finite automaton (DFA). The DFA can be constructed explicitly and then run on the resulting input string one symbol at a time. Constructing the DFA for a regular expression of size m has the time and memory cost of O(2m), but it can be run on a string of size n in time O(n). An alternative approach is to simulate the NFA directly, essentially building each DFA state on demand and then discarding it at the next step. This keeps the DFA implicit and avoids the exponential construction cost, but running cost rises to O(m2n). The explicit approach is called the DFA algorithm and the implicit approach the NFA algorithm. Adding caching to the NFA algorithm is often called the "lazy DFA" algorithm, or just the DFA algorithm without making a distinction. These algorithms are fast, but using them for recalling grouped subexpressions, lazy quantification, and similar features is tricky.
The third algorithm is to match the pattern against the input string by backtracking. This algorithm is commonly called NFA, but this terminology can be confusing. Its running time can be exponential, which simple implementations exhibit when matching against expressions like (a|aa)*b that contain both alternation and unbounded quantification and force the algorithm to consider an exponentially increasing number of sub-cases. This behavior can cause a security problem called Regular expression Denial of Service.
Although backtracking implementations only give an exponential guarantee in the worst case, they provide much greater flexibility and expressive power. For example, any implementation which allows the use of backreferences, or implements the various extensions introduced by Perl, must include some kind of backtracking. Some implementations try to provide the best of both algorithms by first running a fast DFA algorithm, and revert to a potentially slower backtracking algorithm only when a backreference is encountered during the match.
Read more about this topic: Regular Expression
Famous quotes containing the words running and/or times:
“Tattoo-shops, consulates, grim head-scarfed wives;
And out beyond its mortgaged half-built edges
Fast-shadowed wheat-fields, running high as hedges,
Isolate villages, where removed lives
Loneliness clarifies. Here silence stands
Like heat. Here leaves unnoticed thicken,
Hidden weeds flower....”
—Philip Larkin (1922–1986)
“Since I am a man, my heart is three or four times less sensitive, because I have three or four times as much power of reason and experience of the world—a thing which you women call hard-heartedness. As a man, I can take refuge in having mistresses. The more of them I have, and the greater the scandal, the more I acquire reputation and brilliance in society.”
—Stendhal [Marie Henri Beyle] (1783–1842)