Even when similar states exist in alternation, the DFA treats them
as separate items, which may complicate the transition in NFA and
cause slowdown. This change assembles the states into one. For
example, ab|ac is changed into a(b|c). This change speeds-up
matching for many branched patterns. For example, grep speeds up
more than 30× in:
seq 10000 | sed 's/$/ abcdefghijklmnopqrstuvwxyz/; s/$/./' >in
time -p env LC_ALL=C grep -vf in in
* lib/dfa.c (prune): New function.
(merge_nfa_state): New function. It merges similar NFA states.
(dfaoptimize): New function. It seeks merged and removed nodes.
(dfaanalyze): Call new function.
(dfautf8noss): Change name from dfaoptimize because of addition of new
function.
(dfacomp): Update caller.